주제: 파이썬에서 연결리스트 구현하기(이중 & 원형리스트)

파이썬과 함께하는 자료구조의 이해[개정판] pp.61-75 참고해서 내용 작성하였습니다.
파이썬으로 배우는 자료구조 핵심 원리 pp.52-61 참고해서 내용 작성하였습니다.

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

정의
: 이중연결리스트는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트를 의미한다. (더미 이중연결리스트라고도 부른다.)

• 비교

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

---

1.1 코드 구현

🤜 입력

class DList:
    class Node:   # 노드 생성자 항목과 앞뒤 노드 레퍼런스
        def __init__(self, item, prev, link):   # item = None, link = None
            self.item = item
            self.prev = prev  # 리스트의 맨 처음과 마지막은 실제 데이터를 저장하지 않는 노드인'더미노드'라고 한다
            self.next = link
        
        def __init__(self):   # 초기화 # head와 tail을 연결한다 
            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)       # 새 노드 생성하여 n이 참조한다 
            p.prev = n     # 1
            t.next = n     # 2
            self.size += 1
            
        def insert_after(self, p, item):
            t = p.next
            n = self.Node(item, p ,t)
            t.prev = n     # 3
            p.next = n     # 4    # 1,2,3,4는 새 노드와 앞뒤 노드를 연결한다 
            self.size += 1
            
        def delete(self, x):
            f = x.prev
            r = x.next
            f.next = r  # x를 건너 띄고 x의 앞뒤 노드를 직접 연결한다 
            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):  # underflow 시 에러처리
    pass 

---

1.2 코드 이해하기

1. 노드 생성자 항목과 앞뒤 노드 레퍼런스

• 더미 이중연결리스트를 초기화한다. 여기서 가장 중요한 점은 head와 tail이 가리키는 더미 노드에는 데이터가 저장되어 있지 않다는 것이다.

• 구체적으로 그림을 표현하면 다음과 같다. 2개의 'dummy'노드를 생성하고이 노드에는 실제 항목을 저장하지 않는다.

2. insert_before() 코드

• 2번과 3번과 4번과정은 item인 apple을 orange 노드와 cherry 노드에 연결하는 과정이다.
• 5번과 6번 과정은 새로운 노드인 n을 연결하는 과정이다.

3. insert_after() 코드

• 2번과 3번과 4번과정은 위의 insert_before 과정과 똑같다. 위와 비교해봤을 때, p와 t의 위치만 바꼈을 뿐 수행 과정은 비슷하다.

4. delete() 코드

• x가 참조하는 노드는 연결리스트에서 분리되어 가비지 컬렉터에 의해 처리된다.

---

1.3 삽입, 삭제, 탐색 연산 수행

🤜 입력

from dlist import DList
if __name__ == '__main__':
    s = DList()
    s.insert_after(s.head, 'apple') 
    s.insert_before(s.tail, 'orange')
    s.insert_before(s.tail, 'cherry')
    s.insert_after(s.head.next, 'pear')
    s.print_list()
    print('마지막 노드 삭제 후:\t', end='')
    s.delete(s.tail.prev)
    s.print_list()
    print('맨 끝에 포도 삽입 후:\t', end='')
    s.insert_before(s.tail, 'grape')
    s.print_list()
    print('첫 노드 삭제 후:\t', end='')
    s.delete(s.head.next)
    s.print_list()
    print('첫 노드 삭제 후:\t', end='')
    s.delete(s.head.next)
    s.print_list()
    print('첫 노드 삭제 후:\t', end='')
    s.delete(s.head.next)
    s.print_list()
    print('첫 노드 삭제 후:\t', end='')
    s.delete(s.head.next)
    s.print_list()      # 일련의 삽입 삭제 탐색 연산 수행

💻 출력

• 수행시간
  : 삽입, 삭제 연산은 각각 O(1)개의 레퍼런스만을 갱신하므로 O(1)시간을 수행한다.

• 탐색 연산
  : head or tail로부터 순차적으로 탐색 O(N) 시간을 수행한다.

---

1.4 활용

• 데크 자료구조
• 이항 힙 or 피보나치 힙과 같은 우선순위 큐를 구현하는 데에도 이중연결리스트가 부분적으로 이용된다.

---

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

정의
: 원형연결리스트는 마지막 노드가 첫 노드와 연결된 단순연결리스트를 의미한다.

• 특징
  -마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할을 수행한다.
  -마지막 노드와 첫 노드를 O(1) 시간에 접근한다.
  -리스트가 empty가 아니면 프로그램에서 None 조건을 검사하지 않아도 되는 장점이 있다.
  -반대 방향으로 노드들을 방문하기 어렵고, 무한 루프가 발생할 수 있다는 단점이 있다.

