Singly Linked List vs Doubly Linked List vs Circular Linked List 시간복잡도 & 사용 사례

Singly Linked List (단일 연결 리스트)

각 요소가 다음 요소만 가리키는 단일 방향 구조이다.

시간 복잡도

검색

- 처음 노드(head)부터 하나씩 순회하며 원하는 값을 찾아야 하므로 O(n)

 

삽입

- 시작에 원소를 삽입하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간에 원소를 삽입하는 경우, 처음부터 순회하여 삽입할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝에 원소를 삽입하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

 

삭제

- 시작 원소를 삭제하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간 원소를 삭제하는 경우, 처음부터 순회하여 삭제할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝 원소를 삭제하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

 

사용 사례

- 스택과 큐의 구현: 삽입 및 삭제 연산이 O(1)의 시간복잡도를 가지기 때문에 스택/큐 구현에 주로 사용된다.

 

Doubly Linked List (이중 연결 리스트)

각 요소가 이전 요소와 다음 요소를 모두 가리키는 이중 방향 구조이다.

각 노드가 다음(next) 노드와 이전(prev) 노드를 가리키는 두 개의 포인터를 가지고 있다.

시간 복잡도

검색

- 처음 노드(head)부터 하나씩 순회하며 원하는 값을 찾아야 하므로 O(n)

 

삽입

- 시작에 원소를 삽입하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간에 원소를 삽입하는 경우, 처음부터 순회하여 삽입할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝에 원소를 삽입하는 경우, tail 노드의 포인터만 변경하면 되므로 O(1)

 

삭제

- 시작 원소를 삭제하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간 원소를 삭제하는 경우, 처음부터 순회하여 삭제할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝 원소를 삭제하는 경우, tail 노드의 포인터만 변경하면 되므로 O(1)

 

사용 사례

- 텍스트 에디터 구현: 사용자가 커서를 앞 뒤로 움직이면서 텍스트를 편집할 수 있어야 한다. 이때 이중 연결 리스트가 유용하며 각 노드가 한 문자를 나타내는 방식으로 구현될 수 있다. 

- 브라우저의 히스토리: 브라우저에서 '앞으로 가기'와 '뒤로 가기' 버튼을 구현할 때 효과적이다. 각 노드는 한 개의 웹 페이지 URL을 저장하고, 사용자가 앞/뒤로 이동할 때마다 이중 연결 리스트를 통해 쉽게 탐색할 수 있다.

- 캐시 구현: LRU(Least Recently Used) Cache와 같이 삽입/삭제가 빈번한 경우 이중 연결 리스트를 사용하면 효율적이다. 중간에 새로운 항목을 삽입하거나 가장 오래된 항목을 삭제하는 작업을 빠르게 수행할 수 있다.

 

Circular Linked List (원형 연결 리스트)

마지막 요소의 포인터가 첫 요소를 가리키는 형태로 구성된 연결리스트이다.

단일 원형 연결 리스트

시간 복잡도

검색

- 처음 노드(head)부터 하나씩 순회하며 원하는 값을 찾아야 하므로 O(n)

 

삽입

- 시작에 원소를 삽입하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간에 원소를 삽입하는 경우, 처음부터 순회하여 삽입할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝에 원소를 삽입하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

 

삭제

- 시작 원소를 삭제하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간 원소를 삭제하는 경우, 처음부터 순회하여 삭제할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝 원소를 삭제하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

 

이중 원형 연결 리스트

시간 복잡도

검색

- 처음 노드(head)부터 하나씩 순회하며 원하는 값을 찾아야 하므로 O(n)

 

삽입

- 시작에 원소를 삽입하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간에 원소를 삽입하는 경우, 처음부터 순회하여 삽입할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝에 원소를 삽입하는 경우, head 노드의 이전(prev) 주소를 따라가면 마지막 노드가 있기 때문에 O(1)

 

삭제

- 시작 원소를 삭제하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

- 중간 원소를 삭제하는 경우, 처음부터 순회하여 삭제할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 끝 원소를 삭제하는 경우, head 노드의 이전(prev) 주소를 따라가면 마지막 노드가 있기 때문에 O(1)

 

사용 사례

- Round Robin 알고리즘을 이용한 프로세스 스케줄링: 예를 들어, 프로세스 A, B, C가 있을 때, Circular Linked List는 A -> B -> C -> A의 형태로 구성된다. 스케줄러는 이 리스트를 따라 순환하면서 각 프로세스에게 CPU를 할당한다. (프로세스 C의 시간 할당이 끝나면 다시 프로세스 A로 돌아가게 된다.)