[자료구조] Linked List - (6) 노드 삭제

2022.05.25 - [자료구조] - [자료구조] Linked List - (1) 개념

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

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

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

2022.06.12 - [자료구조] - [자료구조] Linked List - (5) 데이터 조회

본 글에서는 Linked List에서 노드 삭제에 대해 다룸. cur이라는 변수를 이용하여 head가 가리키는 노드부터 삭제할 노드를 찾음.

노드 삭제에 대해서 크게 3가지 경우로 나눠서 생각

1) Linked list가 비어있는 경우 : 메소드 바로 종료

cur = self.head

if cur is None:
	return

Linked List가 비어있는 상태

2) head가 가리키는 노드의 값이 삭제하고자하는 값인 경우 (아래 그림에서 data 변수가 3인 경우)

cur = self.head

 

head가 가리키는 노드를 삭제하는 경우

head는 현재 가리키는 노드의 next가 가리키는 노드를 참조해야 함. 그리고 cur에는 None 할당

if cur.data == data: # 첫 노드 삭제
    self.head = cur.next
    cur = None
    return

head가 가리키는 노드 업데이트

3) head가 가리키는 노드가 아닌 다른 노드를 삭제하는 경우 (data에 2가 담긴 노드를 삭제한다고 가정)

cur = self.head

prev 변수를 도입하여 cur이 가리키는 노드를 참조하고, cur 변수는 현재 가리키는 노드의 next가 가리키는 노드 참조.

prev = cur
cur = cur.next

그리고 cur 변수가 가리키는 노드의 data가 삭제할 데이터인지 확인하는 과정을 반복하고 맞으면 반복과정을 종료

while True:
    prev = cur
    cur = cur.next
        
    if cur.data == data:
        break

 

Linked List가 끊기지 않기 위해서는 prev가 가리키는 노드의 next가 cur노드가 가리키는 노드의 next가 가리키는 노드를 참조해야 함 (아래 그림에서 빨간선)

prev.next = cur.next

data에 3이 담긴 노드의 next가 data에 1이 담긴 노드를 가리킴

 

위 3가지 경우가 포함된 delete 메소드는 아래와 같음

    def delete(self, data): # data가 포함된 노드를 linked list에서 삭제
        cur = self.head
        
        if cur == None: # Linked List가 비어있는 경우
            return 

        if cur.data == data: # 첫 노드 삭제
            self.head = cur.next
            cur = None
            return

        while True:
            prev = cur
            cur = cur.next
        
            if cur.data == data: # 중간 노드 삭제 
                break
        
        prev.next = cur.next
        cur = None

전체 코드

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

    def delete_all(self):
        while self.head is not None:
            cur = self.head
            self.head = self.head.next
            cur = None

    # data가 포함된 노드를 linked list에서 삭제
    def delete(self, data):
        cur = self.head
        
        if cur == None: # Linked List가 비어있는 경우
            return 

        if cur.data == data: # 첫 노드 삭제
            self.head = cur.next
            cur = None
            return

        while True:
            prev = cur
            cur = cur.next
        
            if cur.data == data: # 중간 노드 삭제
                break
        
        prev.next = cur.next
        cur = None

    def print(self):
        cur = self.head

        while cur:
            print(cur.data, end=" ")
            cur = cur.next
        print()

if __name__ == "__main__":
    linked_list = LinkedList()
    linked_list.print() # 출력 없음
    linked_list.push(1)
    linked_list.print() # 1
    linked_list.push(2)
    linked_list.print() # 2 1
    linked_list.push(3)
    linked_list.print() # 3 2 1

    linked_list.delete(2)
    linked_list.print() # 3 1