링크드 리스트 1: 정의, Python으로 구현하기

링크드 리스트는 노드 객체들로 구성되어 있으며, 노드는 data 속성과 next 속성으로 구성됨

data에는 저장하고 싶은 정보를, next에는 다음 노드에 대한 레퍼런스

배열과 달리 노드 객체들은 연속적으로 저장되어 있지 않고 여기저기 흩어져 있으나

각 노드들은 다음 노드에 대한 레퍼런스를 가지고 있기 때문에,

첫번째 노드(= head node)만 있으면 데이터를 순서대로 연결할 수 있다. 

 

 

링크드 리스트 구현하기 - 1

우선 링크드 리스트를 구성하기 위한 Node 클래스를 만든다.

class Node:

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스

 

각 노드에는 data와 next 속성을 지정해준다.

# 데이터 2, 3, 5, 7, 11을 담는 노드들 생성
head_node = Node(2)
node1 = Node(3)
node2 = Node(5)
node3 = Node(7)
tail_node = Node(11)

# 노드들을 연결
head_node.next = node1
node1.next = node2
node2.next = node3
node3.next = tail_node

 

그리고 데이터 2, 3, 5, 7, 11을 담는 노드들을 생성하고, 

2를 담는 노드를 헤드 노드로 지정해주고, 각 노드들을 연결해준다.

 

링크드 리스트를 출력하기 위해서는 iterator라는 객체를 사용한다.

# 노드 순서대로 출력
iterator = head_node

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next

 

이렇게 되면 각 노드의 데이터가 출력되고 다음 노드로 넘어가게 되며

tail_node의 경우 next 속성을 지정해주지 않아 None이 되므로 반복문이 끝나게 된다.

 

링크드 리스트 구현하기 - 2

링크드 리스트를 더 체계적으로 구현하기 위해, LinkedList 클래스를 만들어본다.

class LinkedList:
    """ 링크드 리스트 클래스"""
    def __init__(self):
        self.head = None
        self.tail = None

우선 init 메서드를 사용하여 linked list의 head, tail 속성을 추가해준다.

 

그리고 링크드 리스트에 노드를 추가하는 append 함수를 작성한다.

 def append(self, data):
        """링크드 리스트 추가 연산 메서드"""
        new_node = Node(data)

        if self.head == None:
            self.head = new_node
            self.tail = new_node

        else:
            # 기존 tail node와 new node를 연결
            self.tail.next = new_node
            self.tail = new_node

링크드 리스트에 노드를 추가하기 위해 우선 new_node 객체를 만들어준다.

만약 링크드 리스트가 비어 있다면 new_node가 head이자 tail이 될 것이므로

self.head와 self.tail을 모두 new_node로 지정한다.

 

만약 링크드 리스트에 객체가 있다면 기존 tail node에 new_node를 연결해주어야 한다.

따라서 self.tail.next에 new_node를 지정해주고, self.tail을 new_node로 옮겨준다.

 

# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

 

링크드 리스트에 데이터를 입력하고, 

아까와 같은 방법으로 출력하면 잘 출력된다.

iterator = my_list.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next