링크드 리스트 [Linked List]
자료구조 2번째 Linked List posting 입니다.
링크드리스트란 ?
링크드리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있다. 여러 개의 노드들이 포인터를 통해서 한 줄로 연결된 방식이다. 그리고 아래의 그림과 같이 마지막의 노드의 다음 가리키는 부분이 없으므로, null pointer를 가지게 된다.
배열과의 비교
Linked List와 유사한 배열과의 비교를 해보겠습니다.
먼저 배열의 경우, 인덱스만 알고 있다면 찾으려는 자료를 O(1)에 가능하지만, 리스트는 순차적으로 탐색을 해야 하고, 순회를 거치게 된다면 O(N)의 시간이 걸리게 됩니다.
다음으로는 배열은 미리 크기를 할당해두고 사용해야 하기 때문에, 수정할 수 없고 이로 인해서 낭비되는 공간도 존재할 수 있습니다. 하지만 Linked List의 경우 크기의 제한이 없기 때문에 데이터 추가 삭제가 자유롭습니다.
| 배열(Array) | 연결 리스트( LinkedList ) |
|---|---|
| 정적 자료구조 | 동적 자료구조 |
| 크기를 정해두고 사용 | 크기를 정해둘 필요 없음 |
| index를 통해 접근이 편함 | 추가 삭제 편함 |
| 데이터 임의 접근이 가능하다 | 순차적으로 데이터 탐색 |
Linked List의 종류
- singly Linked List
위에서 언급했던, 마지막 tail node에 null pointer를 가지고 있는 것이 특징입니다.
- Doubly Linked List
노드에 포인터가 두 개 존재하고, 앞 뒤 노드들을 탐색 할 수 있습니다.
- Circularly Linked List
1번의 Singly Linked List는 tail node에서 끝이 나게 되지만, Circularly Linked List는 tail node가 가장 앞의 head node를 가리켜서 앞으로 돌아오게 됩니다.
Linked List로 구현하는 다른 자료구조 (자세한 설명 추가 예정)
- Stack
Linked List를 이용하여서 head 부분을 stack의 top으로 생각하여 구현하게 된다면 O(1)의 시간으로 삭제와 삽입이 가능하게 됩니다.
- Queue
Linked List를 이용하여서 FIFO(First In First Out)의 형태인 Queue를 구현할 수 있습니다. 삽입은 Node의 tail에서 삭제는 Node의 head에서 이루어지게 됩니다. 삽입의 경우 노드의 끝에서 이루어지므로 O(N), 삭제는 노드의 앞에서 이루어지므로 O(1)이 걸리게 됩니다.
- Tree
Tree는 계층적인 구조를 가지는 자료구조로, 각 노드는 자식 노드들을 가지고 있습니다. Tree를 Linked List로 구현할 경우, 각 노드는 자식 노드들의 참조를 리스트로 가지고 있습니다. 루트 노드를 Linked List의 head로 설정하고, 각 노드의 자식 노드를 Linked List의 다음 노드로 연결하여 구현할 수 있습니다.
- Graph
Graph는 노드들이 연결된 자료구조로, 각 노드는 다른 노드들과의 연결 정보를 가지고 있습니다. Graph를 Linked List로 구현할 경우, 각 노드는 연결된 노드들의 참조를 리스트로 가지고 있습니다. 이를 인접 리스트(Adjacency List)라고 합니다. 인접 리스트는 Sparse Graph(간선이 적은 그래프)에서 유용합니다. 만약 Dense Graph(간선이 많은 그래프)를 Linked List로 구현하면 메모리를 많이 사용하게 되므로 인접 행렬(Adjacency Matrix)을 사용하는 것이 좋습니다.
- 참고 블로그