Python 연결 리스트(Linked List)

연결 리스트(Linked List)는 데이터 요소들을 순서대로 저장하는 자료구조다. 

 

 

연결리스트는 위 그림처럼 노드로 이루어져 있다.

각 노는 데이터와 다음 노드를 가리키는 포인터(Pointer)로 이루어져 있다.

이 포인터는 다음 노드의 위치를 가리키므로, 데이터 요소들이 메모리에 연속적으로 저장되지 않아도 된다.

 

앞서 배운 클래스를 통해 파이썬으로 노드와 연결리스트를 구현해보자.

 

class LinkedList:
    def __init__(self):
        self.head = None
        pass
        
    def insert_head(self, data):
        new_node = LinkedList.Node(data, self.head)
        self.head = new_node
        pass    
        
    class Node:
        def __init__(self, data, next):
            self.data = data
            self.next = next
            pass
            
my_list = LinkedList()
my_list.insert_head(1)
my_list.insert_head(2)
my_list.insert_head(3)
my_list.insert_head(4)
my_list.insert_head(5)

node = my_list.head
while node:
    print(node.data, " ")
    node = node.next
    
>> 5 4 3 2 1

 

위 그림과 같은 연결리스트가 생성된다.

연결리스트의 단점으로는 데이터를 순회하기 위해서 사용자가 직접 객체 변수인 next를 참조해야 된다는 것이다.

또한, 1이 담겨있는 노드에 접근하기 위해 next를 4번이나 접근해야 한다.

이러한 단점을 해결하기 위해 인덱싱 기능이 있는 연결리스트를 구현해보자.

class LinkedList:
    class Cursor:
    	def __init__(self, linkedList):
        	self.cursor = 0
        	self.list = linkedList
        	pass

    	def __next__(self): 
            if self.cursor == len(self.list):
                raise StopIteration
            data = self.list.get(self.cursor)
            self.cursor += 1
            return data 

    class Node:
        def __init__(self, data, next):
            self.data = data
            self.next = next
            pass
            
    def __init__(self):
        self.head = None
        self.count = 0 # 리스트에 저장된 원소의 갯수
        pass
        
    def __len__(self):
        return self.count
        
    def __iter__(self):
    	return LinkedList.Cursor(self)
        
    def insert_head(self, data):
        self.head = LinkedList.Node(data, self.head)
        self.count += 1
        pass
        
    def get(self, idx):
        if (self.count == 0) or (idx >= self.count):
            return None
        
        cur_node = self.head
        for _ in range(idx):
            cur_node = cur_node.next
        
        return cur_node.data
        
my_list = LinkedList()
for item in range(5):
    my_list.insert_head(item+1)

cursor = iter(my_list)

while True:
	try:
    	print(next(cur))
    except StopIteration
    	break

print()

for item in my_list:
    print(item, end= " ")

>> 5 4 3 2 1
>> 5 4 3 2 1

 

__iter__ 메서드는 반복자(iterator)를 반환하는 메소드인데, 위 코드에서 Cursor 객체를 반환한다.

반복자 클래스는 기본적으로 __next__ 메서드가 정의되어 있어야 하는데 Cursor 클래스는 __next__ 메서드가 정의되어 있으므로 반복자 역할을 수행할 수 있다.