[자료구조] Linked List

링크드 리스트

• 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠르다. → O(1) , 배열은 삽입이 어려움

• 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요함

• 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기 까지의 시간이 많이 소요됨 → O(N) , 배열은 인덱스를 통해 접근하므로 O(1) 이 걸린다

시간복잡도

주요 연산

• CreateNode(노드 생성), DestroyNode(노드 소멸)

• AppendNode 노드 추가

• GetNodeAt 노드 탐색

• RemoveNode 노드 제거

• InsertAfter, InsertNewHead 노드 삽입

노드 생성

링크드 리스트의 노드는 자동메모리와 자유 저장소 둘 중 어느 곳에 생성하는게 좋을까?

• 자동 메모리(스택) 영역에 담고 필드를 초기화 하고 생성했다면 함수를 끝에서 NewNode의 주소를 반환한다.

• 하지만 return 을 만나면서 메모리가 사라지기 때문에 사용할 수 없어진다.

• 따라서 자유저장소인 Heap 영역에 저장을 해줘야 한다.

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

노드 탐색 연산

링크드 리스트는 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 하나씩 노드의 갯수만큼 거쳐야만 원하는 요소에 접근할 수 있다 찾고자 하는 요소가 N번째라면 N-1 만큼 노드를 거쳐야한다 → 느림!!

def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index :
            cnt +=1
            node = node.next
        return node

노드 삭제 연산

삭제 하고자는 노드를 찾은 후에 해당 노드의 다음 노드를 이전노드의 NextNode 포인터에 연결해주면 삭제 완료

남아있는 노드는 free를 이용하여 삭제한 노드를 소멸시킴

def removeNode(self,remove):
        if self.head == remove:
            self.head = remove.next
        else:
            current = self.head
            while current != None and current.next != remove:
                current = current.next
            if current != None:
                current.next = remove.next

노드 삽입 연산

이전 노드의 NextNode 포인터가 새 노드를 가르키게 하고 새노드의 NextNode 포인터가 다음 노드를 가르키게 한다.

def insertNode(self, current, data):
        data.next = current.next
        current.next = data