💡 노드를 연결해서 만든 리스트
💡 장단점
장점
단점
복잡도 | |
---|---|
삽입 | O(1) |
추가 | O(1) |
삭제 | O(1) |
탐색 | O(n) |
링크드 리스트의 노드는 자동메모리(스택)와 자유 저장소(힙) 둘 중 어느 곳에 생성하는게 좋을까?
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