[자료구조] Linked List - (3) 노드 삽입 (at the end)

2022.06.05 - [자료구조] - [자료구조] Linked List - (2) 간단 개념 구현

[자료구조] Linked List - (2) 간단 개념 구현

 

본 글에서는 위의 글에 이어서 Linked List에 노드를 추가하는 방법을 다룸. 노드를 추가하는 방법이 크게 2가지가 있음.

(1) 새로운 노드를 Linked List 맨 앞에 추가
(2) 새로운 노드를 Linked List 맨 뒤에 추가 (본 글에서 다룸)

1) LinkedList 클래스를 정의

• 클래스의 instance 변수로 head와 tail이 있고 모두 None값으로 초기화

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

LinkedList의 초기 상태

 

head가 None을 가리키면, LinkedList에 아직 Node가 하나도 없는 상태.

2) 빈 Linked List에 새로운 node 추가

node가 새롭게 추가되면 head가 새로 추가된 node를 가리킴.

총 1개의 node만 있으므로 tail로 새로 추가된 node를 가리킴.

new_node = Node(1) # 새로운 노드 추가

if self.head is None: # head가 None을 가리키면,
    self.head = new_node
    self.tail = new_node

Linked List에 노드가 하나도 없는 상황에서 노드가 추가되는 과정

3) Node가 있는 Linked List에 새로운 node 추가

여기에 다시 새로운 node를 추가.

new_node = Node(2)

새로운 노드 추가

Linked List로 연결되기 위해서는 head와 tail이 가리키는 노드의 next가 새로운 노드를 가리켜야함. 

self.tail.next = new_node

기존의 노드의 next가 새로운 노드를 가리킴

그리고 tail은 새로 추가된 노드를 가리켜야함. 

self.tail = new_node

tail이 참조하는 노드 업데이트

마지막으로 새로운 노드 하나 더 추가.

new_node = Node(3)

세번째 노드 추가

 

tail이 가리키는 노드의 next가 새로운 노드를 가리켜야함.

self.tail.next = new_node

두번재 node의 next가 새로운 노드를 가리킴

 

마지막으로 tail이 새로 추가된 노드를 가리키도록 업데이트

self.tail = new_node

 

위의 과정을 'append' 라는 이름의 method로 변환하면 아래와 같음.

# linked list 끝에 노드 추가
def append(self, new_data):

    new_node = Node(new_data)

    if self.head is None:# 기존에 node가 없는 경우
        self.head = new_node
    else: # 기존에 node가 있는 경우
        self.tail.next = new_node
    
    self.tail = new_node

 

• self.tail = new_node는 if-else 문에서 공통이므로 바깥으로 빼줌

최종코드

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # linked list 끝에 노드 추가
    def append(self, new_data):
        new_node = Node(new_data)

        if self.head is None:# 기존에 node가 없는 경우
            self.head = new_node
        else: # 기존에 node가 있는 경우
            self.tail.next = new_node
    
        self.tail = new_node

 

참고)

1. Linked List 클래스에서 tail 이라는 인스턴스 변수를 사용함으로써, append 메소드의 time complexity가 O(1)을 유지한다. 변수를 사용하지 않는 경우는 head 노드부터 끝 노드까지 loop를 이용해 찾은 후 node를 추가해야하기 때문에 time complexity가 O(n)이 된다. (n은 노드 수)