링크드 리스트 구현

링크드 리스트

구현

노드

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

링크드 리스트에 사용할 노드이다.
노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있다.

링크드 리스트

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

링크드 리스트 선언부로 input으로 node에 들어갈 data 사용하도록 구현했다.

append

    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

링크드 리스트 마지막 노드에 다음 노드를 추가하는 메서드이다.
cur = self.head를 통해 헤드에서부터 while문을 통해 마지막 노드까지 탐색을 한 후 cur.next를 통해 노드를 추가하도록 구현했다.

print_all

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

링크드 리스트의 모든 노드의 데이터를 출력하는 메서드이다.
append 메서드와 같이 헤더부터 마지막 노드를 탐색하면서 각 노드의 데이터를 출력하도록 구현했다.

get_node

    def get_node(self, index):
        node = self.head
        cnt = 0
        while cnt < index:
            node = node.next
            cnt += 1
        return node

링크드 리스트의 입력한 index의 노드를 반환하는 메서드이다. print_all과 다르게 node.data가 아닌 node 자체를 반환하는 로직이며 링크드 리스트의 삽입 및 삭제 메서드에 노드를 가져오는 로직이 필요하기 때문에 구현했다.
헤드에서 탐색을 시작해 while문을 사용하여 index 노드까지 탐색하여 반환하도록 구현했다.

add_node

    def add_node(self, index, data):
        new_node = Node(data)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

링크드 리스트의 index번째에 노드를 삽입하는 메서드이다.
i 번째에 삽입을 한다면

1. get_node 메서드를 사용해 i-1번째 노드 탐색
2. 현재 i번째 노드를 임시 변수에 저장
3. i-1번째 노드의 포인터를 삽입할 노드를 향하게 할당
4. 삽입한 노드의 포인터가 임시 변수의 노드를 향하게 할당

위 과정을 통해 삽입이 동작하도록 구현했으며 첫 번째 노드에 삽입하는 경우는 탐색이 필요없이 헤드 노드 및 포인터만 수정하면 되므로 if문을 사용해 따로 구현했다.

delete_node

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next

링크드 리스트의 index 번째의 노드를 삭제하는 메서드이다.

1. get_node 메서드를 사용해 i-1번째 노드 탐색
2. i-1번째 노드의 포인터를 i+1번째 노드를 가리키도록 설정
   (node.next = node.next.next)

위 과정을 통해 삭제 기능이 동작하도록 구현했으며 add_node 보다 간단한 로직이었다. 마찬가지로 첫 번째 노드를 삭제할 경우 탐색과정이 필요없이 헤드 노드 및 포인터만 수정하면 되므로 if문을 사용해 따로 구현했다.