[알고리즘 공부] #6 연결 리스트(Linked List) 알고리즘 with Python

연결 리스트(Linked List) 

어떤 알고리즘일까?

연결리스트(Linked List)는 데이터를 순서대로 저장하는 선형 자료구조의 한 종류로, 각 요소가 노드라는 개별 단위로 존재하며, 각 노드는 데이터(value)와 다음 노드에 대한 포인터를 가지고 있다.

연결리스트 설명

---

연결리스트의 종류

연결리스트의 종류는 노드가 가지는 포인터의 개수에 따라 달라진다.

1. 단일 연결 리스트
   • 각 노드가 다음 노드에 대한 포인터를 가지며, 마지막 노드는 None을 가리켜 끝을 나타낸다.
   • 다음 노드에 대한 포인터만 가지기 때문에 한 방향으로만 값을 읽을 수 있다.
2. 이중 연결 리스트
   • 각 노드가 다음 노드와 이전 노드에 대한 포인터를 가지며, 첫 번째 노드의 이전 노드와 마지막 노드의 다음 노드는 None 값을 가진다.
   • 다음 노드와 이전 노드에 대한 포인터를 모두 가지고 있기 때문에 양 방향으로 값을 읽을 수 있다.
3. 원형 연결 리스트
   • 마지막 노드가 다시 첫 번째 노드를 가리켜 원형을 이룬다.
   • 값이 원형을 이루기 때문에 마지막 노드에서 다음 값은 첫번째 노드 값이 된다.

---

연결 리스트의 장단점

• 장점
  1. 동적 크기 조정 : 배열과 달리 연결 리스트는 미리 고정된 크기가 필요하지 않고, 데이터를 추가할 때마다 새로운 노드를 생성하여 연결만 시켜주면 되기 때문에 크기를 유연하게 조절할 수 있다.
  2. 효율적인 삽입/삭제 : 삽입이나 삭제가 필요한 위치의 노드만 수정하면 되므로, 중간에 데이터를 추가하거나 삭제할 때 O(1)의 시간 복잡도로 빠르게 처리할 수 있다.
• 단점
  1. 임의 접근 불가 : 연결 리스트는 노드들이 순차적으로 연결되어 있어, 특정 인덱스에 접근하려면 처음부터 순회해야 하므로 O(n)의 시간이 소요된다.
  2. 추가 메모리 사용 : 각 노드가 데이터뿐만 아니라 다음 노드에 대한 포인터를 저장해야 하므로, 배열보다 메모리를 더 많이 차지할 수 있다.

---

언제 사용하는가?

• 대기열 관리 : 대기열과 같이 순차적으로 처리되는 데이터 관계에 효과적이다.
• 캐시 구현 : 최근 사용된 항목을 관리하는 LRU 캐시와 같은 경우, 삽입과 삭제가 빈번하므로 이중 연결 리스트가 유용하다.
• 그래프와 인접 리스트 표현 : 그래프의 각 정점과 인접한 정점을 관리하기 위해 연결 리스트가 많이 사용된다.

---

연결리스트 예제

1158번: 요세푸스 문제

class LinkedList:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next
 
N, K = map(int,input().split())
head = LinkedList(1)
curr_node = head
 
 
for i in range(2,N+1):
    new_node = LinkedList(i)
    curr_node.next = new_node
    curr_node = curr_node.next
 
curr_node.next = head
curr_node = head
prev_node = head
cnt = 0
print("<", end="")
 
while cnt < N - 1:
    for i in range(K-1):
        prev_node = curr_node
        curr_node = curr_node.next
    prev_node.next = curr_node.next
    print(curr_node.val, end = ", ")
    curr_node = curr_node.next
    cnt += 1
 
print(curr_node.val, end=">")
 

백준에 있는 요세푸스 문제의 해결 코드이다.
각 노드가 다음 노드에 대한 정보만 담고 있으므로 단일 연결리스트를 사용한 것을 알 수 있다.

연결리스트 구현은 주로 class를 사용하며, 각 노드를 객체로 관리한다.

---