[알고리즘][자료구조] Linked List (링크드 리스트)

 

Linked List

원소의 추가/삭제가 빈번하게 일어날 때,

배열은 해당 원소 이후의 모든 원소를 1칸씩 앞/뒤로 옮겨 주어야합니다.

 

이런 문제를 해결한 자료 구조가 Linked List입니다.

하나의 Node가 다음 Node에 대한 Link를 가지고 있는 것이 Single Linked List

이전 node에 대한 Link도 가지고 있는 경우 Double Linked List

아래 그림과 같이 간단한 작업으로 Node의 추가 삭제가 가능합니다.

보통 Head에는 Data를 가지지 않고 Node1에 대한 Link만을 가지고, Tail Node에서 next로 Nullptr을 가지는 것이 일반적입니다.

 

하지만 이 Linked List는 특정 원소에 접근하는 시간이 길다는 단점이 있습니다.

ArrayList같은 경우는 O(1)에 접근하게 되지만 LinkedList는 O(n) 이 걸리게 되죠.

(예를 들어 100번째 자료에 접근하려면 ArrayList는 arr[99]지만 LinkedList는 node->next를 100번 수행해야하죠)

문제의 특성에 따라서 자료구조를 결정하면 됩니다.

 

이 Linked List를 이용하여 Stack과 Queue를 만들 수 있습니다.

Stack은 FILO (First-in Last-out,) Queue는 FIFO (First-in First-out) 구조입니다.

Linked List를 응용해서 만들면 간단하게 작성이 될 것입니다.

 

단, Queue를 만들 때는, 일반적인 linked list나 stack과는 다르게 front, rear에 대한 정보를 가지고 있어야 합니다.

(Queue에서는 일반적으로 제일 먼저 호출되어야 하는(혹은 제일 먼저 추가된) Node를 front, 마지막 Node를 Rear라고 부릅니다.

Stack에서는 Top이라고 부릅니다.)

Linked List를 이용하여 우선순위 큐도 만들 수 있는데 우선순위 큐는 Linked List 보다는 Heap을 많이 사용합니다.

탐색 시간은 Linked List는 O(1)이고 Heap은 O(logn) 입니다.

하지만 추가 시간은 O(n)이고, Heap은 O(logn) 입니다.

Priority Queue with Linked List: O(1) + O(n) = O(n)

Priority Queue with Heap: O(logn) + O(logn) = O(logn) 이므로  보통Heap을 사용합니다.