더블리 링크드 리스트의 구현 및 연산, 링크드 리스트와의 차이점 - 파이썬 (Python)

더블리 링크드 리스트는 링크드 리스트와 다르게 노드 안에 data와 다음 노드에 대한 정보, 그리고 이전 노드에 대한 정보를 가진다.

 

따라서 특정 노드를 탐색하거나 리스트 크기를 구할 때는 일반적인 링크드 리스트와 동일한 메서드를 사용할 수 있지만,

 

노드를 정의할 때와 삽입 및 제거 연산을 해줄 때는 약간은 다른 방식이 필요하다.

 

먼저, 더블리 링크드 리스트의 노드는 다음과 같다.

# 더블리 링크드 리스트의 노드 클래스

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None
        self.prev = None # 이전 노드에 대한 정보도 저장해준다.

 

더블리 링크드 리스트의 연산 (삽입, 삭제)

 

링크드 리스트와는 다르게, 특정 데이터가 삽입되거나 삭제되면 관련 노드의 prev까지 수정되어야한다.

 

1) append 연산 - 맨 뒤에 새로운 노드를 추가

 

# 더블리 링크드 리스트의 append 연산

def append(self, data):
	new_node = Node(data)
    
   	if self.head != None:
    	self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
    
    else: # 리스트가 비어있을 때
    	self.head = new_node
        self.tail = new_node

 

2) prepend 연산 - 맨 앞에 새로운 노드를 추가

 

# 더블리 링크드 리스트의 prepend 연산

def prepend(self, data):
	new_node = Node(data)
    
    if self.head == None: # 리스트가 비었을 때
    	self.head = new_node
        self.tail = new_node
	
    else:
    	self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

 

3) insert_after 연산 - 파라미터로 받은 노드 다음에 새로운 값을 추가

 

# 더블리 링크드 리스트의 insert_after 연산

def insert_after(self, prev_node, data):
	new_node = Node(data)
    
    if prev_node == None: # prev_node의 값이 잘못되었을 때
    	return None
    
    else:
		if prev_node == self.tail: # prev_node가 tail노드일 때
			self.append(data)

		elif: # 순서를 다르게 하면 꼬일 수 있음
        	prev_node.next.prev = new_node
            new_node.next = prev_node.next
            prev_node.next = new_node
            new_node.prev = prev_node
            

 

4) pop 연산 - 맨 뒤의 값을 삭제 후 삭제된 값을 리턴

 

# 더블리 링크드 리스트의 pop 연산

def pop(self):
	
    node_to_delete = self.tail
    
    if self.head == self.tail: # 리스트에 하나의 값만 존재할 때
    	self.head = None
        self.tail = None
    
    else: # 링크드 리스트에서와 다르게 iterator로 탐색할 필요가 없다
		new_tail = self.tail.prev
        new_tail.next = None
        self.tail = new_tail
        
	return node_to_delete

 

5) popleft 연산 - 맨 앞의 값을 삭제 후 삭제된 값을 리턴

 

# 더블리 링크드 리스트의 popleft 연산

def popleft(self):
	node_to_delete = self.head
    
    if node_to_delete == self.tail: # 리스트에 하나의 값만 존재할 때
    	self.head = None
        self.tail = None
	else:
      self.head.next.prev = None
      self.head = self.head.next
      
	return node_to_delete

 

6) delete_after 연산 - 파라미터로 받은 노드 다음의 값을 삭제 후 삭제된 값을 리턴

 

# 더블리 링크드 리스트의 delete_after 연산

def delete_after(self, prev_node):
	if prev_node == None: # 파라미터로 받아온 prev_node의 값이 잘못되었을 때
    	return None
        
	else:
    	if prev_node.next == self.tail: # 삭제하려는 값이 tail 노드일 때
        	self.pop()
		
        else: # 삭제될 노드와의 연결을 끊어주고 그 다음 노드와 연결
        	prev_node.next = prev_node.next.next 
            prev_node.next.next.prev = prev_node

 

링크드 리스트와 더블리 링크드 리스트의 차이

 

앞서 언급했듯, 두 리스트의 차이는 노드에 있다.

 

링크드 리스트는 하나의 노드에 데이터와 다음 노드에 대한 레퍼런스를 저장한다.

 

반면에 더블리 링크드 리스트는 노드에 데이터와 다음 노드, 그리고 이전 노드의 레퍼런스를 저장한다.

 

다시 말해, 더블리 링크드 리스트는 tail에서 역순으로 다른 데이터에게 접근이 가능하다.

 

이것은 pop연산에서 명백한 차이점을 보여준다.

 

링크드 리스트의 경우, tail의 이전 노드에 접근하기 위해선 head부터 선형적으로 거슬러 올라가야한다.

 

따라서 pop연산을 하기 위해선 실질적으로 O(n)만큼의 시간이 걸린다.

 

하지만 더블리 링크드의 리스트에서는 tail에서 곧바로 이전 노드로 접근할 수 있기 때문에 pop 연산을 O(1) 시간내에 할 수 있다.