2022 01 25

2022-01-24¶

데이터 구조 - 연결 리스트¶

앞선 뉴스레터들에서 배열을 알아보고, 배열을 통해 스택과 큐를 구현했어요. 하지만 배열을 사용하는 것은 몇 가지 불편한 점이 있었어요. 우선 코드를 실행하기 전 (컴파일 타임) 에 배열의 사이즈를 지정해야 했어요. 또한 배열은 원소의 삽입/삭제에 유연하지 못했어요. 삽입/삭제할 원소의 뒤 원소들에 대해 모두 위치를 변경해줘야 하기 때문이죠. 이번 뉴스레터에서는 배열과는 또 다른 매력이 있는 선형 자료구조인 연결 리스트를 소개할게요.
연결 리스트는 여러 개의 노드가 이어진 형태로 구성되어요. 노드는 아래 그림과 같이 Data와 Next로 구성되어 있어요. Data에는 해당 노드가 담아야 할 데이터를, Next에는 다음 순서의 노드를 가리키는 주소/참조를 가져요.
연결 리스트에 순차적으로 10, 20, 30을 저장하면 다음과 같은 형식으로 저장되어요.
- 첫 번째 노드의 Data에는 10을 담고, Next에는 두 번째 노드의 참조를 담아요.
- 두 번째 노드의 Data에는 20을 담고, Next에는 세 번째 노드의 참조를 담아요.
- 세 번째 노드의 Data에는 30을 담고, Next에는 null을 담아요.
이제 배열과 연결 리스트를 비교해볼까요? 10, 20, 30을 순차적으로 저장한 배열과 연결 리스트의 맨 앞에 40이라는 값을 삽입하고 싶어요.
배열의 경우, 모든 원소를 한 칸씩 뒤로 미룬 뒤, 40을 맨 앞에 저장해요. (O(n) 시간복잡도) 만약 초기에 할당된 배열이 3칸이었다면, 아예 삽입할 수 없을 것이에요.
연결 리스트의 경우, 새로운 노드를 만들어 Data에는 40을 담고, Next에는 기존 첫 번째 노드의 참조를 담아요. (O(1) 시간복잡도) 배열에 비해 쉽게 원소를 삽입할 수 있어요.
삭제도 마찬가지예요. 배열은 삭제하고자 하는 원소의 뒤부터는 모두 위치를 변경해야 해요. (O(n) 시간복잡도) 반면 연결 리스트는 삭제하고자 하는 노드의 이전 노드와 다음 노드를 연결해주면 삭제가 되어요. (O(1) 시간복잡도) 연결 리스트는 배열보다 원소의 삽입/삭제가 용이해요.
하지만 탐색의 경우 배열이 더 빨라요. 배열은 index 값을 통해 특정 위치의 원소에 접근할 수 있어요. (O(1) 시간복잡도) 배열의 원소들은 메모리상에 붙어서 할당되어 있기 때문이죠. 반면 연결리스트는 index 값의 원소에 접근하기 위해 순차적으로 탐색해야 해요. (O(n) 시간복잡도) 연결리스트의 노드들은 메모리상에 띄엄띄엄 존재하기 때문이죠!
배열과 연결 리스트는 살펴본 것처럼 장단점을 각각 가지고 있어요. 원소의 삽입/삭제가 많이 필요하다면 배열보다 연결 리스트를 활용하는 것이 더 유리할 것이에요! (스택과 큐를 연결 리스트로 구현하면 더 유연한 대처가 가능하겠죠?)

연결 리스트¶

Chunked List: 리스트의 원소가 작은 배열... Locality로 인한 Cache hit을 높이자!
B+tree: 연결 리스트 정렬은 O(n)... 밸런스드 트리로 O(nlogn) 시간에 쇼부보자!