[자료구조] LinkedList

LinkedList

대표적으로 C같은 경우 선형 자료구조인 Array가 있다.

그러나 이 배열의 경우는 시작부터 크기를 지정해주어야하고, 새로운 요소를 추가하거나, 배열 안의 요소를 제거할 때 비용(시간)이 많이 든다. 

 

이를 개선하기 위해서 구조체를 만드는데, 이 구조체에는 하나의 요소 값과, 다음 구조체의 정보를 가진다.

이 구조체를 연결하여 만드는 리스트가 바로 LinkedList이다. 

 

LinkedList를 사용함으로써 크기가 유동적인 자료형을 만들 수 있고, 삽입, 제거에 시간이 적게 든다. 

특히 값을 탐색하다가 데이터를 추가, 제거하기에 용이하다.

 

단점으로는 index가 없어 값을 앞에서부터 탐색해야 한다. -> 탐색에 시간이 많이 소요된다.

종류로는 단순(Single), 양방향(Double)이 있다.

 

간단한 Single LinkedList 코드

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

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos <= 0 or pos >self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        curr = self.head
        res = []
        
        while curr is not None:
            res.append(curr.data)
            curr = curr.next
        return res

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        if pos == 1:
            newNode.next = self.head
            self.head = newNode
        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos-1)

            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount+1:
                self.tail = newNode

        self.nodeCount += 1
        return True

    def popAt(self, pos):
        if pos < 1 or pos >= self.nodeCount + 1:
            raise IndexError
        popNode = self.getAt(pos)
        if self.nodeCount == 1:
            self.head = None
            self.tail = None
            
        else:
            if pos == 1:
                self.head = popNode.next
            else:
                prevNode = self.getAt(pos-1)
                if pos == self.nodeCount:
                    self.tail = prevNode
                
                prevNode.next = popNode.next

        self.nodeCount -= 1
        return popNode.data

 

위 코드에서 self.next에 추가로 self.prev등을 넣으면 양방향 리스트가 되며,

insertAt, popAt과 같이 인덱스로 위치를 정하는 것이 아니라 특정 노드 뒤에 삽입하는 방법도 있다.