![[자료구조] Doubly Linked List](https://image.inblog.dev?url=https%3A%2F%2Finblog.ai%2Fapi%2Fog%3Ftitle%3D%255B%25EC%259E%2590%25EB%25A3%258C%25EA%25B5%25AC%25EC%25A1%25B0%255D%2520Doubly%2520Linked%2520List%26logoUrl%3Dhttps%253A%252F%252Finblog.ai%252Finblog_logo.png%26blogTitle%3D%25EB%25B0%25B1%25EC%2597%2594%25EB%2593%259C%25EB%25B8%2594%25EB%25A1%259C%25EA%25B7%25B8-dohyeong&w=2048&q=75)
Contents
주요 연산링크드 리스트의 탐색 기능을 개선한 자료구조
링크드 리스트는 헤더에서 테일 방향으로만 탐색이 가능하지만, 더블 링크드 리스트에서는 양방향으로 탐색이 가능하다.
![notion image](https://image.inblog.dev?url=https%3A%2F%2Fwww.notion.so%2Fimage%2Fhttps%253A%252F%252Fs3-us-west-2.amazonaws.com%252Fsecure.notion-static.com%252Fbb24d2fd-40d7-4908-95ce-92a5b0caba9f%252FUntitled.png%3Ftable%3Dblock%26id%3Dc201369b-da41-4eb3-b06a-9ddd440775bd%26cache%3Dv2&w=2048&q=75)
시간복잡도
ㅤ | 복잡도 |
삽입 | O(1) |
삭제 | O(1) |
추가 | O(1) |
탐색 | O(N) |
주요 연산
- CreateNode(노드 생성), DestroyNode(노드 소멸)
- AppendNode 노드 추가
- GetNodeAt 노드 탐색
- RemoveNode 노드 제거
- InsertAfter 노드 삽입
노드생성
링크드 리스트 노드 생성과 비교하면 양방향 노드를 위한 prev 추가됨
class Node: def __init__(self,data=0, next=None, prev =None): self.data = data self.next = next self.prev = prev
노드 추가
새로운 테일의 prev 가 기존 테일을 가르키도록 해야한다.
def append(self, newNode): if self.head == None: self.head = newNode else: tail = self.head while tail.next != None: tail = tail.next tail.next = newNode newNode.prev = tail
노드 탐색
링크드 리스트와 같은 노드 탐색 → 역시 느림
def get_node(self, index): cnt = 0 node = self.head while cnt < index : cnt +=1 node = node.next return node
노드 제거
def removeNode(self, removeNode): if self.head == removeNode: self.head = removeNode.next if(self.head != None): self.head.prev = None removeNode.prev = None removeNode.next = None else: temp = removeNode if removeNode.prev != None: removeNode.prev.next = temp.next if removeNode.next != None: removeNode.next.prev = temp.prev removeNode.prev = None removeNode.next = None
노드 삽입
노드 삽입
def insertAfter(self, current, newNode): newNode.next = current.next newNode.prev = current if current.next != None: current.next.prev = newNode current.next = newNode # 노드 추가시 마지막 Tail 인 경우 # else: # current.next = newNode
Share article