Linked list (1) : deque, merge sorted lists

공부를 하면 할 수록, 기본 개념은 간단하며 소위 '기초'로 분류되는 주제이나 실제로 문제를 풀기에는 여간 까다롭지 않은 것이 연결 리스트라는 생각이 든다. 주변 엔지니어에게 경험을 물어봐도 이 주제를 어렵다고 평가하는 것을 들을 수 있었다. 대표적 문제를 풀면서 심층적으로 탐구해 보고자 한다.

정의

연결 리스트는 아래와 같이 정의된 노드들의 연결로 이루어진다 (Goodrich et al. [1])

class _Node:
    def __init__(self, element=0, next=None, prev=None): # initialize node's fields
      self._element = element   # user's element
      self._prev = prev         # previous node reference
      self._next = next         # next node reference, 단일 연결리스트의 경우는 불필요

 

리스트의 뒤에 내용을 손쉽게 삽입하거나 삭제, 또는 값을 검색하기 위한 멤버함수(메소드) 등을 별도의 클래스를 만들어 정의할 수 있다. 이중 연결리스트와 이를 이용한 deque의 구현 코드를 소개한다. [1]

# Copyright 2013, Michael H. Goldwasser (GNU General Public License)

class _DoublyLinkedBase:
  """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

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

  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

  #-------------------------- 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."""
    return self._size == 0

  #-------------------------- 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)      # 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                                      # return deleted element

 

우선 이중 연결리스트의 안에는 nested class로서 _Node가 있다. 이처럼 클래스를 정의하기 위해 다른 클래스의 정의를 활용한 객체지향(OOP) 디자인 패턴을 합성(composition)이라고 부르기도 한다. 멤버함수의 정의에 _Node가 쓰이고 있는 것을 볼 수 있다. __slots__ 는 속도를 빠르게 하기 위한 장치로 생략 가능하다.

이를 이용한 Double-ended queue (deque) 의 구현은 다음과 같다. 앞의 _DoublyLinkedBase 클래스를 상속한 다음, 그 클래스의 nonpublic 멤버(field, method)를 적절한 인수(argument)를 넣어 호출하는 역할인 public method 들의 모음으로 구현이 되어 있다. 결국 deque는 이중 연결 리스트에 다름 아닌 것이다. deque는 collections.deque 에서 간편하게 사용할 수 있으나 연결리스트의 예로서 소개하였다.

 

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 the deque.

    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

 

연결리스트로 구현한 deque는 보는 바와 같이 queue의 앞과 뒤에서의 삽입, 삭제가 O(1) 만에 이루어진다.

문제

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

정렬된 두 연결리스트(list 1, list 2)를 역시 정렬되도록 합칠 것. 즉 merge sort와 유사하다고 할 수 있다. 내용을 정리하면 다음 그림과 같다.

그림으로 요약한 알고리즘

1. 빈 dummy head (DH) 를 만들고 tail (T) 가 이것을 가리키도록 최초 설정한다. DH는 리스트의 맨 처음을 굳건히 가리키기 위한 용도이다. 나중에 이것의 next를 리턴할 계획이다.

2. 어느 한 list가 존재할 때 까지 두 리스트의 값을 비교하면서 DH의 뒤에 계속 작은 값을 붙인다. 이 붙이는 역할을 tail을 움직이면서 수행하게 된다. 예를 들어 list 1의 첫 노드가 list 2의 첫 노드보다 더 작았다고 하자 그러면 이것을 먼저 DH의 뒤에 붙여야 한다 (merge sort의 merge 단계와 같다).

3. 주어진 리스트들의 길이가 같다는 보장은 없었으므로 2번 과정을 수행하고 나면 한 리스트의 남은 부분이 있을 수 있다. 이를 tail.next에 붙이기 위해 l1 또는 l2 중 존재하는 것을 붙인다.

4. 1에서 계획한대로 dh.next를 리턴한다.

만일 dh를 만들지 않으면 어떻게 될까. 두 리스트의 head node 중 작은 값을 선택한 다음 그것에서 출발하도록 하면 될까. 그러면 해당 리스트를 순회해야 할텐데, 그러려면 결국 포인터를 만들어야 한다. 그러므로 리스트의 경우는 dummy head를 만들어 푸는 것이 편리하다고 생각된다.

 

참고문헌

[1] Goodrich et al., 2013, Data Structures and Algorithms in Python, pp 270-276, Wiley