-
[자료구조/Data Structure] 파이썬으로 이중 연결 리스트(Double Linked List) 자료구조 알아보기Data Structure/List 2021. 6. 17. 22:26
이중 연결 리스트를 쉽게 이해하기 위해서는 기본 연결 리스트를 선행하는 것이 좋다.(아래 글 참고)
2021.06.05 - [Data Structure/List] - [자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기
이중 연결 리스트의 구조
이중 연결 리스트는 그림과 같이 노드가 앞, 뒤 양방향으로 연결돼있는 구조다.
첫 번째 노드는 head가 마지막 노드는 tail이 가르키고 있으며 자연스럽게 head의 prev와 tail의 next는 None이 된다.
연결 리스트와 비교 했을시 이중 연결 리스트의 장점 및 단점
장점
- 양방향 검색이 가능하다.
- 양방향 삽입이 가능하다.
- 양방향 삭제가 가능하다.
단점
- 구현이 비교적 복잡하다.
- node가 변수를 하나 더 차지하므로 메모리를 더 사용한다.
이중 연결 리스트의 함수
- insert(data) : data를 가진 node를 리스트 마지막에 삽입
- desc() : head부터 순차적으로 node의 data를 출력
- searchFromHead(data) : data를 가진 node가 head로부터 몇 번째 node인지 출력 data가 없을 시 'not found'를 출력
- searchFromTail(data) : data를 가진 node가 tail로부터 몇 번째 node인지 출력 data가 없을 시 'not found'를 출력
- insertBefore(data, beforeData) : data를 가진 node전에 (head로부터 가까운 쪽) beforeData를 삽입 만약 data가 없을 시 'data not found'를 출력
파이썬으로 구현한 이중 연결 리스트
class Node(): def __init__(self, data, prev=None, next=None): self.data = data self.prev = prev self.next = next class Double_Linked_List(): def __init__(self, data): self.head = Node(data) self.tail = self.head def insert(self, data): self.tail.next = Node(data) self.tail.next.prev = self.tail self.tail = self.tail.next # head부터 순차적으로 print def desc(self): node = self.head while node: print(node.data) node = node.next # head에서부터 순차적으로 검색 def searchFromHead(self, data): node = self.head count = 0 while node: if node.data == data: print("index is", count) return count += 1 node = node.next print("not found") # tail에서부터 순차적으로 검색 def searchFromTail(self, data): node = self.tail count = -1 while node: if node.data == data: print("index is", count) return count += -1 node = node.prev print("not found") # data를 가진 node전에(head로부터 가까운 쪽) beforeData를 삽입 def insertBefore(self, data, beforeData): if data == self.head.data: node = Node(beforeData) self.head.prev = node node.next = self.head self.head = self.head.prev else: targetNode = self.head while targetNode: if targetNode.data == data: node = Node(beforeData) node.prev = targetNode.prev node.next = targetNode targetNode.prev.next = node targetNode.prev = node return else: targetNode = targetNode.next print("data not found")
'Data Structure > List' 카테고리의 다른 글
[자료구조/Data Structure] 파이썬으로 연결 리스트(Linked List) 자료구조 알아보기 (0) 2021.06.05