<목차>
ArrayList
LinkedList
ArrayList 와 LinkedList
기본적인 자료구조인 ArrayList와 LinkedList의 각 특성과 작업에 대한 시간복잡도 등을 비교하며 정리해보았다.
ArrayList
항목들이 순서대로 나열되어 있고, 각 항목들은 위치(인덱스)를 갖는다.
해당 인덱스에 값이 위치하기 때문에, 데이터 탐색 시 인덱스를 통해 바로 접근할 수 있다. => 시간복잡도 O(1)
파이썬의 리스트는 ArrayList로 구현되어 있다.
따라서 큰 프로젝트나 손해를 볼 수 있는 경우에 파이썬의 리스트를 쓰면 안 좋을 수 있다. 배우 비효율적이고 엄청 느리기 때문이다.
파이썬에서 Linked List가 필요하면 'deque'를 사용하면 된다.
from collections import deque
queue = deque() # deque 생성
queue.append(new_element) # 새로운 원소 삽입(맨 뒤에)
value = queue.pop() # 맨 뒤 원소 뽑기(반환하고 큐에서 제거)
queue.appendleft(new_element) # 새로운 원소 삽입 (맨 앞에)
value = queue.popleft() # 맨 앞 원소 뽑기(반환하고 큐에서 제거)
① 삽입
삽입 시 만약 초기 설정한 크기가 넘는다면 기존 배열 크기의 2배로 더블링(Doubling)해서 더 큰 공간을 만들어 할당하고 기존 배열을 복사해서 옮겨버린다. 그 후 삽입할 위치 뒤에 데이터들을 밀어준다. 그리고 삽입할 위치에 데이터를 넣어준다.
1. allocation → 2. memcopy → 3. free
맨 앞에 원소 삽입 시 데이터를 밀어주는 작업이 있기 때문에 시간복잡도는 O(n)이다.
② 삭제
삭제할 데이터가 위치한 곳에서 데이터 삭제 후, 그 뒤의 데이터들을 앞으로 당겨준다.
이것도 삽입과 마찬가지로 데이터를 당겨주는 작업이 있기 때문에 시간복잡도는 O(n)이다.
<ArrayList를 사용하면 좋은 경우>
- 검색이 잦은 경우 적합하다.
인덱스를 통해 바로 접근할 수 있기 때문이다.(시간복잡도 O(1))
순차적으로 접근해야 한다면? 그래도 ArrayList가 LinkedList보다 빠르다.
ArrayList는 메모리에 연속되어 저장되는 반면, LinkedList는 무작위의 공간에 저장되기 때문이다.
따라서 다음 데이터의 주소를 찾은 후 접근하기보다 메모리상 연속적으로 저장된 ArrayList가 더 빠르다.
<적합하지 않은 경우>
데이터의 추가&삭제가 많은 경우, ArrayList보다는 LinkedList를 사용하는 것이 좋다.
LinkedList
LinkedList의 종류
- Singly Linked List (단순 연결 리스트)
- Circular Linked List (원형 연결 리스트)
- Doubly Linked List (이중(양방향) 연결 리스트)
- Circular Doubly Linked List (양방향 연결 리스트)
1. Singly Linked List (단순 연결 리스트)
[데이터 | 링크]로 이루어진 노드, 맨 첫 노드를 가리키는 포인터 Head로 이루어져 있다.
각 노드의 링크는 다음 노드의 데이터를 가리킨다.
맨 마지막 원소는 Null이나 None을 가리킨다.
맨 마지막 원소를 가리키는 포인터인 Tail을 쓰기도 한다.(Optional이지만, 보통 많이 사용한다.)
2. Circular Linked List (원형 연결 리스트)
단순 연결 리스트에서 맨 마지막 노드의 링크가 맨 앞 원소를 가리키는 구조이다.
3. Doubly Linked List (이중(양방향) 연결 리스트)
단순 연결 리스트와 비슷하지만, 양방향 연결 리스트의 노드는[앞 링크 | 데이터 | 뒤 링크]로 이루어져 있다.
따라서 노드의 앞뒤(양쪽)으로 이동할 수 있다.
① 접근
인덱스가 없기 때문에, 데이터에 접근 시 Head로부터 차례대로 탐색한다.
따라서 시간복잡도는 O(n)이다.
② 삽입&삭제
연결된 주소만 바꿔주면 된다.
맨앞 또는 맨끝이 아닌 중간에 원소 삽입/삭제 시 해당 인덱스의 데이터를 검색해서 연결된 주소만 바꾸면 되기 때문에,
시간복잡도는 O(n)이다.
오직 맨앞 또는 맨끝에서 삽입/삭제 시 시간복잡도는 O(1)이다.
4. Circular Doubly Linked List (양방향 원형 연결 리스트)
양방향 연결리스트와 원형 연결 리스트를 합친 것이라고 보면 된다.
앞뒤로 이동할 수 있고, 맨 앞 노드는 맨 뒤 노드를 가리키고, 맨 뒤 노드는 맨 앞 노드를 가리킨다.
<LinkedList 사용하기>
- 데이터의 추가, 삭제가 많은 경우 적합하다.
데이터의 위치를 색인하는 속도를 제외하면 O(n)
의 속도로 추가 및 삭제할 수 있기 때문이다.
- 원소 개수를 모르는 경우 적합하다.
뒤에 계속해서 추가할 수 있기 때문이다.
마무리
[시간복잡도]
| ArrayList | LinkedList | |
| 접근 | O(1) | O(n) |
| 중간에 삽입/삭제 | O(n) | O(n) |
| 맨앞/맨끝에 삽입/삭제 | O(1) |
- 검색이 잦은 경우, 인덱스를 사용하는 ArrayList 사용
- 추가/삭제가 많은 경우, LinkedList 사용