4-5. 양방향 연결 리스트로 덱 구현하기

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

 

3-3 덱

 

양방향 연결 리스트로 덱을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

덱

연결 리스트로 만든 덱의 형태

 

1. LinkedDeque 클래스

from .doubly_linked_base import _DoublyLinkedBase
class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedDeque(_DoublyLinkedBase):					# note the use of inheritance
	"""Double-ended queue implementation based on a doubly linked list."""

	def first(self):
		"""Return (but do not remove) the element at the front of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._header._next._element			# real item just after header

	def last(self):
		"""Return (but do not remove) the element at the back of queue.
        Raise Empty Exception if the deque is_empty"""
		if self.is_empty():
			raise Empty('Deque is_empty.')
		return self._trailer._prev._element			# real item just before trailer

	def insert_first(self, e):
		"""Add an element to the front of the deque."""
		self._insert._between(e, self._header, self._header._next)	# after header

	def insert_last(self, e):
		"""Add an element to the back of the deque."""
		self._insert._between(e, self._trailer._prev, self._trailer)	#before trailer
        
	def delete_first(self):
		"""Remove and return the element from the front of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._delete_node(self._header._next)		# use inherited method
        
	def delete_last(self):
		"""Remove and return the element from the back of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._delete_node(self._trailer._prev)		# use inherited method

---

1) 클래스 선언: _DoublyLinkedBase에서 상속받음.

from .doubly_linked_base import _DoublyLinkedBase
class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedDeque(_DoublyLinkedBase):					# note the use of inheritance
	"""Double-ended queue implementation based on a doubly linked list."""

 

2) 첫번째 요소 반환: 덱이 비어 있으면 Empty Exception 발생, header 다음 노드의 요소 반환

	def first(self):
		"""Return (but do not remove) the element at the front of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._header._next._element			# real item just after header

 

3) 마지막 요소 반환: 덱이 비어 있으면 Empty Exception 발생, trailer 이전 노드의 요소 반환

	def last(self):
		"""Return (but do not remove) the element at the back of queue.
        Raise Empty Exception if the deque is_empty"""
		if self.is_empty():
			raise Empty('Deque is_empty.')
		return self._trailer._prev._element			# real item just before trailer

 

4) 첫번째 요소로 삽입: header와 header 다음 노드 사이에 새로운 노드 삽입

	def insert_first(self, e):
		"""Add an element to the front of the deque."""
		self._insert._between(e, self._header, self._header._next)	# after header

 

5) 마지막 요소로 삽입: trailer 이전 노드와 trailer 사이에 새로운 노드 삽입

	def insert_last(self, e):
		"""Add an element to the back of the deque."""
		self._insert._between(e, self._trailer._prev, self._trailer)	#before trailer

 

