파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제 방법)

이번에는 단순 연결리스트에서 노드를 삭제하는 방법을 알아보겠습니다. 

 

노드를 삭제할 때는 맨 앞 노드를 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제로 경우를 나눌 수 있습니다.

 

그렇다면 삭제할 노드가 맨 앞인지, 맨 뒤인지, 중간인지 판단할 수 있어야 합니다.

 

만약 잘 판단했다고 치고 맨 앞 노드를 삭제하는 경우는 다음과 같습니다.

맨 앞 삭제
reference	head	->	->	->	....
data	a	b	c	d	....

 

i) 맨 앞 노드 삭제 방법 -> head.next가 head가 된다.

맨 앞 삭제
reference		head	->	->	....
data	a	b	c	d	....

그러면 단순 연결리스트는 head 부터 시작하니까 a가 자연스럽게 끊어집니다.

 

방법을 알았으면 코드를 작성해야합니다.

코드를 작성하려면 보다 자세한 동작 과정이 필요합니다.

 

리스트에서 index를 받아 지운 것 처럼 구현하려고 합니다. 맨 앞이니까 0이 들어오겠죠?

그렇다면 여기서의 조건은 index == 0이 됩니다. 

def remove(self, index):
    """연결리스트의 원하는 노드를 지운다."""

    if index == 0:  # 맨 앞을 의미한다.
        self.head = self.head.next
    self.count -= 1  # 노드를 지웠으니까 개수를 하나 줄여 줍니다.

 

 

그렇다면 맨 뒤 노드를 삭제하는 방법을 알아보겠습니다. 맨 뒤 노드를 지우는 방법은 맨 앞을 지우는 방법과 비슷합니다.

ii) 맨 뒤 노드 지우는 방법

맨 뒤를 특정하는 방법은 넘겨 받은 인덱스 번호가 self.count - 1이면 됩니다. 인덱스 번호와 실제 노드 개수는 1 차이가 있기 때문입니다.

 

그러나 한 가지 문제점이 있습니다. 맨 뒤를 지우고 그 다음 맨 뒤의 이전이 tail 노드가 되면 맨 뒤를 지울 수 있습니다. 단순 순 연결리스트라 리스트의 맨 뒤는 self.tail로 찾을 수 있지만 그 이전을 찾기 위해서는 탐색을 거쳐야 합니다.

 

우리가 찾야야하는 정보는 맨 뒤의 이전을 찾아야 합니다.

 

반복문을 이용하여 tail 이전을 찾을 것인데 얼마나 반복을 해야할까요?

맨 앞 삭제
reference	head	->	->	->	tail
data	a	b	c	d	e

self.head 부터 시작해서 그 다음으로 넘어가는 과정이 반복문 1번 입니다. 그렇다면 이전으로 가기 위해서 a -> b, b -> c, c -> d 총 3번 입니다. 이 과정을 어떠한 길이의 연결리스트에서도 동작되게 하려면 규칙을 찾아야 합니다.

 

연결리스트의 총 노드의 개수는 5개 우리가 tail의 뒤가 누구인지 찾기 위해서 3번의 반복 실행 즉, 5-2번 반복 해야하므로 (self.count - 2)번 반복해야한다는 정보를 알았습니다.

 

코드로 작성해보겠습니다.

def remove(self, index):
    """연결리스트의 원하는 노드를 지운다."""

    if index == 0:  # 맨 앞을 의미한다.
        self.head = self.head.next
    elif index == self.count-1:  # count에서 1을 빼면 맨 뒤를 의미함
        i = self.head  # head 부터 시작해서
        for _ in range(self.count-2):  # -2를 해야 딱 그 전까지 찾기 가능
            i = i.next
        tail_prev_node = i
        self.tail = tail_prev_node
        self.tail.next = None  # 다음이 없어야 하므로 None 값을 넣어줍니다.
    self.count -= 1  # 지웠으니까 노드의 개수도 하나 줄어듬

 

 

마지막입니다. 중간에 있는 노드를 지우는 과정입니다.

중간이 어디있는지 알기 위해서 역시나 탐색의 과정을 거쳐야 합니다.

받은 인덱스 값 만큼 반복을 하면 됩니다.

 

중간을 지우기 위해서 3가지 정보를 알아야합니다. a, b, c 노드를 알아야 하는데 다음과 같이 정의하겠습니다.

지울 노드의 이전을 a노드, 지울 노드를 b노드, 지울 노드의 다음을 c노드라 하겠습니다.

 

최종 목적은 a.next를 c와 연결해야합니다. c에 연결할 정보는 b.next에 들어있습니다. 코드로 알아보겠습니다.

def remove(self, index):
    """연결리스트의 원하는 노드를 지운다."""

    if index == 0:  # 맨 앞을 의미한다.
        self.head = self.head.next
    elif index == self.count-1:  # count에서 1을 빼면 맨 뒤를 의미함
        i = self.head  # head 부터 시작해서
        for _ in range(self.count-2):  # -2를 해야 딱 그 전까지 찾기 가능
            i = i.next
        tail_prev_node = i
        self.tail = tail_prev_node
        self.tail.next = None  # 다음이 없어야 하므로 None 값을 넣어줍니다.
    elif 0 < index < self.count-1:  # 중간 노드를 지울 경우
        i = self.head
        for _ in range(index-1):  # 이전을 찾기 위해서 반복은 index-1번만 합니다.
            i = i.next
        remove_prev_node = i  # 지우는 노드 이전
        remove_node = remove_prev_node.next  # 지우는 노드

        temp = remove_node.next  # 지울 노드의 다음 노드로 갈 정보
        remove_prev_node.next = temp  # 그 정보를 지울 노드의 이전의 다음으로 갈 정보로 준다

    self.count -= 1  # 지웠으니까 노드의 개수도 하나 줄어듬

 

 

