[CS기초] 연결 리스트(Linked List)

연결 리스트

연결 리스트(Linked List)는 각 데이터가 메모리 상의 불연속적인 위치에 저장되면서, 다른 데이터(노드)의 위치 정보를 함께 저장하는 자료구조이다. 배열과 달리 요소들이 물리적으로 연속되어 있지 않아도 논리적으로 연결되어 있으며, 삽입과 삭제가 효율적이라는 장점이 있다.

연결 리스트의 종류

• 단일 연결 리스트 : 각 노드가 자신의 데이터와 다음 노드의 주소만을 저장한다.
• 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드의 주소를 모두 저장한다. 양방향 순회가 가능해 탐색 및 삭제 연산이 유연해진다.
• 원형 연결 리스트 : 연결 리스트의 끝 노드가 다시 처음 노드를 가리키는 구조이다. 단일 또는 이중 연결 리스트에 모두 적용 가능하며, 반복적인 순회에 유리하다.

 

연결 리스트의 특징

• 임의의 위치의 데이터를 확인/수정하는 데 O(N)의 시간이 소요
  • 연결 리스트는 인덱스 기반 접근이 불가능하기 때문에, 처음 노드부터 순차적으로 접근해야 원하는 위치 노드에 도달이 가능
• 임의의 위치에 노드를 삽입/삭제하는 데 O(1)의 시간이 소요
  • 단, 해당 위치의 노드 주소(포인터)를 알고 있는 경우에만 O(1)이 걸린다
  • 해당 위치의 노드 주소를 모를 경우, 삽입/삭제할 위치까지 O(N)의 시간이 걸려야 찾아갈 수 있다
  • 실제 삽입/삭제는 노드 간 포인터만 조정하면 되기 때문에, 포인터만 알고 있다면 매우 빠르게 처리된다
• 추가적인 메모리 공간 필요
  • 각 노드는 데이터 뿐만 아니라 다음 노드(또는 이전 노드)의 주소를 함께 저장해야 함
  • 이로 인해 배열에 비해 노드 당 추가적인 포인터 공간이 필요하며, 전체적으로는 노드 수 N에 비례한 추가 메모리가 요구됨
• 낮은 캐시 적중률
  • 데이터가 메모리에 불연속적으로 저장되기 때문에, CPU 입장에서 다음에 접근할 데이터를 미리 로딩해두기 어려움
  • 이로 인해 배열보다 캐시 활용 효율이 낮고, 전반적인 접근 속도가 떨어질 수 있음
• 유연한 메모리 할당
  • 연속된 메모리 공간을 필요로 하지 않기 때문에, 메모리 조각이 많아도 유연하게 할당이 가능
  • 특히 동적 할당이 자주 필요한 환경에서 유리

 

파이썬에서 연결 리스트의 구현

파이썬에서는 연결 리스트를 각 노드에 대한 객체 클래스를 만들어 구현할 수도 있지만, 여러 개의 배열만으로 데이터와 주소를 관리하는 연결리스트를 구현할 수도 있다.

MX = 1000001
data = [0] * MX
prev = [-1] * MX
next = [-1] * MX
unused = 1

# 특정 주소에 새 요소 삽입
# 새 요소가 기존 요소들을 가리키게 하고, 기존 요소들이 새 요소를 가리키게 한다.
# 단, 해당 주소가 연결 리스트의 끝일 경우, next[addr]에 대한 처리를 하지 않음.
def insert(addr, num):
    global unused
    data[unused] = num
    
    prev[unused] = addr
    next[unused] = next[addr]
    next[addr] = unused
    if next[addr] != -1:
        prev[next[addr]] = unused
    
    unused += 1
    
# 특정 주소의 요소 삭제
# 특정 주소의 양쪽 주소가 서로를 가리키게 하여 연결을 끊어버린다.
# 단, 해당 주소가 연결 리스트의 끝일 경우, next[addr]에 대한 처리를 하지 않음.
def erase(addr):
    next[prev[addr]] = next[addr]
    if next[addr] != -1:    
        prev[next[addr]] = prev[addr]
    
# 연결 리스트의 모든 요소 순회
# 아직 할당되지 않은 주소(-1)가 될 때까지 모든 요소의 data를 출력한다.
def traverse():
    cur = next[0]
    while cur != -1:
        print(data[cur], end=' ')
        cur = next[cur]
    print()

 

 

 

참고 자료

BaaaaaaaarkingDog, "[실전 알고리즘] 0x04강 - 연결 리스트", 2020. 3. 1,
https://blog.encrypted.gg/932