[Python] 연결 리스트(Linked List) 구현하기

노드(Node)

연결 리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 연결 리스트를 구현하기 위해서는 노드(Node)를 먼저 구현해야 한다.

노드(Node) 구현

노드는 데이터와 다음 노드를 가리키는 포인터를 가진다.

class ListNode:
    def __init__(self,val):
    	self.val = val
        self.next = None

노드(Node) 연결

다음 노드를 가리키는 포인터(next)를 통해 다음 노드와 연결할 수 있다.

head_node = ListNode(12)
head_node.next = ListNode(74)
head_node.next.next = ListNode(23)
head_node.next.next.next = ListNode(8)

Head 노드부터 모든 노드 출력

반복문 사용

def printNodes(node:ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val , end= ' ')
        crnt_node = crnt_node.next
        
printNodes(head_node)

재귀 사용

def printNodesRecur(node:ListNode):
    print(node.val, end=' ')
    if node.next is not None:
        printNodesRecur(node.next)
        
printNodesRecur(head_node)

연결 리스트(Linked List)

단순 연결 리스트(Singly Linked List) 구현

단일 연결 리스트(Singly linked list)는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

맨 앞에 노드 삽입(addAtHead): 시간 복잡도 O(1)

def addAtHead(self, val): #O(1)
    node = ListNode(val)
    node.next = self.head
    self.head = node

맨 뒤에 노드 삽입(addBack): 시간 복잡도 O(n)

#but when the list
def addBack(self, val): #O(n)
    node = ListNode(val)
    crnt_node = self.head
    while crnt_node.next:
        crnt_node = crnt_node.next
    crnt_node.next = node

탐색(findNode): 시간 복잡도 O(n)

def findNode(self, val): #O(n)
    crnt_node = self.head
    while crnt_node is not None:
        if crnt_node.val == val:
            return crnt_node
        crnt_node = crnt_node.next
    raise RuntimeError('Node not found')

특정 노드의 뒤에 삽입(addAfter): 시간 복잡도 O(1)

def addAfter(self, node, val): #O(1)
    new_node = ListNode(val)
    new_node.next = node.next
    node.next = new_node

특정 노드의 다음 노드 삭제(deleteAfter): 시간 복잡도 O(1)

def deleteAfter(self, prev_node): #O(1)
    if prev_node.next is not None:
        prev_node.next = prev_node.next.next

전체 코드

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def printNodes(node:ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next

class SLinkedList:
    def __init__(self):
        self.head = None
        
    def addAtHead(self, val): #O(1)
        node = ListNode(val)
        node.next = self.head
        self.head = node

    #but when the list
    def addBack(self, val): #O(n)
        node = ListNode(val)
        crnt_node = self.head
        while crnt_node.next:
            crnt_node = crnt_node.next
        crnt_node.next = node

    def findNode(self, val): #O(n)
        crnt_node = self.head
        while crnt_node is not None:
            if crnt_node.val == val:
                return crnt_node
            crnt_node = crnt_node.next
        raise RuntimeError('Node not found')

    def addAfter(self, node, val): #O(1)
        new_node = ListNode(val)
        new_node.next = node.next
        node.next = new_node

    def deleteAfter(self, prev_node): #O(1)
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next

📗 참고

유튜브, 코드없는 프로그래밍, 코딩테스트 LinkedList

저작자표시

hyeinisfree