파이썬 | 링크드 리스트 구현하기 (Constructor, Append, Pop)

파이썬 | 링크드 리스트 구현하기 (Constructor, Append, Pop) - 2

올리브한입 2024. 9. 23. 20:30

전 글에서 링크드 리스트 구조에 대해서 공부했다면, 이제 파이썬으로 링크드 리스트를 구현하는 것을 도전해 봅시다.

링크드 리스트

링크드 리스트를 구현할 때, 노드를 반복해서 생성하는 작업을 효율적으로 처리할 필요가 있습니다. 각 노드는 데이터를 저장하고, 다음 노드를 가리키는 포인터를 포함하고 있기 때문에, 새로운 노드를 만들 때마다 이 구조를 동일하게 반복하게 되죠. 이를 반복하지 않도록 Node 클래스를 따로 만들어 관리할 수 있습니다.

class LinkedList:
    def __init__(self, value):
        # create new Node
    
    def append(self, value):
        # create new Node
        # add Node to end

    def prepend(self, value):
        # create new Node
        # add Node to beginning

    def insert(self, index, value):
        # create new Node
        # insert node

여기서 노드를 추가하는 작업이 반복되면서, 각 메서드에서 같은 작업을 여러 번 하게 되죠. 이를 개선하기 위해 Node 클래스를 따로 정의해서, 중복되는 부분을 없애고 효율적으로 코드를 관리할 수 있습니다.

Node 클래스

class Node:
    def __init__(self, value):
        self.value = value  # 노드가 저장할 값
        self.next = None    # 다음 노드를 가리키는 포인터, 기본값은 None

Node 클래스는 각 노드를 생성하는 역할만 담당합니다. 즉, 링크드 리스트에서 필요한 노드를 만들 때마다 같은 방식으로 데이터를 저장하고, 다음 노드로 연결하는 구조를 재사용할 수 있습니다.

여기서 __init__ 메서드는 Node 클래스의 컨스트럭터입니다. 객체가 생성될 때, 사용자가 넘긴 value 값을 받아 self.value에 할당하고, self.next는 기본적으로 None으로 초기화됩니다. 이는 새로 생성된 노드가 다른 노드와 연결되지 않았다는 것을 의미합니다.

LinkedList 클래스

컨스트럭터

class LinkedList:
    def __init__(self, value):
        new_node = Node(value)  # 첫 번째 노드 생성
        self.head = new_node    # 리스트의 시작점(head)을 첫 번째 노드로 설정
        self.tail = new_node    # tail도 동일하게 첫 번째 노드를 가리킴
        self.length = 1         # 리스트의 길이는 1로 시작

여기서 head는 리스트의 첫 번째 노드를 가리키고, tail은 리스트의 마지막 노드를 가리킵니다. 이 경우, 처음에는 노드가 하나뿐이므로 head와 tail이 동일한 노드를 가리키게 됩니다. 리스트의 길이(length)는 1로 설정됩니다. 이렇게 하면, 링크드 리스트는 Node 클래스를 사용해 노드를 생성하고, 그 노드를 통해 리스트를 초기화할 수 있게 됩니다. 예시를 들어 보겠습니다.

my_linked_list = LinkedList(4)

4를 Node 클래스로 패스해 새로운 노드를 생성합니다.

head와 tail을 새 노드로 설정합니다.

이때 리스트의 길이는 1로 설정됩니다.

Append

append 메서드는 링크드 리스트의 끝에 새로운 노드를 추가하는 기능을 수행합니다. 이 메서드를 구현할 때에는 링크드 리스트의 끝에 새로운 노드를 추가하는 경우와 리스트가 비어 있는 경우를 고려해야 합니다.

def append(self, value):
    # 새로운 노드를 생성합니다.
    new_node = Node(value)

    # 리스트가 비어 있는지 확인합니다.
    if self.head is None:
        # 리스트가 비어 있다면, 새로운 노드를 head와 tail로 설정합니다.
        self.head = new_node
        self.tail = new_node
    else:
        # 리스트가 비어 있지 않다면, tail의 next를 새로운 노드로 설정합니다.
        self.tail.next = new_node
        # tail을 새로운 노드로 업데이트합니다.
        self.tail = new_node
    
    # 리스트의 길이를 증가시킵니다.
    self.length += 1
    return True

이와 같은 경우가 리스트가 비어 있는 경우입니다. 이때, 우리는 새로 생성한 노드를 헤드와 테일로 설정해야 합니다.

class Node:  # 새로운 노드를 생성하는 클래스
    def __init__(self, value):
        self.value = value  # 노드가 저장할 값
        self.next = None    # 다음 노드를 가리키는 포인터

class LinkedList:  # 링크드 리스트 클래스
    def __init__(self, value):
        new_node = Node(value)  # 새로운 노드 생성
        self.head = new_node     # 리스트의 헤드(첫 번째 노드)
        self.tail = new_node     # 리스트의 테일(마지막 노드)
        self.length = 1          # 리스트의 길이

    def append(self, value):
        new_node = Node(value)  # 새로운 노드 생성
        if self.head is None:   # 리스트가 비어 있는 경우
            self.head = new_node  # 헤드와 테일을 새로운 노드로 설정
            self.tail = new_node
        else:  # 리스트에 노드가 있는 경우
        	#print(self.tail.value) # 1 출력
            #print(self.tail.next) # None 출력
            self.tail.next = new_node  # 기존 테일의 next를 새로운 노드로 설정
            self.tail = new_node        # 테일을 새로운 노드로 업데이트
        self.length += 1  # 리스트의 길이 증가
        return True  # 성공적으로 추가됨을 나타냄

# 링크드 리스트 생성 및 노드 추가
my_linked_list = LinkedList(1)  # 첫 번째 노드로 1을 추가
my_linked_list.append(2)         # 두 번째 노드로 2를 추가

새로운 노드 1을 생성 후 헤드와 테일을 새 노드로 설정합니다.

append 할 새로운 노드가 생성됩니다.

기존 테일 (1)의 다음 노드를 새로운 노드(2)로 설정합니다.

테일을 업데이트 합니다.

리스트의 길이는 2로 업데이트 됩니다.

Pop

링크드 리스트에서 pop 메서드는 리스트의 마지막 노드를 제거하고, 그 노드의 값을 반환하는 기능을 합니다. 이 메서드를 구현할 때에는 링크드 리스트의 끝에 새로운 노드를 제거하는 경우, 리스트가 비어 있는 경우, 그리고 리스트에 노드가 하나만 있는 경우를 고려해야 합니다.

def pop(self):
    # 리스트가 비어 있는 경우
    if self.length == 0:
        return None
    
    # 현재 노드와 이전 노드를 초기화
    temp = self.head
    pre = self.head

    # 리스트의 끝까지 탐색
    while temp.next: 
        pre = temp 
        temp = temp.next

    # 테일을 이전 노드로 업데이트하고 마지막 노드를 제거
    self.tail = pre
    self.tail.next = None

    # 리스트의 길이 감소
    self.length -= 1

    # 리스트가 비어 있으면 헤드와 테일을 None으로 설정
    if self.length == 0:
        self.head = None
        self.tail = None

    # 제거된 노드의 값을 반환
    return temp