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

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

본 글에서는 위의 글에 이어서 새로운 노드를 Linked List 맨 앞에 추가하는 방법을 다룸. 

(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로 연결되기 위해서는 새로운 노드의 next가 head가 가리키는 노드를 가리켜야 함

new_node.next = self.head

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

그리고 head는 새로 추가된 노드를 가리켜야함. 

self.head = new_node

head가 참조하는 노드 업데이트

 

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

new_node = Node(3)

세번째 노드 추가

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

new_node.next = self.head

 

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

self.head = new_node

 

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

# linked list 처음에 노드 추가
def push(self, new_data):
    new_node = Node(new_data)

    if self.head is None:
        self.tail = new_node
    else:
        new_node.next = self.head
        
    self.head = new_node

• push 메소드는 항상 처음에 노드를 추가하기 때문에 Time complexity가 항상 O(1)이다.

최종코드

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:
            self.head = new_node
        else:
            self.tail.next = new_node
            
        self.tail = new_node

	# linked list 처음에 노드 추가
    def push(self, new_data):
        new_node = Node(new_data)

        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head
        
        self.head = new_node