이제 전체 소스입니다.

class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드를 가리키는 정보


class LinkedList:
    def __init__(self):
        # 연결리스트를 처음 생성 시 아무것도 없으므로 다음과 같이 초기화 할 수 있다.
        self.head = None
        self.tail = None
        self.count = 0

    def append(self, value):
        """연결리스트 뒤에 추가하는 메소드"""
        new_node = Node(value)  # 공통 특징은 우선 새 노드를 생성한다는 것

        if self.count == 0:  # 연결리스트가 비었을 때
            self.head = new_node  # 새 노드가 head node가 된다.
            self.tail = new_node  # 새 노드가 tail node가 된다.
        else:  # 연결리스트가 안 비어있을 때
            self.tail.next = new_node  # tail node의 다음이 새 노드를 가리킨다
            self.tail = new_node  # 새 노드는 tail node가 된다
        self.count += 1  # 노드가 추가 되었으니까 갯수를 하나 올린다.

    def insert(self, index, value):
        """연결리스트의 원하는 위치에 삽입하는 메소드"""
        new_node = Node(value)

        if 0 <= index <= self.count:  # 연결리스트의 원하는 인덱스 범위에 있나?
            if index == 0:  # 인덱스가 0이란 맨 앞에 넣고 싶다는 뜻
                head_node = self.head  # head를 잠시 저장
                self.head = new_node  # head 노드를 새 노드로 교체
                self.head.next = head_node  # head(신)의 다음을 아까 잠깐 저장한 head(구)를 가리킴
            elif index == self.count:  # 이 말은 만약 tail 노드라면?
                self.tail.next = new_node  # tail의 다음을 새 노드를 가리킴
                self.tail = new_node  # tail을 새 노드로 교체
            else:  # 나머지 경우는 일반적인 중간에 넣는 것임
                i = self.head
                for _ in range(index - 1):
                    i = i.next
                prev_node = i  # 삽입할 위치의 이전 노드
                new_node.next = prev_node.next  # 새 노드의 다음은 이전 노드의 다음을 연결해준다.
                prev_node.next = new_node  # 이전 노드의 다음은 새 노드를 연결한다.
            self.count += 1  # 노드를 삽입했으니까 1 올림
        else:  # 범위에 없으면 인덱스를 잘못 입력했다고 출력해줄까?
            print("인덱스를 잘못 입력했습니다.")

    def remove(self, index):
        """연결리스트의 원하는 노드를 지운다."""

        if index == 0:  # 맨 앞을 의미한다.
            self.head = self.head.next
        elif index == self.count-1:  # count에서 1을 빼면 맨 뒤를 의미함
            i = self.head  # head 부터 시작해서
            for _ in range(self.count-2):  # -2를 해야 딱 그 전까지 찾기 가능
                i = i.next
            tail_prev_node = i
            self.tail = tail_prev_node
            self.tail.next = None  # 다음이 없어야 하므로 None 값을 넣어줍니다.
        elif 0 < index < self.count-1:  # 중간 노드를 지울 경우
            i = self.head
            for _ in range(index-1):  # 이전을 찾기 위해서 반복은 index-1번만 합니다.
                i = i.next
            remove_prev_node = i  # 지우는 노드 이전
            remove_node = remove_prev_node.next  # 지우는 노드

            temp = remove_node.next  # 지울 노드의 다음 노드로 갈 정보
            remove_prev_node.next = temp  # 그 정보를 지울 노드의 이전의 다음으로 갈 정보로 준다

        self.count -= 1  # 지웠으니까 노드의 개수도 하나 줄어듬

    def __str__(self):
        """자동으로 출력해주는 메소드 사용법은 인스턴스를 출력시키면됩니다."""
        i = self.head
        result = ""
        while True:
            if i.next is None:
                result += str(i.data)
                break
            else:
                result += str(i.data) + " -> "
            i = i.next
        return result


# 테스트 코드
s = LinkedList()
for i in range(1, 11):
    s.append(i)

print(s)  # 생성한 인스턴스를 출력하면 __str__이 동작합니다.

# 중간에 넣기
s.insert(5, 777)
print(s)

# 맨 앞에 넣기
s.insert(0, "aaa")
print(s)
print(s.head.data)  # head가 바뀌었나 확인

# 맨 뒤에 넣기
s.insert(12, "end")
print(s)
print(s.tail.data)  # tail이 바뀌었나 확인

# 이제 삭제해 보자
# 맨 앞 노드 지우기
s.remove(0)
print(s)
print(s.head.data)  # head가 바뀌었나 확인

# 맨 뒤 노드 지우기
print(s.count)  # 노드 개수 확인
s.remove(11)  # 맨 뒤의 인덱스는 13 - 1
print(s)
print(s.tail.data)  # tail이 바뀌었나 확인

# 중간 노드 지우기
print(s.count)  # 노드 개수 확인
print(s)  # 지울 노드 확인 -> 777 지울거임
s.remove(5)
print(s)  # 지운거 확인
print(s.count)  # 지운 후 노드 개수 확인