[Python] 연결 리스트(Linked List)의 기본 (w/ singly linked list)

각 노드(node)가 데이터와 다음 노드에 대한 참조(포인터)를 가지고 있는 선형 자료구조
배열과 달리 메모리 상에 연속적으로 배치되지 않고, 각 노드가 동적으로 생성되어 연결

코드 참고 : https://www.geeksforgeeks.org/linked-list-data-structure/

링크를 끊자

 

구성 요소

• 노드(Node)
  • 데이터 : 실제 저장할 값
  • 다음 포인터 : 다음 노드의 주소(참조)를 가리킴
• 헤드(Head): 리스트의 시작 노드를 가리킴
• 테일(Tail) : 필수요소는 아니며, 리스트의 마지막 노드를 가리키며 삽입 시 효율적으로 사용될 수 있음

Linked list의 기본 구조

종류

1. 단일 연결 리스트 (Singly Linked List) : 각 노드가 다음 노드만 참조
2. 이중 연결 리스트 (Doubly Linked List) :
   • 각 노드가 이전 노드와 다음 노드 모두를 참조함
   • 양방향 탐색이 가능함
3. 원형 연결 리스트 (Circular Linked List) : 마지막 노드가 다시 첫 번째 노드를 참조하여 원형 구조를 이루는 형태

특징

• 동적 크기 조절 : 필요한 만큼 노드를 생성할 수 있어 메모리의 연속적 할당이 필요 없음
• 빠른 삽입 / 삭제 : 중간 노드의 삽입이나 삭제 시, 해당 노드의 이전 노드만 참조를 변경하면 되므로 O(1)의 연산으로 처리 가능
  단, 해당 노드의 위치를 알고 있을 때
• 임의 접근(Random Access)의 어려움 : 배열과 달리 인덱스 기반 접근이 불가능하여, 특정 위치의 데이터를 찾으려면 순차적으로 탐색해야 함 O(n)
• 포인터와 참조를 통해 연결된 연속적인 요소로 구성
• 마지막 노드는 null을 가리킴

장점

• 삽입과 삭제에 효과적임. 자료 중간에 아이템을 삽입 또는 삭제를 하기위해 몇 개의 포인터(또는 참조)만 변경해주면 됨
• 어느 지점에서든지 삽입 / 삭제 시 O(1)의 시간복잡도를 가짐. 반면, 배열형태의 자료형에서는 O(n)의 시간복잡도를 가짐
• 데이터 구조가 간단하며, 스택 / 큐 또는 다른 추상 자료형을 구현하는데 사용됨
• 일반 배열을 통해 큐 또는 덱을 구현하는 것 보다 쉽고, 직관적임
• 요소의 n값을 모르는 상태에서, 배열에 비해 공간의 효율이 좋음.

단점

• 느린 액세스 시간 : 원하는 요소를 찾기위해 탐색할 때 요소에 접근하는데 느려질 수 있어, 최종적으로는 O(n)의 시간복잡도를 가짐
• 포인터, 참조 : 다음 노드에 액세스 하기 위해 포인터나 참조를 사용하는 이유로, 배열에 비해 이해와 사용에 더 복잡함을 가짐. 이런 특성으로 유지보수와 디버깅에 어려움을 가짐
• 오버헤드 : 일반 배열보다, 다음 노드의 참조를 저장하기 위해 추가적인 메모리가 필요하여 더 큰 오버헤드를 가짐
• 캐시의 비효율성 : 메모리의 비연속성 때문에 Linked list를 순회할 때 필요한 데이터를 캐시에 가져올 수 없어 캐시 누락과 성능저하로 이어질 수 있음

활용

• 동적 데이터 저장 : 데이터의 삽입과 삭제가 빈번한 경우, 연결리스트를 사용하면 효율적 (OS와 컴파일러 등)
• 스택, 큐 구현 : 연결 리스트를 기반으로 스택이나 큐를 구현하여, 삽입/삭제 연산을 O(1)에 처리 가능
• 메모리 관리 : 배열처럼 연속된 메모리 공간이 필요없으므로, 메모리 조각화가 있는 환경에서 유리할 수 있음
• 그 외
  • 다항식의 연산 조작
  • 긴 정수에 대한 산술연산
  • 운영체제 내 메모리관리, 프로세스 스케쥴링(예를들어, round robin scheduling을 위한 round linked list), 파일 시스템 등

실생활 Linked List의 적용

OIIA OIIA

• 음악 플레이(APP)의 플레이 리스트에서의 이전곡과 다음곡의 연결
• 웹 브라우저에서 이전, 다음 버튼을 통한 이전 / 다음 페이지 URL 연결 (Doubly linked list)
• 이미지 뷰어에서 이전, 다음 사진 연결 (Doubly linked list)
• Circular Linked List는 모든 요소를 하나하나 둘러보는 동작을 구현할 때 사용
• 큐와 덱 구조를 구현할 때 배열보다 더 선호됨

 

구현 및 동작

Singly linked list

