[Python Algorithms] 이중 연결 리스트

이중 연결 리스트는 (단일) 연결 리스트와 다르게 두 개의 포인터를 이용해 양방향으로 이동할 수 있는 자료구조이다.

(단일) 연결 리스트와는 연결 링크(포인터)가 하나 추가되었다는 것 이외에 큰 차이점은 없다.

 

 

1. 노드(Node) 정의하기

class Node:
	def __init__(self, data, next=None, prev=None):
    	self.date = data
        self.next = next
        self.prev = prev

(단일) 연결 리스트와의 차이점으로는 prev라는 포인터가 하나 더 생겼다는 것을 알 수 있다.

 

2. 이중 연결 리스트 초기화하기

class Node:
	def __init__(self, data, next=None, prev=None):
    	self.date = data
        self.next = next
        self.prev = prev
        
def init_list():
    global node_A
    node_A = Node("A")
    node_B = Node("B")
    node_D = Node("D")
    node_D = Node("E")
    node_A.next = node_B
    node_B.next = node_D
    node_B.prev = node_A
    node_D.next = node_E
    node_D.prev = nove_B

노드 객체 A, B, D, E를 생성한 후 각 노드 앞 뒤에 노드들을 연결해준다.

 

 

3. 이중 연결 리스트 삽입하기

class Node:
	def __init__(self, data, next=None, prev=None):
    	self.date = data
        self.next = next
        self.prev = prev
        
def init_list():
    global node_A
    node_A = Node("A")
    node_B = Node("B")
    node_D = Node("D")
    node_D = Node("E")
    node_A.next = node_B
    node_B.next = node_D
    node_B.prev = node_A
    node_D.next = node_E
    node_D.prev = nove_B
    
def insert_node(data):
    global node_A
    new_node = Node(data)
    node_P = node_A
    node_T = node_A
    while node_T.data <= data:
        node_P = node_T
        node_T = node_T.next
    new_node.next = node_T
    node_P.next = new_node
    new_node.prev = node_P
    node_T.prev = new_node

 이중 연결 리스트의 삽입 알고리즘 역시 (단일) 연결 리스트와 비슷하다.

노드 삽입 위치를 검색한 후 node_P는 삽입하게 될 노드의 앞 노드를 가리키고 node_T는 삽입하게 될 노드의 다음 노드를 가리키게 된다.

이 후 새로운 노드를 삽입한 후 새로운 노드의 이전 노드인 node_P와 이후 노드인 node_T의 next와 prev링크를 수정해주면 된다.

 

4. 이중 연결 삭제 알고리즘

class Node:
	def __init__(self, data, next=None, prev=None):
    	self.date = data
        self.next = next
        self.prev = prev
        
def init_list():
    global node_A
    node_A = Node("A")
    node_B = Node("B")
    node_D = Node("D")
    node_D = Node("E")
    node_A.next = node_B
    node_B.next = node_D
    node_B.prev = node_A
    node_D.next = node_E
    node_D.prev = nove_B

def delete_node(del_data):
    global node_A
    pre_node = node_A
    next_node = pre_node.next
    next_next_node = next_node.next
    
    if pre_node.data == del_data:
        node_A = next_node
        del pre_node
        return
        
    while next_node:
        if next_node.data == del_data:
             next_next_node = next_node.next
             pre_node.next = next_node.next
             next_next_node.prev = next_node.prev
             del next_node
             break

 

5. 연결 리스트 알고리즘 분석하기 (단일 연결 리스트와 비교하기)

(단일) 연결 리스트는 한 방향 탐색만 가능하고

이중(다중) 연결 리스트는 양쪽 방향으로 탐색이 가능하다.

 

양방향으로 탐색이 가능하다는 것은 전체적인 탐색 시간을 줄여준다는 장점이 있지만

노드 삽입과 삭제 시에 코드가 복잡해질 수 있다는 단점이 있다.

 

 

 

---

[참고 문헌]

 

1. 위키백과, "연결 리스트", https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

2. 박선주, 영진닷컴, "필수 알고리즘 with 파이썬