[Concept] 더블 링크드 리스트 (double linked list)

[Concept] 더블 링크드 리스트 (double linked list)

이번 글에서는 더블 링크드 리스트 (이중 연결 리스트) 에 대해 적어보겠습니다.

이전 글에서 적었던 일반 링크드 리스트는 데이터를 조회할 때 head, 즉 앞에서부터 찾아가는 방식이었습니다.

But, 만약 데이터가 20000개가 있고, 맨 마지막 데이터를 조회하고자한다면, 20000번 조회를 해야하는거겠죠?

대신 뒤에서부터 조회한다면 어떨까요?

즉, 앞쪽의 데이터를 조회할 떄는 앞에서부터, 뒤쪽의 데이터를 조회할 때는 뒤에서부터 찾아나갈 수 있는 리스트가 더블 링크드 리스트 입니다.

이전 기본 연결 리스트의 노드에는 데이터와 next 주소만 있었다면,

더블 연결 리스트에는 prev 주소 도 함께 저장됩니다.

이전 기본 연결 리스트에서는, self.head()만 지정했다면,

더블 연결 리스트에는 self.tail() 도 지정해줄 수 있습니다.

구조

장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

설명은 주석으로 달았으니 참고하시면 이해될 거에요! 위의 내용이 이해 안 됐다면 이전 글 '링크드 리스트'를 읽고오셔도 좋을 듯 해요

1

노드 생성 과 맨 끝에 노드를 추가 하는 코드를 적어봅시다.

# 노드 생성 class Node: def __init__(self, data, prev=None, next=None): self.data = data self.prev = prev # 더블 연결리스트니까! self.next = next # 노드(linked list) 관리 class NodeMgmt: # 처음 노드 생성 시 호출되는 생성자 def __init__(self, data): self.head = Node(data) # 클래스 Node의 생성자 호출 self.tail = self.head # head이자 tail # 노드 추가 def insert(self, data): if self.head == None: self.head= Node(data) self.tail = self.head else: node = self.head while node.next: # 가장 끝으로 이동 node = node.next # 가장 끝으로 왔으면 new = Node(data) node.next = new new.prev = node self.tail = new # 노드 조회 def desc(self): node = self.head while node: print(node.data) node = node.next

2

특정 데이터를 앞에서부터 혹은 뒤에서부터 찾는 메서드를 적어봅시다.

# 앞에서부터 찾기 def search_from_head(self,data): # 방어코드 if self.head == None: return False # head에서 시작 node = self.head while node: if node.data == data: return node.data else: node = node.next # 뒤로 return False # 뒤에서부터 찾기 def search_from_tail(self,data): # 방어코드 if self.head == None: return False # tail에서 시작 node = self.tail while node: if node.data == data: return node.data else: node = node.prev # 앞으로 return False

3

특정 노드 앞에 추가 하는 코드입니다.

def insert_before(self, data, before_data): # before_data 앞에 만들겠다. if self.head == None: self.head = Node(data) # head가 없으면(노드가 없으면) 생성! return True else: node = self.tail while node.data != before_data: # before_data와 일치하면? node = node.prev if node == None: return False new = Node(data) # 그앞에 새 노드 추가 before_new = node.prev # before_data의 앞이 before_new # next 주소연결 before_new.next = new new.next = node # prev 주소 연결 new.prev = before_new node.prev = new return True

4

특정 노드 뒤에 추가 하는 코드입니다.

def insert_after(self, data, after_data): if self.head == None: self.head = Node(data) return True else: node = self.head while node.data != after_data: # 일치하는 데이터 찾을 때까지 뒤로 node = node.next if node == None: return False # 일치하는 after_data 찾으면 new = Node(data) after_new = node.next # after_data의 뒤 new.prev = node # after_new.prev = new node.next = new new.next = after_new # after_new가 없다면 new가 tail! if after_new == None: self.tail = new return True

중간 주석은 생략해도 결과는 잘 나와서 주석처리 해주었습니다.

5

이제 직접 노드를 생성 하고, insert_after(), insert_before() 를 사용해보겠습니다.

node_mgmt = NodeMgmt(0) # 0은 이미 생성했으니 1부터 9까지 생성! for data in range(1, 10): node_mgmt.insert(data) # 0 1 2 3 4 5 6 7 8 9 생성 node_mgmt.insert_before(2.5, 3) node_mgmt.desc() # 0 1 2 2.5 3 4 5 6 7 8 9 생성 node_mgmt.insert_after(4.5, 4) node_mgmt.desc() # 0 1 2 2.5 3 4 4.5 5 6 7 8 9 생성

더보기 전체 코드 참고해주세요:) class Node: def __init__(self, data, prev=None, next=None): self.prev = prev self.data = data self.next = next class NodeMgmt: def __init__(self, data): self.head = Node(data) self.tail = self.head def insert(self, data): if self.head == None: self.head = Node(data) self.tail = self.head else: node = self.head while node.next: node = node.next new = Node(data) node.next = new new.prev = node self.tail = new def desc(self): node = self.head while node: print (node.data) node = node.next def search_from_head(self,data): # 방어코드 if self.head == None: return False node = self.head while node: if node.data == data: return node.data else: node = node.next return False def search_from_tail(self,data): # 방어코드 if self.head == None: return False node = self.tail while node: if node.data == data: return node.data else: node = node.prev return False def insert_before(self, data, before_data): # before_data 앞에 만들겠다. if self.head == None: self.head = Node(data) # head가 없으면 만들면되! return True else: node = self.tail while node.data != before_data: # before_data와 일치하면 그앞에 추가 node = node.prev if node == None: return False new = Node(data) before_new = node.prev # before_data의 앞이 before_new before_new.next = new new.next = node new.prev = before_new node.prev = new # before_data 앞에 추가한 것. return True def insert_after(self, data, after_data): if self.head == None: self.head = Node(data) return True else: node = self.head while node.data != after_data: # 일치하는 데이터 찾을 때까지 뒤로 node = node.next if node == None: return False # 일치하는 after_data 찾으면 new = Node(data) after_new = node.next # after_data의 뒤 new.prev = node # after_new.prev = new node.next = new new.next = after_new # after_new가 없다면 new가 tail! if after_new == None: self.tail = new return True

from http://thisisprogrammingworld.tistory.com/110 by ccl(A) rewrite - 2021-08-04 17:00:38