what?
linked list는 자료구조의 방법중 하나이다. list 라는 이름에 걸맞게 가장 많이 비교되는 것은 배열(arrat list)과의 비교이다. 아래의 그림은 배열과 링크드리스트를 도식화하여 비교해 놓은 그림이다. (출처: 생활 코딩)
그림에서 보이는 것처럼 Array list 는 한 층을 전부 쓰고 있습니다. 또한 각 호수는 index numder를 가지고있기때문에 접근하기는 쉬우나 한 층을 다 써야하기 때문에 공간낭비가 많습니다. 그러나 linked list는 각각 떨어진 호수들을 화살표로 이어서 다음 list에는 어떤 호실이 오는지 만 저장되는 것을 뜻합니다.
why?
링크드리스트를 이용하면 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.
연결 리스트의 종류별 특징
연결리스트는 연결 방향과 모양에 따라 Single , Double, Circular, Double - Circular 등의 종류를 가지고 있으며 Double - Circular 가 많이 쓰입니다.
1. 단일 연결 리스트 (Single linked List)
단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다. - 위키백과
단일 연결 리스트의 각 노드는 자신의 값과 다음 노드에 대한 정보만 가지고 있다.
배열과 비교했을 때, 동적으로 메모리를 사용할 수 있다는 장점이 있지만 자바스크립트의 배열은 동적 배열이므로 큰 장점이 없다고 할 수 있다.
각 노드가 다음 노드에 대한 정보도 가지고 있어야 하므로 배열에 비해 메모리를 추가적으로 사용하는 단점이 있다.
단일 연결
---------------- ----------------
Head --- | value | next | --- | value | next |
---------------- ----------------2. 이중 연결 리스트 (Doubly linked List)
이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. - 위키백과
이중 연결 리스트는 노드가 다음 노드 뿐만 아니라 이전 노드의 정보도 가지고 있는 구조를 가진다.
단일 연결 리스트는 새로운 노드를 추가할 때, 이전 노드의 정보를 수정하는 과정에서
첫 지점부터 다시 순회를 해야하지만 이중 연결 리스트는 이전 노드로의 이동을 통해 한 번의 반복으로 처리가 가능하다는 장점이 있다.
다만 단일 연결 리스트보다 구현이 복잡하며, 노드 삭제 시 인접한 노드에 추가적인 수정이 필요하다.
이중 연결
------------- ------------- -------------
Head --- | p | v | n | --- | p | v | n | --- | p | v | n | ---- Tail
------------- ------------- -------------3. 원형 연결 리스트 (Circularly linked)
원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다. - 위키백과
원형 연결 리스트는 마지막 노드의 정보도 가지고 있기 때문에 새로운 노드를 추가하는 과정에서
탐색없이 바로 노드를 추가할 수 있다.
다만 이중 연결 리스트보다 구현이 조금 복잡하다.
원형 연결
------------- ------------- -------------
-- | p | v | n | --- | p | v | n | --- | p | v | n | --
| ------------- ------------- ------------- |
| |
----------------------- Head --------------------------