[자료구조] 연결 리스트를 알아보고 파이썬으로 구현하기

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 

---

연결 리스트(Linked List)

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

 

 연결 리스트는 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형 구현의 기반이 됩니다.

 

 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다는 장점이 있습니다.

 

 연결 리스트는 배열과는 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없습니다. 즉 탐색에는 O(n)이 소요됩니다. 반면, 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추추하는 작업은 O(1)에 가능합니다.

 

---

파이썬으로 연결 리스트 구현하기

 여기서 구현하는 연결 리스트는 단일 연결 리스트(Single Linked List)입니다.

 

# define ListNode class
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = LinsNode(0) # pseudo-head
        
    def get(self, index):
        # if index is invalid
        if index < 0 or index >= self.size:
            return -1
            
        curr = self.head
        
        # index steps needed to move from sentinel node to wanted index
        for _ in range(index + 1):
            curr = curr.next
        return curr.val
        
    # add node at head
    def addAtHead(self, val):
        self.addAtIndex(0, val)
        
    # add node at tail
    def addAtTail(self, val):
        self.addAtIndex(self.size, val)
        
    # add node at index
    def addAtIndex(self, index, val):
        # if index is greater than the length, the node will not be inserted
        if index > self.size:
            return
            
        # if index is negative, the node will be inserted at the head of the list
        if index < 0:
            index = 0
            
        self.size += 1
        
        # find predecessor of the node to be added
        pred = self.head
        for _ in range(index):
            pred = pred.next
            
        # node to be added
        to_add = LinstNode(val)
        # insertion itself
        to_add.next = pred.next
        pred.next = to_add
        
    # delete node at index
    def deleteAtIndex(self, index):
        # if the index is invalid, do nothing
        if index < 0 or index >= self.size:
            return
            
        self.size -= 1
        
        # find predecessor of the node to be deleted
        pred = self.head
        for _ in range(index):
            pred = pred.next
            
        # delete pred.next
        pred.next = pred.next.next