Linked List 파이썬으로 구현하기

• 노드

class Node:
    def __init__(self, value):
        self.value = value #데이터
        self.next = None #포인터

• SinglyLinkedList 클래스

class SinglyLinkedList:
    def __init__(self):
        self.head = None 
        self.tail = None
        
    def find(self, value):
        curr_node = self.head
        while curr_node.value != value:
            curr_node = curr_node.next
        return curr_node
    
    def append(self, new_value):
        new_node = Node(new_value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
    
    def insert(self, node, new_value):
        new_node = Node(new_value)
        new_node.next = node.next
        node.next = new_node
        
    def remove(self, value):
        prev_node = self.head
        while prev_node.next.value != value:
            prev_node = prev_node.next
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next
            
    def display(self):
        curr_node = self.head
        display_string = "["
        while curr_node is not None:
            display_string += f"{curr_node.value}, "
            curr_node = curr_node.next
        display_string = display_string[0:len(display_string)-2]
        display_string += "]"
        print(display_string)

이제 이걸 하나하나 뜯어보면,

• 초기화

def __init__(self):
    self.head = None #시작 노드
    self.tail = None #끝 노드

SinglyLinkedList는 그 자체로는 노드를 가지고 있지 않으며 단순히 연결 관계만 표현한 자료구조이다

• 찾기

def find(self, value):
    curr_node = self.head
    while curr_node.value != value:
        curr_node = curr_node.next
    return curr_node

- 현재 노드의 값과 비교하여 다를 경우 다음 노드로 이동

• 맨 끝에 요소 추가

def append(self, new_value):
    new_node = Node(new_value)
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node

- 링크드리스트에 노드가 존재하지 않으면 새 노드를 추가하고
- 그게 아니면 맨 끝에 새 노드 추가

• 중간에 요소 삽입

    def insert(self, node, new_value):
        new_node = Node(new_value)
        new_node.next = node.next
        node.next = new_node

- 해당 노드(node) 다음으로 Node(new_value) 추가하기

• 요소 삭제

def remove(self, value):
    prev_node = self.head
    while prev_node.next.value != value:
        prev_node = prev_node.next
    if prev_node.next is not None:
        prev_node.next = prev_node.next.next

- prev_node.next가 찾는 value가 나올 때까지 순회하다가
- 해당 노드가 None이 아니라면 그 다음 노드를 가르킬 수 있도록 함