연결리스트

• 데이터 요소의 선형 집합
• 데이터 요소(노드)들이 포인터를 통해 순차적으로 연결되어 있는 구조
• 각 노드는 데이터와 하나 또는 여러 개의 포인터(다음 노드를 가리키는 링크)를 포함하며, 이 포인터들이 전체적으로 연결된 체인을 형성

연결 리스트의 장점

• 동적 메모리 할당
• 데이터 삽입 및 삭제 용이

연결 리스트의 단점

• 순차 접근 : 연결 리스트에서는 특정 요소에 접근하기 위해 처음부터 순차적으로 탐색해야 한다. 이는 배열의 직접 접근에 비해 느림
• 메모리 오버헤드 : 각 노드가 데이터 외에도 포인터를 포함하므로, 배열에 비해 추가적인 메모리 공간이 필요

연결 리스트의 종류

• 단일 연결 리스트(Singly Linked List) : 각 노드가 다음 노드만을 가리키는 가장 간단한 형태

• 이중 연결 리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 형태

• 원형 연결 리스트(Circular Linked List) : 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키는 형태

  단일 연결 리스트 예시

  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):
         if not self.head:
             self.head = Node(data)
         else:
             current = self.head
             while current.next:
                 current = current.next
             current.next = Node(data)
  
     def display(self):
         elements = []
         current = self.head
         while current:
             elements.append(current.data)
             current = current.next
         print(elements)
  
     def delete(self, data):
         current = self.head
         if current and current.data == data:
             self.head = current.next
             return
         prev = None
         while current and current.data != data:
             prev = current
             current = current.next
         if current:
             prev.next = current.next
  linked_list = LinkedList()
  linked_list.append(1)
  linked_list.append(2)
  linked_list.append(3)
  linked_list.display()  # [1, 2, 3]
  linked_list.delete(2)
  linked_list.display()  # [1, 3]