[DS] 연결 리스트 (Linked List)

출처 : https://ko.wikipedia.org/wiki/연결_리스트

 

연결 리스트 (Linked List)

연결 리스트(Linked List)는 자료를 저장하는 자료구조 중 하나로, 데이터를 일렬로 연결한 형태입니다. 연결 리스트는 각 노드(node)가 데이터와 포인터(pointer)로 이루어져 있습니다. 데이터는 자료를 저장하는 공간이고, 포인터는 다음 노드의 주소를 저장하는 공간입니다.

연결 리스트의 장점

• 삽입(insertion)과 삭제(deletion)가 용이 : 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터로 연결되어 있기 때문에, 삽입(insertion)과 삭제(deletion)가 매우 유연하게 이루어집니다.
• 동적으로 크기가 변하는 데이터를 저장할 수 있습니다. 이는 배열과는 다르게, 메모리 할당을 미리 해놓을 필요가 없기 때문입니다.
  

연결 리스트의 단점

• 검색(search) 연산에 대한 성능이 좋지 않음 : 연결 리스트는 순차적으로 노드를 탐색해야 하기 때문입니다.
• 각 노드마다 포인터를 저장하기 때문에, 메모리 사용량이 높아질 수 있습니다. 이는 연속된 메모리 공간을 필요로 하는 배열보다 메모리를 더 많이 사용한다는 것을 의미합니다.

따라서, 연결 리스트는 동적으로 크기가 변하는 데이터를 다룰 때 유용하며, 데이터의 추가 및 삭제가 빈번히 일어나는 경우에 효율적입니다. 하지만 검색 연산이 많이 일어나는 경우에는 배열보다 성능이 떨어질 수 있습니다.

 

연결 리스트 구현 (Python)

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr_node = self.head
        while curr_node.next:
            curr_node = curr_node.next
        curr_node.next = new_node
        
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        
    def delete_node(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        curr_node = self.head
        while curr_node.next:
            if curr_node.next.data == data:
                curr_node.next = curr_node.next.next
                return
            curr_node = curr_node.next
        
    def print_list(self):
        curr_node = self.head
        while curr_node:
            print(curr_node.data)
            curr_node = curr_node.next

• Node 클래스 - 각 노드를 나타낸다.
• LinkedList 클래스 - 전체 연결리스트를 나타낸다.
• append 메서드 - 연결리스트 끝에 노드를 추가한다.
• prepend 메서드 - 연결리스트 시작 부분에 노드를 추가한다.
• delete_node 메서드 - 데이터 값을 받아서 해당 값을 갖는 노드를 삭제한다.
• print_list 메서드 - 연결리스트를 출력한다.

 

# 사용 예시
my_list = LinkedList()
my_list.append("A")
my_list.append("B")
my_list.prepend("C")
my_list.delete_node("B")
my_list.print_list() # 출력 결과: C -> A