연결 리스트란?
연결 리스트(linked list):
각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
연결 리스트(Linked List) vs 배열(Array)
-
조회(read) 속도는 배열이 리스트보다 빠르다. 왜냐하면 배열은 인덱스만 있으면 O(1)에 가능하지만, 리스트는 최소 한 번 순회를 거쳐야 하기 때문에 O(n)이 걸린다.
-
삽입(insertion)과 삭제(delete) 속도는 리스트가 배열보다 빠르다. 리스트는 중간에 데이터를 삽입하게 되면 양옆 노드의 링크 정보만 변경하면 된다.
| 배열 | 연결리스트 | |
|---|---|---|
| 조회 | O(1) | O(n) |
| 삽입 및 삭제 | O(n) | O(1), 단, 해당 원소의 위치를 알고 있는 경우 |
| 메모리 상의 배치 | 연속적 | 불연속적 |
연결 리스트는 배열과 달리 메모리 공간에서 떨어져 있는 데이터를 링크(포인터)로 연결한 형태이다. 따라서 중간 지점에서도 자료의 추가와 삭제가 O(1) 시간에 가능하다. 하지만 배열과 달리 특정 위치의 데이터를 검색하는 데는 O(n) 시간이 걸리는 단점이 있다. 이는 연결된 노드를 순회해야 하기 때문이다.
연결 리스트의 종류
단순 연결 리스트(Singly linked list)
단일 연결 리스트는 가장 기본적인 형태의 연결 리스트로, 각 노드는 하나의 데이터와 다음 노드를 가리키는 포인터를 포함한다.
Head -> Node1 -> Node2 -> Node3 -> ... -> NodeN -> None- 방향성: 한 방향으로만 이동 가능 (이전 노드로는 갈 수 없다.)
- 시간 복잡도: 조회
O(n), 삽입/삭제O(1)(단, 해당 원소의 위치를 알고 있는 경우)
이중 연결 리스트 (Doulbe Linked List)
이중 연결 리스트는 각 노드가 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 포함한다.
None <- Node1 <-> Node2 <-> Node3 <-> ... <-> NodeN -> None- 방향성: 양방향 이동 가능
- 시간 복잡도: 조회 O(n), 삽입/삭제 O(1) (단, 해당 원소의 위치를 알고 있는 경우)
원형 연결 리스트 (Circular Linked List)
원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 포인터를 포함하여 원형 구조를 이룬다.
Head -> Node1 -> Node2 -> Node3 -> ... -> NodeN -> Head- 방향성: 마지막 노드에서 Head를 가리켜 원형 이동 가능
- 시간 복잡도: 조회 O(n), 삽입/삭제 O(1) (단, 해당 원소의 위치를 알고 있는 경우)
비교표
| 종류 | 방향성 | 시간 복잡도 (조회) | 시간 복잡도 (삽입/삭제) | 메모리 사용 |
|---|---|---|---|---|
| 단일 연결 리스트 | 단방향 | O(n) | O(1) | 적음 |
| 이중 연결 리스트 | 양방향 | O(n) | O(1) | 중간 |
| 원형 연결 리스트 | 단방향/양방향 | O(n) | O(1) | 중간 |
연결 리스트의 시간 복잡도
접근(Access) 시간 복잡도: O(n)
- 인덱스 x에 있는 노드에 접근하려면 Head에서 시작하여 다음 노드로 x번 이동해야 한다.
- 마지막 노드에 접근하려면 Head에서 시작하여 n-1번 이동해야 한다.
- 최악의 경우 시간 복잡도: O(n)
탐색(Find) 시간 복잡도: O(n)
- 배열을 탐색할 때와 같은 방법으로 선형 탐색을 한다.
- 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 노드를 찾는다.
- 찾는 데이터가 리스트에 없거나 마지막 노드에 있는 경우, n개의 노드를 모두 탐색해야 한다.
- 최악의 경우 시간 복잡도: O(n)
삽입/삭제(Insertion/Deletion) 시간 복잡도: O(1)
- 삽입 또는 삭제할 노드의 주변 노드들의 링크만 수정하면 된다.
- 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정하다.
- 시간 복잡도: O(1)
어떠한 상황에서 사용하면 좋을까?
1) 데이터 삽입과 삭제가 빈번한 경우:
연결 리스트는 데이터를 삽입하거나 삭제할 때 링크만 조정하면 되기 때문에 배열과 달리 데이터의 이동이 필요하지 않다. 따라서 삽입과 삭제 연산이 빈번한 상황에서 유리하다.
2) 메모리 관리가 중요한 경우:
연결 리스트는 포인터를 이용해 각 노드를 연결하기 때문에 메모리 공간을 유연하게 사용할 수 있다. 또한, 노드가 필요할 때마다 동적으로 할당하므로 메모리의 낭비를 줄일 수 있다.
3) 크기가 변동적일 때:
배열은 크기가 고정되어 있지만, 연결 리스트는 동적으로 크기를 조절할 수 있다. 따라서 데이터의 크기가 변동적이거나 미리 크기를 예측하기 어려운 경우에 적합하다.
4) 무작위 접근이 많은 경우:
연결 리스트는 포인터를 이용해 임의의 노드에 접근할 수 있지만, 순차적인 접근은 비효율적이다. 따라서 데이터를 무작위로 접근해야 할 때 적합하다.
요약하면, 연결 리스트는 데이터의 삽입과 삭제가 빈번하거나 크기가 변동적이며, 메모리 관리가 중요한 상황에서 특히 유용하다고 볼 수 있다. 많은 자료 구조(큐, 스택, 그래프 등)가 연결 리스트를 기반으로 구현되는 만큼 연결 리스트를 이해하는 것은 중요하다. 헷갈리지 않게 잘 공부해두자.