# 노드 class 선언
class Node:
    def __init__(self, data):
       # 노드 클래스는 데이터와, 다음 노드로의 연결을 설정하기 위해 포인터를 포함 
        self.data = data   
        self.next = None    

• singly linked list에서의 순회
  1. 포인터(현재)를 리스트의 헤드로 초기화
  2. current가 NULL이 될 때 까지 반복문으로 리스트를 순회
  3. 각 노드의 데이터를 처리(출력, 작동 등)
  4. 다음 노드로 이동 (current = current.next)

```python
def traverseList(head): # 반복문(while)로 구현한 순회
    # 헤드가 null 포인터가 될 때 까지 순회
    while head is not None:
        # 현재 노드의 데이터를 출력
        print(head.data, end=" ")
        # 다음 노드로 이동
        head = head.next
    print()

def traverseList(head): # 재귀로 구현한 순회
    if head is None:
        print()
        return

    print(head.data, end=" ")

    traverseList(head.next)

# 실행 코드
def main():
    # 예제 실행을 위한 linked list 생성:
    # 10 -> 20 -> 30 -> 40
    head = Node(10)
    head.next = Node(20)
    head.next.next = Node(30)
    head.next.next.next = Node(40)

    # 노드 순회 및 출력 실행
    traverseList(head)
```

• 탐색
  1. 헤드에서 출발
  2. 각 노드의 데이터를 체크
     1. 타겟값과 일치 시 True 반환
     2. 아닐경우, 다음 노드로 이동
  3. 리스트의 끝(NULL)까지 반복
  4. 그럼에도 발견하지 못하면 False 반환

```python
def search_key(head, key):  # 반복문

    # 현재 위치를 head로 초기화
    curr = head

    # 모든 노드를 순회하도록 반복
    while curr is not None:

        # 현재 노드 값이 키(타겟)과 동일하면, True 반환
        if curr.data == key:
            return True

        # 다음 노드로 이동
        curr = curr.next

    # 아닐경우 False 반환
    return False

def searchKey(head, key): # 재귀

    # Base case
    if head is None:
        return False

    if head.data == key:
        return True

    return searchKey(head.next, key)
```

• list길이 구하기 : counter 변수 선언 후 순회하며 += 1
• 특정 위치의 노드 삽입
  1. 새 노드를 생성 및 값을 정의
  2. 최초 위치에 삽입하는 조건이면
     1. 새 노드의 다음 포인트를 현재의 헤드로 선언
     2. 새 노드를 헤드로 갱신
     3. 리턴 (삽입 종료)
  3. 아닐경우, 리스트 순회
     1. 헤드에서부터 position-1번째 노드(원하는 위치 직전)까지 순회
     2. position이 리스트의 길이를 넘어갈경우, 에러를 반환하거나 끝부분에 노드를 추가
  4. 새로운 노드 삽입
     1. 현재 위치의 노드를 새 노드의 다음 포인트로 선언
     2. 이전 노드의 다음 포인트로 새 노드로 갱신
  5. 갱신된 리스트를 반환

```python
def insert_pos(head, pos, data):

    # 원하는 삽입 위치가 존재하는지 검증
    if pos < 1:
        return head

    # 삽입하기 위하는 position이 1일 경우, head를 새로운 데이터로 교체
    if pos == 1:
        new_node = Node(data)
        new_node.next = head
        size += 1
        return new_node

    curr = head

    # 새 노드 삽입 전 노드들이 존재하는지 순회
    for _ in range(1, pos - 1):
        if curr == None:
            break
        curr = curr.next

    # position이 list를 초과할 때 head로 리턴
    if curr is None:
        return head

    new_node = Node(data)

    # 다음 포인터로 이동
    new_node.next = curr.next
    curr.next = new_node

    return head
```

• 특정 위치의 노드 삭제
  1. 리스트가 비어있거나, 삭제하려는 노드의 위치가 잘못되었을 경우 종료
  2. head를 삭제할 경우, head를 다음 노드로 변경하고 삭제(새로운 헤드로 리턴)
  3. 삭제하려는 위치 전까지 노드 순회
  4. 삭제 위치가 리스트 범위를 벗어날 경우 종료(리턴)
  5. 삭제하려는 노드를 저장
  6. 삭제 대상 노드를 우회하기 위해 앞과 뒤의 노드를 재 연결(저장된 노드를 삭제)
     1. 참고 : python에서는 가비지 컬렉터가 참조가 없어지면 자동으로 메모리를 정리
        즉, 노드를 리스트 체인에서 참조하지 않게 연결을 끊는 행위가 삭제

```python
def deleteNode(head, position):
    temp = head
    prev = None

    # base case
    if temp is None:
        return head

    # Case 1: head가 삭제 대상 노드인경우
    if position == 1:
        head = temp.next
        return head

    # Case 2: 중간의 노드를 삭제할 경우
    # 목표 위치까지 순회
    for i in range(1, position):
        prev = temp
        temp = temp.next
        if temp is None:
            print("Data not present")
            return head

    # position을 찾았을 경우, 노드를 삭제
    if temp is not None:
        prev.next = temp.next

    return head

```