[크래프톤 정글] 연결 리스트

연결 리스트(Linked List)는 데이터를 노드(Node)라는 단위로 저장하며, 각 노드는 다음 노드를 가리키는 포인터를 포함하는 선형 자료 구조다. 연결 리스트는 데이터를 물리적으로 연속된 공간에 저장하지 않고, 메모리의 동적 할당을 통해 데이터 요소들이 필요할 때마다 새로운 공간을 할당받아 저장한다. 이 때문에 데이터 요소의 추가와 삭제가 비교적 자유로운 특징이 있다.

파이썬의 참조와 C 언어의 포인터의 차이

• 파이썬의 참조(Reference): 파이썬에서는 변수들이 실제 객체에 대한 참조를 저장한다. 이는 메모리 주소를 직접적으로 다루지 않기 때문에 메모리 관리가 자동으로 이루어지며, 개발자는 객체의 참조만을 다룬다. 예를 들어, 리스트의 노드가 다른 노드를 가리킬 때 그 노드는 단순히 다른 객체를 참조하고 있다는 뜻이다. 파이썬의 참조는 안전하고 메모리 관리를 자동으로 하기 때문에, 메모리 누수나 잘못된 접근 문제로부터 비교적 자유롭다.

• C 언어의 포인터(Pointer): C 언어에서는 포인터를 통해 변수의 메모리 주소를 직접 다룬다. 개발자는 변수나 객체의 메모리 주소를 명시적으로 지정하고 관리할 수 있다. 포인터는 강력한 기능을 제공하지만, 메모리 할당 및 해제를 수동으로 관리해야 하며, 잘못된 메모리 접근으로 인한 오류(예: 세그멘테이션 오류) 발생 가능성이 있다. C 언어의 연결 리스트 구현에서, 각 노드는 다음 노드에 대한 포인터를 명시적으로 포함한다.

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List)
2. 이중 연결 리스트(Doubly Linked List)
3. 원형 연결 리스트(Circular Linked List)

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

• 구조: 각 노드는 데이터와 다음 노드를 가리키는 포인터(next)를 가진다.
• 특징:
  • 처음 노드부터 마지막 노드까지 순차적으로 탐색 가능.
  • 삽입과 삭제가 쉬움: 노드를 삽입하거나 삭제할 때, 기존 포인터를 재설정하는 작업만 필요.
  • 단점은 노드 탐색 시 항상 처음부터 탐색해야 하므로, 특정 위치에 있는 노드를 찾기 위한 탐색이 비효율적이다.

단일 연결 리스트의 노드 정의 (Python 예제)

class Node:
    def __init__(self, data):
        self.data = data  # 노드의 데이터
        self.next = None  # 다음 노드를 가리키는 포인터

단일 연결 리스트의 기본 연산

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 시작을 가리키는 포인터

    # 리스트의 끝에 노드를 추가하는 함수
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 마지막 노드로 이동
                current = current.next
            current.next = new_node

    # 리스트에서 특정 값을 삭제하는 함수
    def delete(self, key):
        current = self.head
        previous = None
        while current:
            if current.data == key:
                if previous:
                    previous.next = current.next
                else:
                    self.head = current.next
                return
            previous = current
            current = current.next

    # 리스트의 모든 값을 출력하는 함수
    def display(self):
        current = self.head
        while current:
            print(current.data, end=' -> ')
            current = current.next
        print("None")

# 사용 예시
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.display()  # 출력: 1 -> 2 -> 3 -> None

linked_list.delete(2)
linked_list.display()  # 출력: 1 -> 3 -> None

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

• 구조: 각 노드는 데이터와 다음 노드를 가리키는 포인터(next), 이전 노드를 가리키는 포인터(prev)를 가진다.

• 특징:

  • 양방향으로 노드를 탐색할 수 있어, 단일 연결 리스트보다 탐색이 유연하다.
  • 양쪽으로 탐색할 수 있어 뒤로 이동하거나 역순으로 탐색할 때 효율적이다.
  • 단점은 각 노드가 두 개의 포인터를 저장하므로 메모리 사용량이 더 많아진다.

  

이중 연결 리스트의 노드 정의 (Python 예제)

class DNode:
    def __init__(self, data):
        self.data = data  # 노드의 데이터
        self.prev = None  # 이전 노드를 가리키는 포인터
        self.next = None  # 다음 노드를 가리키는 포인터

이중 연결 리스트의 기본 연산

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 시작을 가리키는 포인터

    # 리스트의 끝에 노드를 추가하는 함수
    def append(self, data):
        new_node = DNode(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

    # 리스트에서 특정 값을 삭제하는 함수
    def delete(self, key):
        current = self.head
        while current:
            if current.data == key:
                if current.prev:
                    current.prev.next = current.next
                if current.next:
                    current.next.prev = current.prev
                if current == self.head:
                    self.head = current.next
                return
            current = current.next

    # 리스트의 모든 값을 출력하는 함수
    def display(self):
        current = self.head
        while current:
            print(current.data, end=' <-> ')
            current = current.next
        print("None")

# 사용 예시
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)
doubly_linked_list.display()  # 출력: 1 <-> 2 <-> 3 <-> None

doubly_linked_list.delete(2)
doubly_linked_list.display()  # 출력: 1 <-> 3 <-> None

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

• 구조: 마지막 노드가 다시 첫 번째 노드를 가리키는 형태로, 리스트의 끝이 없는 원형 구조를 가진다.
• 특징:
  • 마지막 노드에서 다음 노드가 첫 번째 노드가 되므로 순환 구조를 만든다.
  • 메모리 효율성이 높으며, 원형 구조를 이용한 알고리즘에 유리하다.
  • 단점은 탐색에 대한 종료 조건이 필요하며, 리스트가 무한 반복될 수 있다.

원형 연결 리스트의 노드 정의 (Python 예제)

class CNode:
    def __init__(self, data):
        self.data = data
        self.next = None

원형 연결 리스트의 기본 연산

class CircularLinkedList:
    def __init__(self):
        self.head = None

    # 리스트의 끝에 노드를 추가하는 함수
    def append(self, data):
        new_node = CNode(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    # 리스트의 모든 값을 출력하는 함수
    def display(self):
        current = self.head
        if self.head:
            while True:
                print(current.data, end=' -> ')
                current = current.next
                if current == self.head:
                    break
        print("None")

# 사용 예시
circular_linked_list = CircularLinkedList()
circular_linked_list.append(1)
circular_linked_list.append(2)
circular_linked_list.append(3)
circular_linked_list.display()  # 출력: 1 -> 2 -> 3 -> None

연결 리스트의 장점과 단점

장점

1. 동적 크기: 연결 리스트는 메모리를 동적으로 할당하므로 데이터의 크기에 유연하게 대처할 수 있다.
2. 빠른 삽입과 삭제: 중간에 있는 요소를 삭제하거나 추가할 때, 노드의 포인터만 조정하면 되므로 매우 빠르다.
3. 메모리 효율성: 데이터가 연속된 메모리 공간에 저장