링크드 리스트
노드를 연결해서 만든 리스트
![notion image](https://inblog.ai/_next/image?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fce52ece1-6a82-47c1-a69d-ca46984c1a1f%252FUntitled.png%3Ftable%3Dblock%26id%3De995be3a-c38e-4f5f-bb8e-11cf079cecdb%26cache%3Dv2&w=3840&q=75)
장단점
장점
- 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠르다. → O(1) , 배열은 삽입이 어려움
단점
- 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요함
- 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기 까지의 시간이 많이 소요됨 → O(N) , 배열은 인덱스를 통해 접근하므로 O(1) 이 걸린다
시간복잡도
삽입 | O(1) |
추가 | O(1) |
삭제 | O(1) |
탐색 | O(n) |
주요 연산
- 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
Share article