---

2.1 코드 구현

🤜 입력

class CList:
    class Node:
        def __init__(self, item, link):
            self.item = item  # 노드 생성자 항목과 
            self.next = link # 다음 노드 레퍼런스 
        
        def __init__(self):
            self.last = None  # 원형연결리스트 생성자 last
            self.size = 0     # 항목 수 size로 구성
        
        def no_items(self): return self.size
        def is_empty(self): return self.size == 0
        
        def insert(self, item):     # 단순,이중연결리스트와 다른 삽입 방법이다.
            n = self.Node(item, None)  # 새 노드 생성하여 n이 참조한다.
            if self.is_empty():
                n.next = n       # 새 노드는 자신을 참조하고 last가 새 노드를 참조한다.
                self.last = n    # 위와 같음
            else:
                n.next = self.last.next   # 새 노드는 첫 노드를 참조하고 last가 참조하는 노드와 새 노드를 연결한다
                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  # empty리스트가 된다
            else:
                self.last.next = x.next # last가 참조하는 노드가 두 번째 노드를 연결한다
            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:  # f가 첫 노드가 아니라면 루프 중단한다.
                    print(p.item, ' -> ', end='')
                    p = p.next  # 노드들을 차례로 방문하기 위해
                print(p.item)
                
class EmptyError(Exception):  # underflow시 에러 처리
    pass

---

2.2 코드 이해하기

1. insert() 코드

• 단순,이중연결리스트의 삽입 과정과 많이 다르다.
• 새로운 노드를 리스트의 첫노드로 삽입하는 insert로 구현한다. 그 후, 연결리스트가 empty인 경우와 그렇지 않은 경우로 분리하여 연산을 수행한다.

  • empty 리스트인 경우의 새로운 노드가 삽입되는 과정을 나타낸다. (위 그림)
  • empty가 아닌 경우의 새로운 노드가 삽입되는 과정을 나타낸다 (아래 그림)

2. delete() 코드

• 삭제 연산은 리스트의 첫 노드를 삭제하는 delete로 구현한다.

  self.last.next 는 첫 노드를 의미한다.

• 연결리스트의 노드 갯수가 1이면, last를 None으로 만든다.
• 연결리스트의 노드 갯수가 2개 이상 있는 경우는 첫 노드를 `x.next 해주면 가비지 컬렉션이 수행된다.

---

2.3 삽입, 삭제, 탐색 연산 수행

🤜 입력

from clist import CList
if __name__ == '__main__':
    s = CList()
    s.insert('pear')
    s.insert('cherry')
    s.insert('orange')
    s.insert('apple')
    s.print_list()
    print('s의 길이=', s.no_items())
    print('s의 첫 항목 :', s.first())
    s.delete()
    print('첫 노드 삭제 후: ', end='')
    s.print_list()
    print('s의 길이=', s.no_items())
    print('s의 첫 항목 :', s.first())
    s.delete()
    print('첫 노드 삭제 후: ', end='')
    s.print_list()
    s.delete()
    print('첫 노드 삭제 후: ', end='')
    s.print_list()
    s.delete()
    print('첫 노드 삭제 후: ', end='')
    s.print_list()

💻 출력

• 수행시간
  : 삽입 or 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간이 수행된다.
  
  
• 탐색 연산
  : last로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 시간이 수행된다.

---

2.4 활용

• 여러 사람이 차례로 돌아가며 하는 게임을 구현하는데 적합하다.
• 많은 사람들이 동시에 사용하는 컴퓨터에서 CPU 시간을 분할하여 작업들에 할당하는 운영체제에 사용한다.
• 이항힙 or 피보나치힙과 같은 우선순위큐를 구현하는 데에도 부분적으로 사용된다.

---

3. 최종 정리

---

🎯 Summary

이번에는 연결리스트의 이중연결리스트와 원형연결리스트를 공부하였다. 연결리스트를 공부하면 할 수록 너무 복잡해서 코드를 뜯어보는 과정이 너무 힘들었다. 하지만 이것 또한 나중에 도움이 될 것이라고 믿는다.

원형연결리스트의 insert()의 노드 삽입 과정은 다른 연결리스트의 insert() 과정가 많이 달랐다. 이 점을 유의해서 공부해야겠다.

효율적인 코드 구성을 하는 그 날까지 열심히 공부하겠다!

📚 References

• 양성봉(2022),'파이썬과 함께하는 자료구조의 이해[개정판]', 생능출판, pp.61-75.
• 양태환(2021),'파이썬으로 배우는 자료구조 핵심 원리', 길벗, pp.52-61.