연결 리스트는 데이터를 담은 노드들이 연결되어 있는 자료구조입니다. 일반적으로 포인터를 사용하여 노드 간의 연결을 구현하지만, 배열을 이용하여 연결 리스트를 구현할 수도 있습니다.

구현 방법

1. 노드 클래스 정의하기

   먼저, 각 노드를 나타내는 클래스를 정의합니다. 각 노드는 데이터를 저장하는 data 속성과 다음 노드를 가리키는 next 속성을 갖습니다.

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

2. 연결 리스트 클래스 정의하기

   다음으로, 연결 리스트를 나타내는 클래스를 정의합니다. 이 클래스는 배열을 이용하여 노드들을 관리합니다. 노드의 데이터를 가져오거나 삽입하기 위해 인덱스를 사용하며, 첫 번째 노드를 가리키는 head 속성을 유지합니다.

   class LinkedList:
       def __init__(self):
           self.head = None
   
       def get(self, index):
           if index < 0:
               raise IndexError("Index out of range")
   
           current = self.head
           count = 0
   
           while current:
               if count == index:
                   return current.data
               current = current.next
               count += 1
   
           raise IndexError("Index out of range")
   
       def insert(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
   

3. 연결 리스트 사용하기

   이제 연결 리스트를 생성하고 데이터를 추가해보겠습니다.

   linked_list = LinkedList()
   linked_list.insert(1)
   linked_list.insert(2)
   linked_list.insert(3)
   
   print(linked_list.get(0))  # 1
   print(linked_list.get(1))  # 2
   print(linked_list.get(2))  # 3
   

장단점

배열을 이용한 연결 리스트의 장점은 데이터 저장 및 접근에 O(1) 시간복잡도를 갖는다는 것입니다. 또한, 포인터를 사용하지 않으므로 메모리 사용량도 절약할 수 있습니다.

하지만, 배열의 크기를 제한하기 때문에 제한된 공간만을 사용할 수 있다는 단점이 있으며, 데이터의 삽입 및 삭제 시 배열의 재배열 과정이 필요하므로 O(n) 시간복잡도를 가질 수 있습니다.

참고 문서:

• Linked List - Wikipedia