일반적인 리스트(List)

  • 일련의 동일한 타입의 항목(item)들
  • 실생활의 예
    • 학생 명단
    • 시험 성적
    • 서점의 신간 서적
    • 상점의 판매 품목
    • 실시간 급상승 검색어
    • 버킷 리스트
    • 등등
  • 일반적인 리스트의 구현
    • 1차원 파이썬 리스트(list)
    • 단순연결리스트
    • 이중연결리스트
    • 원형연결리스트

단순연결리스트

  • 단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조
  • 동적 메모리 할당을 받아 노드(node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴

단순연결리스트를 위한 SList 클래스

In [8]:
class SList:
  class Node:
    def __init__(self, item, link):
      self.item = item
      self.next = link
  
  def __init__(self):
    self.head = None
    self.size = 0

  def size(self):
    return self.size

  def is_empty(self):
    return self.size == 0

  def insert_front(self, item):
    if self.is_empty():
      self.head = self.Node(item, None)
    else:
      self.head = self.Node(item, self.head)
    self.size += 1

  def insert_after(self, item, p):
    p.next = SList.Node(item, p.next)
    self.size += 1

  def delete_front(self):
    if self.is_empty():
      raise EmptyError('Underflow')
    else:
      self.head = self.head.next
      self.size -= 1

  def delete_after(self, p):
    if self.is_empty():
      raise EmptyError('Underflow')
    t = p.next
    p.next = t.next
    self.size -= 1

  def search(self, target):
    p = self.head
    for k in range(self.size):
      if target == p.item:
        return k
      p = p.next
    return None

  def print_list(self):
    p = self.head
    while p:
      if p.next != None:
        print(p.item, ' -> ', end='')
      else:
        print(p.item)
      p = p.next

  class EmptyError(Exception):
    pass

단순연결리스트 SList 사용

In [15]:
#from slist import SList  
#slist.py 파일에서 Slist를 import -> iPython에서는 위쪽에 선언되어 있어 사용안함

#if __name__ == '__main__': # iPython에서는 위쪽에 선언되어 있어 사용안 함

s = SList()
s.insert_front('orange'), s.print_list()
s.insert_front('apple'), s.print_list()
s.insert_after('cherry', s.head.next), s.print_list()
s.insert_front('pear'), s.print_list()

s.delete_front(), s.print_list()
s.delete_front(), s.print_list()
s.delete_front(), s.print_list()
s.delete_front(), s.print_list()
s.delete_front(), s.print_list()

orange
apple  -> orange
apple  -> orange  -> cherry
pear  -> apple  -> orange  -> cherry
apple  -> orange  -> cherry
orange  -> cherry
cherry

---------------------------------------------------------------------------
EmptyError                                Traceback (most recent call last)
<ipython-input-15-a679a2b9eae5> in <module>
     14 s.delete_front(), s.print_list()
     15 s.delete_front(), s.print_list()
---> 16 s.delete_front(), s.print_list()

<ipython-input-8-27304b5fda69> in delete_front(self)
     28   def delete_front(self):
     29     if self.is_empty():
---> 30       raise EmptyError('Underflow')
     31     else:
     32       self.head = self.head.next

EmptyError: Underflow

수행시간

  • search() : 는 탐색을 위해 연결리스트의 노드들을 첫 노드부터 순차적으로 방문해야 하므로 O(N) 시간 소요
  • 삽입이나 삭제 연산은 각각 O(1) 개의 레퍼런스만을 갱신하므로 O(1) 시간 소요
  • 단, insert_after()나 delete_after()의 경우에 특정 노드 p의 레퍼런스가 주어지지 않으면 head로부터 p를 찾기 위해 search()를 수행해야 하므로 O(N) 시간 소요

이중연결리스트(Doubly Linked List)

  • 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트
  • 단순연결리스트는 삽입이나 삭제할 때 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음
  • 이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐

이중연결리스트를 위한 DList 클래스

In [31]:
class DList:
  class Node:
    def __init__(self, item, prev, link):
      self.item = item
      self.prev = prev
      self.next = link

  def __init__(self):
    self.head = self.Node(None, None, None)
    self.tail = self.Node(None, self.head, None)
    self.head.next = self.tail
    self.size = 0

  def size(self):
    return self.size

  def is_empty(self):
    return self.size == 0

  def insert_before(self, p, item):
    t = p.prev
    n = self.Node(item, t, p)
    p.prev = n
    t.next = n
    self.size += 1

  def insert_after(self, p, item):
    t = p.next
    n = self.Node(item, p, t)
    t.prev = n
    p.next = n
    self.size += 1

  def delete(self, x):
    if self.is_empty():
      raise EmptyError('Underflow')

    f = x.prev
    r = x.next
    f.next = r
    r.prev = f
    self.size -= 1
    return x.item

  def print_list(self):
    if self.is_empty():
      print('리스트 비어있음')
    else:
      p = self.head.next
      while p != self.tail:
        if p.next != self.tail:
          print(p.item, ' <=> ', end='')
        else:
          print(p.item)
        p = p.next

  class EmptyError(Exception):
    pass

이중연결리스트 DList 사용

In [34]:
#from dlist import DList  
#dlist.py 파일에서 Dlist를 import -> iPython에서는 위쪽에 선언되어 있어 사용안함

#if __name__ == '__main__': # iPython에서는 위쪽에 선언되어 있어 사용안 함

s = DList()
s.insert_after(s.head, 'apple'), s.print_list()
s.insert_before(s.tail, 'orange'), s.print_list()
s.insert_before(s.tail, 'cherry'), s.print_list()
s.insert_after(s.head.next, 'pear'), s.print_list()

s.delete(s.tail.prev), s.print_list()
s.delete(s.tail.prev), s.print_list()
s.delete(s.tail.prev), s.print_list()
s.delete(s.tail.prev), s.print_list()
#s.delete(s.tail.prev), s.print_list()

apple
apple  <=> orange
apple  <=> orange  <=> cherry
apple  <=> pear  <=> orange  <=> cherry
apple  <=> pear  <=> orange
apple  <=> pear
apple
리스트 비어있음
Out[34]:
('apple', None)

수행시간

  • 이중연결리스트에서 삽입이나 삭제 연산은 각각 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행
  • 탐색 연산: head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 시간 소요

원형연결리스트(Circular Linked List)

  • 마지막 노드가 첫 노드와 연결된 단순연결리스트
  • 원형연결리스트에서는 마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할

원형연결리스트를 위한 CList 클래스

In [42]:
class CList:
  class Node:
    def __init__(self, item, link):
      self.item = item
      self.next = link

  def __init__(self):
    self.last = None
    self.size = 0

  def size(self):
    return self.size

  def is_empty(self):
    return self.size == 0

  def insert(self, item):
    n = self.Node(item, None)
    if self.is_empty():
      n.next = n
      self.last = n
    else:
      n.next = self.last.next
      self.last.next = n
    self.size += 1

  def first(self):
    if self.is_empty():
      raise EmptyError('Underflow')
    f = self.last.next
    return f.item    

  def delete(self):
    if self.is_empty():
      raise EmptyError('Underflow')
    x = self.last.next

    if self.size == 1:
      self.last = None
    else:
      self.last.next = x.next
    self.size -= 1
    return x.item

  def print_list(self):
    if self.is_empty():
      print('리스트 비어있음')
    else:
      f = self.last.next
      p = f 
      while p.next != f:
        print(p.item, ' -> ', end='')
        p = p.next
      print(p.item)

class EmptyError(Exception):
  pass

원형연결리스트 CList 사용

In [46]:
#from clist import CList  
#clist.py 파일에서 Clist를 import -> iPython에서는 위쪽에 선언되어 있어 사용안함

#if __name__ == '__main__': # iPython에서는 위쪽에 선언되어 있어 사용안 함

s = CList()
s.insert('pear'), s.print_list()
s.insert('cherry'), s.print_list()
s.insert('orange'), s.print_list()
s.insert('apple'), s.print_list()

s.delete(), s.print_list()
s.delete(), s.print_list()
s.delete(), s.print_list()
s.delete(), s.print_list()
s.delete(), s.print_list()

pear
cherry  -> pear
orange  -> cherry  -> pear
apple  -> orange  -> cherry  -> pear
orange  -> cherry  -> pear
cherry  -> pear
pear
리스트 비어있음

---------------------------------------------------------------------------
EmptyError                                Traceback (most recent call last)
<ipython-input-46-9e78323dc9d7> in <module>
     14 s.delete(), s.print_list()
     15 s.delete(), s.print_list()
---> 16 s.delete(), s.print_list()

<ipython-input-42-ad7dd4463a28> in delete(self)
     33   def delete(self):
     34     if self.is_empty():
---> 35       raise EmptyError('Underflow')
     36     x = self.last.next
     37 

EmptyError: Underflow

수행시간

  • 원형연결리스트에서 삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간에 수행
  • 탐색 연산: last로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 소요
In [ ]: