linear-not-linear

선형구조

• 데이터가 순서대로 연결되어 있다. 즉, 1개의 자료 앞뒤로 단 한개의 자료가 존재한다.

  • 그래서 구현이 쉽다.

• 포인터를 사용하여 자료를 연결시 그 갸ㅕㄹ과가 자료에 일직선상에 표시되거나 하나의 원상에 표시되는 구조

• 배열, 링크드 리스트, 스택, 큐 등이 있다.

• 배열

• 간단하고, Random Access Memory가 가능하여 접근시 O(1)이 소요된다.

• 삽입, 삭제시 발생한 인덱스 앞/뒤 자료들을 전부 이동해야 한다. 최대 O(N)이 소요될 수 있다.

1. 링크드 리스트

2. 자료의 순서에 따라 포인터를 이용하여 서로 연결됨

3. 노드의 삽입, 삭제가 O(1)이다.

   • 하지만 Random Access Memory 접근이 안되므로 검색시에는 O(N)이 소요된다.

4. 스택

5. 리스트의 한 쪽 끝에서 삽입, 삭제가 이뤄진다.

6. 인터럽트가 발생하여 복귀주소를 저장할 때 사용한다.

7. 큐

8. 삽입, 삭제가 다른 쪽에서 이뤄진다.

9. 시작과 끝을 표현하는 2개의 포인터가 있다.

10. 창구 업무와 같은 서비스 순서를 기다리는 대기 행렬 처리에 사용한다.

비선형구조

하나의 자료 뒤에 여러개의 자료가 존재할 수 있다. 즉, 여러개의 데이터가 순서대로 존재하지 않는다.

• 그래서 구현이 어렵다.

1. 트리

2. 사이클이 없는 그래프다.

3. 부모와 자식 계층이다.

4. 그래프

5. node와 vertex를 이용하여 사이클이 이뤄진다.