Array List 그리고 Linked List
List: 순서o 중복o
Set: 순서x 중복x
리스트 관련 동작들: insert/ delete/ read/ empty/ count etc.
<Array List>
장점
- tail에 insert/ delete가 O(1)으로 빠르다.
- index를 알고있다면 read가 O(1)으로 빠르다. → 항목 접근 속도가 빠르고 일정하다.
단점
- head에 insert/ delete가 O(n)으로 느리다. → 삽입/ 삭제가 복잡하다.
- 크기 고정으로 인해 사용 전 배열 크기 지정을 해야한다.
- 메모리를 한 덩어리로 차지하므로 배열 크기가 클 경우, 배열 전체를 위한 메모리를 할당 받지 못하는 경우가 있다.
<Linked List>
: 각 노드가 데이터와 포인터를 가지로 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
- Singly Linked List
: 삽입 시, 먼저 그 자리에 있던 노드 가르킨 후 헤드 포인터가 새로 삽입 된 노드를 가르켜야 한다. 싱글리 링크드 리스트는 끝에 삽입/삭제 연산 시 넣을 자리 전 값을 알아야하기 때문에 O(n)이 소요된다.
- head와 tail을 가진 SLL
: tail이 생기면 끝에 삽입하거나 값을 가져오는 동작은 O(1) 시간으로 가능하겠지만, 삭제시 전 노드를 찾아야 하기 때문에 결국 O(n) 시간이 든다.
- Doubly Linked List
: 이제 끝에서 삭제하는 것도 양쪽에 링크가 있기에 O(1)로 한번에 된다. 하지만 n번째 요소에 대한 read는 O(n)이 걸린다.
- Head node를 가진 DLL
: 기존 DLL의 경우 노드가 하나도 없는 상태에서 동작을 실행하려면 if문이 많이 필요하다. 그래서 초기 노드 셋팅을 해놓는 것이 이점이 있다. head node를 설정해주고, ㅁ이 앞에 넣으면 head, 뒤에 넣으면 tail에 넣는 격이다.
- Circular Singly Linked List
: 처음에 tail 값대신 head값만 가지고, 끝 노드가 첫 노드를 가르키게 하는 방식이다. head를 없애고 tail만 가지고 있다면? insert head를 못한다.
<Array vs Linked List>
| Array | SLL(h) | SLL(h/t) | DLL | |
| 특정 위치 찾기 | O(1) | O(n) | O(n) | O(n) |
| 앞에 추가 | O(n) | O(1) | O(1) | O(1) |
| 뒤에 추가 | O(1) | O(n) | O(1) | O(1) |
| 앞에서 삭제 | O(n) | O(1) | O(1) | O(1) |
| 뒤에서 삭제 | O(1) | O(n) | O(n) | O(1) |
| 중간에서 추가/삭제 | O(n) | O(1) O(n) | O(1) O(n) | O(1) |
| 중간 앞에 추가 | - | O(n) | O(n) | O(1) |
메모리는 Array가 적게 들지만, 메모리 공간을 낭비할 확률이 높다. Linked List는 사용할 만큼 + 링크 크기 만큼만 자리 차지한다.