4-4. 양방향 연결 리스트

 한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다.

한방향 연결 리스트

• 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다.
• 삭제를 하려면 삭제할 노드뿐만 아니라 이전 노드의 레퍼런스가 필요한데, 항상 head부터 해당 노드의 이전 노드까지 이동하는 시간이 필요하다.

연결 리스트가 대칭성을 갖도록 이전 노드와 다음 노드의 레퍼런스를 갖도록 해보자.

 

1. 양방향 연결 리스트

양방향 연결 리스트

양방향 연결 리스트(Doubly Linked List)는 노드들이 양방향으로 연결된 리스트로, 각 노드들은 객체(element), 이전 노드(prev), 다음 노드(next)의 레퍼런스를 저장한다. 이때 링크를 따라 특정 노드의 데이터를 접근하고 수정한다.

 

header와 trailer

양방향 연결 리스트에서 header와 trailer Sentinel을 사용하면 구현이 단순해진다. 양방향 연결 리스트는 삽입(insert)/삭제(delete) 연산을 할 때 항상 두 노드 사이에서 연산이 이루어지며 예외처리 로직이 사라진다.

 

1) 삽입

삽입

2) 삭제

삭제

 

2. _DoublyLinkedList 클래스

class _DoublyLinkedList:
	"""A base class providing a doubly linked list representation."""

	class _Node:
		"""Lightweight, nonpublic class for storing a doubly linked node."""
		__slots__ = '_element', '_prev', '_next'			# streamline memory

		def __init__(self, element, prev, next):			# initialize node's fields
			self._element = element					# user's element
			self._prev = prev					# previous node reference
			self._next = next					# next node reference

	def __init__(self):
		"""Create an empty list."""
		self._header = self._Node(None, None, None)
		self._trailer = self._Node(None, None, None)
		self._header._next = self._trailer				# trailer is after header
		self._trailer._prev = self._header				# header is before trailer
		self._size = 0							# number of elements

	def __len__(self):
		"""Return the number of elements in the list."""
		return self._size
        
	def is_empty():
		"""Return True if list is_empty."""
		return self._size == 0
        
	def _insert_between(self, e, predecessor, successor):
		"""Add element e between two existing nodes and return new node."""
		newest = self._Node(e, predecessor, successor)			# linked to neighbors
		predecessor._next = newest
		successor._prev = newest
		self._size += 1
		return newest
        
	def _delete_node(self, node):
		"""Delete nonsentinel node from the list and return its element."""
		predecessor = node._prev
		successor = node._next
		predecessor._next = successor
		successor._prev = predecessor
		self._size -= 1
		element = node._element						# record deleted element
		node._prev = node._next = node._element = None			# deprecate node
		return element
        

---

1) 클래스 선언

class _DoublyLinkedList:
	"""A base class providing a doubly linked list representation."""

 

2) Node 클래스 선언: Node 클래스를 외부에 보이지 않도록 nonpublic class로 선언

	class _Node:
		"""Lightweight, nonpublic class for storing a doubly linked node."""
		__slots__ = '_element', '_prev', '_next'			# streamline memory

		def __init__(self, element, prev, next):			# initialize node's fields
			self._element = element					# user's element
			self._prev = prev					# previous node reference
			self._next = next					# next node reference

 

3) 초기화

header와 trailer의 초기화

• self._header: header 노드
• self._trailer: trailer 노드
• self._size: 양방향 연결 리스트에 저장된 요소 개수

	def __init__(self):
		"""Create an empty list."""
		self._header = self._Node(None, None, None)
		self._trailer = self._Node(None, None, None)
		self._header._next = self._trailer				# trailer is after header
		self._trailer._prev = self._header				# header is before trailer
		self._size = 0							# number of elements

 

4) 양방향 연결 리스트에 저장된 요소 개수: self._size를 return

	def __len__(self):
		"""Return the number of elements in the list."""
		return self._size

 

5) 큐가 비어 있는지 확인: self._size가 0이면 True로, 아니면 False로

	def is_empty():
		"""Return True if list is_empty."""
		return self._size == 0

 

6) 두 노드 사이에 삽입

• 새로운 노드를 생성해 predecessor와 successor 사이에 추가
• predecessor 다음에 새로운 노드 연결
• successor 이전에 새로운 노드 연결
• 크기를 1 증가, 새로운 노드 반환

	def _insert_between(self, e, predecessor, successor):
		"""Add element e between two existing nodes and return new node."""
		newest = self._Node(e, predecessor, successor)			# linked to neighbors
		predecessor._next = newest
		successor._prev = newest
		self._size += 1
		return newest

 

7) 노드 삭제

• node의 이전 노드를 predecessor로 지정
• node의 다음 노드를 successor로 지정
• predecessor의 다음 노드를 successor로 지정
• successor의 이전 노드를 predecessor로 지정
• 크기를 1 줄이고 node의 prev, next, element 레퍼런스를 None으로 지정
• node의 element를 반환

	def _delete_node(self, node):
		"""Delete nonsentinel node from the list and return its element."""
		predecessor = node._prev
		successor = node._next
		predecessor._next = successor
		successor._prev = predecessor
		self._size -= 1
		element = node._element						# record deleted element
		node._prev = node._next = node._element = None			# deprecate node
		return element

 

다음 게시글에서는 양방향 연결 리스트로 덱을 만들어 볼 것이다.