삶은 여행

연결리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.

컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상자료형(ADT) 구현의 기반이 된다.

동적으로 새로운 노드를 삽입/삭제하기 간편하다.

연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다.

​

한 개의 노드는 실제 데이터값을 저장하는 data와 그 다음의 노드를 연결하는 next로 나뉘어져 있다.

​

파이썬으로 구현해보자.

append는 연결 리스트에 노드를 새로 추가하는데, 연결리스트의 맨 마지막 위치에 노드를 추가하는 함수로 설정한다.

맨 뒤까지 즉 node.next == None 일 때까지 쭉 진행한 다음에 새 노드를 삽입해야한다.

find_data는 내가 찾고 싶은 값을 입력해서 그 값이 연결리스트 안에 있는지 없는지 확인하는 함수로 사용할 것이다.

딕셔너리로 치면 in 정도..?

찾고 싶은 값이 내부에 없으면 -1을 반환한다.

Delete_with_index는 내가 원하는 index에 있는 값을 삭제하는 함수이다.

0->1->2->3->4 의 연결리스트가 있을 때, delete_with_index(3)을 하면 3번 인덱스 위치에있는 3이 삭제되는 것.

노드를 지운다고는 하지만 del 등의 기능을 사용하는 건 아니고,

그 노드의 전 노드와 후 노드를 연결하는 식의 작업이기 때문에 prev_node 변수를 통해 이 전 노드를 기억하고

next_node 변수를 통해 이 후의 노드와 연결해준다.

​

delete_with_index와 마찬가지로 새로 한 노드를 추가한 뒤에 여태까지 있던 prev, next와 손잡게 해주는 방식인데,

원래 연결리스트에 아무것도 없는 상태에서 추가하는 경우를 고려하여 조건분기가 조금 더 복잡해져있다.

연결리스트 내부를 확인할 수 있는 show_all 함수를 위와같이 만들고

실행해주면 다음과 같은 결과를 확인해볼 수 있다.

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

class singly_linked_list:
    def __init__(self):
        self.head = None
        self.count = 0

    def append(self, node):
        if self.head == None:
            self.head = node
        else:
            temp = self.head
            while temp.next != None:
                temp = temp.next
            temp.next = node
    
    def find_data(self, num):
        temp = self.head
        #temp는 None이거나 node 둘 중 하나. temp.data와 temp.next 사용 가능
        idx = 0
        while temp:
            if temp.data!=num:
                idx += 1
                temp = temp.next
            else:
                return idx
        return -1 #if cannot find, return -1
    
    def show_all(self):
        temp = self.head
        printout = ""
        while temp:
            printout += str(temp.data)
            if temp.next:
                printout += "->"
            temp = temp.next
        return printout

    def delete_with_index(self, idx):
        temp = self.head
        i = 0 
        prev_node = None
        next_node = self.head.next
        if idx==0:
            self.head = next_node
        else:
            while i < idx:
                if temp.next:
                    prev_node = temp
                    temp = next_node
                    next_node = next_node.next
                else:
                    break
                i += 1
            if i==idx:
                prev_node.next = next_node
            else: print(-1)

    def insert_with_index(self, idx, node):
        temp = self.head
        i = 0 
        prev_node = None
        if idx==0:
            if self.head:
                # next_node = self.head
                # node.next = next_node
                # return node
                # 원리상으론 삽입이 가능하나, node에 붙이기만 했지 원래 self객체에 반환이 안되는거라 아래로 구현.

                next_node = self.head
                self.head = node
                self.head.next = next_node
            else: 
                self.head = node
        else:
            while i < idx:
                if temp:
                    prev_node = temp
                    temp = temp.next
                else: break
                i += 1
            if i==idx:
                prev_node.next = node
                node.next = temp
            else: print(-1)
        

s = singly_linked_list()
s.append(Node(3))
s.append(Node(2))
s.append(Node(1))
s.append(Node(4))
print(s.show_all())
print(s.find_data(1))
s.delete_with_index(2)
s.insert_with_index(2, Node(5))
s.insert_with_index(8, Node(5))
print(s.show_all())

데크 구조(덱 구조, deque)는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있는 구조인데

이를 구현할 때도 이중연결리스트(Doubly Linked List)로 구현하는 것이 편리하다고 한다.

파이썬에서는 collections 모듈에서 deque라는 이름으로 import하면 바로 사용할 수 있다.