Array

• element들이 인접한 memory에 저장됨
• 선언 시점에 size가 지정됨 (변경 불가)
• Compile time에 memory가 할당됨 (Stack memory 영역에)
• 특정 element에 index로 바로 접근이 가능 - O(1)
• 삽입하려는 특정 index에 접근 후 삽입/삭제 후 전체 배열 요소를 1씩 이동 - O(1) + O(N)
• 조회에 용이함
  • 중간의 데이터를 삭제하면 공간 낭비가 발생함

Linked List

• 첫번째 노드인 head, 마지막 노드인 tail를 두고 각 노드가 다음 노드를 가리키는 포인터를 가지고 있어 노드들이 연결되는 구조
• element들이 각각 memory 어딘가에 저장됨
• runtime 시점에 node가 추가/삭제될 때마다 size가 바뀜
• Runtime에 추가/삭제될 때마다 memory가 할당/해제됨 (Heap memory 영역에
• 처음부터 순차적으로 접근하면서 특정 element를 찾아야 함 - O(N)
• 삽입하려는 위치에 접근 후 삽입/삭제 - O(N)
• 수정에 용이함
  • 배열처럼 뒤 element들을 모두 shift할 필요 없이 앞뒤 노드의 포인터만 바꿔주면 됨

Doubly Linked List (이중 연결 리스트)

• 기본 Linked List는 각 노드가 다음 노드의 포인터만 가지고 있음
• 이중 연결 리스트는 각 노드가 앞, 뒤 노드의 포인터를 모두 가지고 있음
• 탐색하려는 노드가 tail에 가깝다면 tail부터 역행해 빠르게 찾을 수 있으므로 이점이 있음

Circular Linked List (원형 연결 리스트)

• 기본, 이중 연결 리스트의 경우 tail 노드의 포인터는 마지막이므로 null을 가리키고 있음
• 원형 연결 리스트는 tail 노드가 head 노드를 가리키고 있음
• 순회를 반복하다보면 최초 시작 위치로 돌아오게 됨

Doubly Circular Linked List (이중 원형 연결 리스트)

• 이중으로, 원형으로 연결된 Linked List