문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업

Linked List

Assignment and Equivalence

x 리스트의 값이 변경되면 y, z 리스트의 값도 함께 변경됨
references 참조를 하고 있기 때문에
== : checks the equivalence of two referenced values
is : checks the equivalence of two referenced obj ID

Singly linked list

노드구성 - next node 를 가리키는 변수 - value 를 가지고 있는 변수
Head, Tail - Head: 리스트의 항상 첫번째 가리킴 - Tail: 리스트의 항상 마지막을 가리킴 - singly linked list 에는 기본 구조에는 포함이 되지 않으나, search, delete 등에서는 사용
코드

class Node:
    next_node = None
    prev_node = ''
    value = ''
    is_head = False
    is_tail = False

    def __init__(self, value = '', next_node = None, is_head = False, is_tail = False):
        self.next_node = next_node
        self.value = value
        self.is_head = is_head
        self.is_tail = is_tail
    def get_value(self):
        return self.value
    def set_value(self, value):
        self.value = value
    def get_next(self):
        return self.node_next
    def set_next(self, next_node):
        self.next_node = next_node
    def is_head(self):
        return self.is_head
    def is_tail(self):
        return self.is_tail

node1 = Node(value='a')
node_head = Node(is_head=True)
node_tail = Node(is_tail=True, next_node=node1)

Search

이전 Array 와 동일하게 모든 리스트를 다 탐색하면서 찾고싶은 Value 를 찾아야함

Insert

Array 의 경우 새로운 값을 추가하기 위해선 새로운 Array 가 필요했음
그러나 Linked list 는 아래 3단계를 통해서 새로운 값을 추가 - 1) 새로운 Node 를 생성 - 2) Node_prev.next = Node_new - 3) Node_new.next = Node_next 로 변경

Delete

Node_prev.next = Node_next 로 변경

코드

class SinglyLinkedList:
    node_head = ''
    node_tail = ''
    size = 0 

    def __init__(self):
        self.node_tail = Node(is_tail=True)
        self.node_head = Node(is_head=True, next_node=self.node_tail)

    def insert_node(self, value, index):
        new_node = Node(value = value)
        prev_node = self.get(index - 1)
        next_node = prev_node.get_next()
        prev_node.set_next(new_node)
        new_node.set_next(next_node)
        self.size += 1

    def remove_node(self, index_to_remove):
        prev_node = self.get(index_to_remove - 1)
        node_to_remove = prev_node.get_next()
        next_node = node_to_remove.get_next()
        prev_node.set_next(next_node)
        self.size -= 1

    def get(self, index):
        result_node = self.node_head
        for i in range(index + 1):
            result_node = result_node.get_next()
        return result_node

    def get_size(self):
        return self.size

    def print_status(self):
        current_node = self.node_head
        while current_node.get_next().is_tail == False:
            current_node = current_node.get_next()
            print(f'{current_node.get_value()} > ', end = "")


linked_list = SinglyLinkedList()
index = 0
for value in range(ord('a'), ord('f') + 1):
    if chr(value) != 'c':
        linked_list.insert_node(chr(value), index)
        index += 1

linked_list.print_status()
>> a > b > d > e > f >

linked_list.insert_node('c', 2)
linked_list.print_status()
>> a > b > c > d > e > f >

linked_list.remove_node(3)
linked_list.print_status()
>> a > b > c > e > f >