링크드 리스트(Linked list) 3

https://zuha.tistory.com/entry/링크드리스트LinkedList2

링크드 리스트(Linked List) 2

이전 포스팅에 이어서!

 

 

6. 링크드 리스트의 복잡한 기능 2 (특정 노드를 삭제)

다음 코드는 이전 코드에서 delete 메서드만 추가한 것이므로 해당 메서드만 확인하면 됨.

1. head 삭제

2. 마지막 노드 삭제

3. 중간 노드 삭제

 

위의 사진처럼 링크드 리스트 A, B, C가 있다고 가정해보자.

 

1. head 삭제

먼저 A라는 노드 데이터를 삭제한다고 가정해보자. 링크드 리스트는 항상 맨 앞에 있는 노드의 값을 가지고 있어야 한다.

그리고 앞 포스팅에서는 이러한 맨 앞에 있는 노드를 head라고 정의했었다.

A 라는 노드 데이터를 삭제해야 한다면 결과적으로는 head가 그다음 노드인 B로 바뀌어야 한다.

 

2. 마지막 노드 삭제

다음으로 C라는 노드 데이터를 삭제한다고 가정하면

링크드 리스트의 맨 마지막에 있는 노드를 삭제하는 경우가 된다.

이때는 노드를 그냥 없애주면 되긴 하지만 C 노드 앞에 있는 노드 B의 주소 값을 null 또는 None으로 변경해주어야 한다.

 

3. 중간 노드 삭제

중간 노드인 B를 삭제한다고 가정했을 때 앞에 있는 A 노드의 주소값을 C로 바꿔주어야 한다.

---

 

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

class NodeMgmt:
    def __init__(self,data):
        self.head = Node(data)
    
    def add(self,data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
    
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

지난 포스팅에서는 Node 라는 클래스를 만들었고 NodeMgmt라는 클래스를 만들어서 연결 리스트를 관리했다.

리스트에는 데이터를 맨 끝에 추가하는 add라는 함수와 데이터를 순회하는 desc라는 함수가 있었다.

여기에 추가적으로 delete 함수를 구현해보자.

class Mgmt:
    def __init__(self,data):
        self.head = Node(data)
        
    # 특정 데이터를 가진 노드를 삭제하는 함수
    def delete(self,data):
        if self.head = '':
            print("해당 값을 가진 노드가 없습니다.")
            return
            
        if self.head.data == data: # 1.head 삭제
            temp = self.head # 임시 변수로 놓은 이유 -> 객체를 삭제하기 위해서
            self.head = self.head.next # head의 주소가 가지고 있는 것 -> B노드. B를 head로 변경.
            del temp # 객체는 가볍게 del을 입력한 후 해당 객체의 주소를 넣으면 그 객체가 삭제가 된다.
        else:
            node = self.head # head는 현재 data가 아님.
            while node.next: # node.next가 null일 때까지 실행
                if node.next.data == data: # 2. 마지막 노드 삭제, 3. 중간 노드 삭제를 이 부분을 통해 해결할 수 있다.
                    temp = node.next
                    node.next = node.next.next
                    del temp
                else:
                   node = node.next

삭제할 노드 데이터를 빨간색으로 표시

 

테스트를 위해 1개 노드를 만들어보자

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

 

head가 살아있음을 확인

linkedlist1.head

 

head를 지워보기

linkedlist1.delete(0)

 

다음 코드 실행시 아무것도 나오지 않는다는 것은 linkedlist1.head가 정상적으로 삭제되었음을 의미한다.

linkedlist1.head

 

다시 하나의 노드를 만들어봄

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

 

여러 노드를 더 추가해봄

for data in range(1,10):
    likedlist1.add(data)
linkedlist1.desc()

 

노드 중에 데이터 1개를 삭제함

linkedlist1.delete(4)

특정 노드가 삭제되었음을 알 수 있음

linkedlist1.desc()

출력해보면 4가 삭제된 것을 확인할 수 있다.

 

 

---

연습1 : 위 코드에서 노드 데이터가 2인 노드 삭제

linkedlist1.delete(2)
linkedlist1.desc()

 

연습2 : 위 코드에서 노드 데이터가 특정 숫자인 노드를 찾는 함수를 만들고, 테스트해보기

(테스트 : 임의로 1 ~ 9까지 데이터를 링크드 리스트에 넣어보고 데이터 값이 4인 노드의 데이터 값 출력해보기)

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
class NodeMgmt:
    def __init__(self,data):
        self.head = Node(data)
    
    def add(self,data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
            
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
            
    def delete(self,data):
        if self.head == '':
            print('해당 값을 가진 노드가 없습니다.')
            return
        if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
            temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
            self.head = self.head.next # 만약 self.head 객체를 삭제하면 이 코드가 실행되지 않기 때문.
            del temp
        else:
            node = self.head
            while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    pass
                else:
                    node = node.next
                    
                    
    def search_node(self,data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

# 테스트
linkedlist1 = NodeMgmt(0)
for data in range(1,10):
    linkedlist1.add(data)
    
node = linkedlist1.search_node(4)
print(node.data)