6) 첫번째 요소 삭제: 덱이 비어 있으면 Empty Exception 발생, header 다음 요소 삭제 

	def delete_first(self):
		"""Remove and return the element from the front of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._delete_node(self._header._next)		# use inherited method

 

7) 마지막 요소 삭제: 덱이 비어 있으면 Empty Exception 발생, trailer 이전 노드 삭제 

	def delete_last(self):
		"""Remove and return the element from the back of the deque.
        Raise Empty Exception if the deque is_empty."""
		if self.is_empty():
			raise Empty('Deque is_empty')
		return self._delete_node(self._trailer._prev)		# use inherited method

 

2. 성능 분석

 양방향 연결 리스트로 덱을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time
D.first()	O(1)
D.last()	O(1)
D.insert_first()	O(1)
D.insert_last()	O(1)
D.delete_first()	O(1)
D.delete_last()	O(1)

 

3. 원형 양방향 덱 구현하기

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

  #-------------------------- nested _Node class --------------------------
  # nested _Node 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

    def __str__(self):                                  # modified
      return str(self._element)                         # modified

  #-------------------------- list constructor --------------------------

  def __init__(self):
    """Create an empty list."""
    self._header = self._Node(None, None, None)
    self._header._next = self._header                   # modified
    self._header._prev = self._header                   # modified
    self._size = 0                                      # number of elements

  #-------------------------- public accessors --------------------------

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

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

  #-------------------------- nonpublic utilities --------------------------

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

  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
    element = node._element
    node._prev = node._next = node._element = None
    self._size -= 1
    return element

  def __iter__(self):  # generator 정의
      v = self._header._next
      while v != self._header:
          yield v
          assert isinstance(v._next, object)
          v = v._next

  def __str__(self):  # 연결 리스트의 값을 print 출력
      return " -> ".join(str(v) for v in self)
		
class Empty(Exception):
  """Error attempting to access an element from an empty container."""
pass

class CircularLinkedDeque(_CircularDoublyLinkedBase):         # note the use of inheritance
  """Double-ended queue implementation based on a doubly linked list."""

  def first(self):
    """Return (but do not remove) the element at the front of the deque.
    Raise Empty exception if the deque is empty.
    """
    if self.is_empty():
      raise Empty('Deque is empty')
    return self._header._next._element

  def last(self):
    """Return (but do not remove) the element at the back of the deque.
    Raise Empty exception if the deque is empty.
    """
    if self.is_empty():
      raise Empty('Deque is empty')
    return self._header._prev._element

  def insert_first(self, e):
    """Add an element to the front of the deque."""
    self._insert_between(e, self._header, self._header._next)

  def insert_last(self, e):
    """Add an element to the back of the deque."""
    self._insert_between(e, self._header._prev, self._header)

  def delete_first(self):
    """Remove and return the element from the front of the deque.
    Raise Empty exception if the deque is empty.
    """
    if self.is_empty():
      raise Empty("Deque is empty")
    v = self._header._next
    return self._delete_node(v)
	
  def delete_last(self):
    """Remove and return the element from the back of the deque.
    Raise Empty exception if the deque is empty.
    """
    if self.is_empty():
      raise Empty("Deque is empty")
    v = self._header._prev
    return self._delete_node(v)


D = CircularLinkedDeque()
command_list = [(D.insert_first, 3, 'D.insert_first(3)'),  
                (D.insert_first, 7, 'D.insert_first(7)'), 
                (D.first, None, 'D.first()'), 
                (D.delete_last, None, 'D.delete_last()'),  
                (len, D, 'len(D)'), 
                (D.delete_last, None, 'D.delete_last()'),
                (D.delete_last, None, 'D.delete_last()'), 
                (D.insert_first, 6, 'D.insert_first(6)'),
                (D.last, None, 'D.last()'), 
                (D.insert_first, 8, 'D.insert_first(8)'), 
                (D.is_empty, None, 'D.is_empty()'),   
                (D.last, None, 'D.last()')]
                
idx = 0
for command, args, cmd_str in command_list:
  print(idx, ':', cmd_str, end="\t")  # 실행할 명령어를 출력
  try:
    return_v = None
    if args == None : 
      return_v = command()      # 메소드 호출
    else:
      return_v = command(args)  # 메소드를 호출할 때 인자(args)가 존재하면 전달
  except Empty as e:            # Empty Exception이 발생하면 종료되지 않도록 오류를 출력
    print(e, end="\t")

  if return_v != None: print(return_v, end="\t")  # 메소드 호출 결과가 None이 아니면 출력
  print('[', D, ']')                              # 덱 내용을 출력
  idx += 1

 

이 코드를 실행한 결과는 다음과 같다.

 

0 : D.insert_first(3) [ 3 ]
1 : D.insert_first(7)   [ 7 -> 3 ]
2 : D.first()   7       [ 7 -> 3 ]
3 : D.delete_last()     3       [ 7 ]
4 : len(D)      1       [ 7 ]
5 : D.delete_last()     7       [  ]
6 : D.delete_last()     Deque is empty  [  ]
7 : D.insert_first(6)   [ 6 ]
8 : D.last()    6       [ 6 ]
9 : D.insert_first(8)   [ 8 -> 6 ]
10 : D.is_empty()       False   [ 8 -> 6 ]
11 : D.last()   6       [ 8 -> 6 ]

 

다음 게시글에서는 포지션 리스트를 다룬다.