이중연결리스트(Doubled Linked-List) 구현

이중연결리스트 (Doubled Linked-List) 란? 

 

 

이중연결리스트는 각 노드가 두 개의 레퍼런스(prev, next)를 가지고 각가 이전 노드와 다음 노드를 가리키는 연결리스트를 구현한 자료구조이다.

 

이중연결리스트는 단순연결리스트의 단점인

 

1. 역방향으로는 노드 탐색 불가능

2. 삽입/삭제시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아야함(이전노드 탐색 시간 걸림)

 

을 보완하기 위해 나왔다. 

But, 노드마다 2개의 레퍼런스(prev, next)를 저장해야 한다는 단점이 있다. 

 

 

 

기본 구조

 

head - 첫번째 노드가 무엇인가를 의미하는 정보이다.

tail - 마지막 노드가 무엇인가를 의미하는 정보이다.

node - 아이템과 레퍼런스 2개를 가진다.

item - 항목으로 데이터값이 저장된다.

prev - 메모리 주소를 의미하며 이전 노드의 위치를 알려준다. 

next - 메모리 주소를 의미하며 다음 노드의 위치를 알려준다. 

 

 

 

구현

 

 

1. 초기 생성

head와 tail 에 각각 item은 저장하지 않은 새로운 노드를 가리키게 한다. 

그 후 head.next로 tail가 가리키고 있는 노드를 가리키고, tail.prev로 head가 가리키고 있는 노드를 가리키면 초기 이중연결리스트 구조가 만들어진다. 아래 코드에서 DList의 생성자 부분이다. 

 

 

 

2. 삽입(특정 노드 뒤에)

n이 삽입하고자 하는 새로운 노드를 가리키고 있고, head가 가리키고 있는 노드 뒤에 노드를 삽입하기로 가정해보자.

① n.prev, n.next를 각각 head가 가리키고 있는 노드, head.next이 가리키고 있는 노드(tail이 가리키고 있는 노드)를 가리키게 하고, ② tail.prev로 n을 가리키고, ③ head.next를 n을 가리키면 head뒤에 n노드가 삽입되게 된다. 

 

여기서 중요한 점은 ③을 ①(오른쪽 화살표),②보다 먼저 수행하면, head.next가 달라지게 되므로 기존의 head.next로 가리키고 있던 tail의 위치를 알 방법이 없다. 따라서, head.next는 마지막에 변경해야한다.

 

아래 코드에서 insert_after(s.head, 'apple')이다. 

 

 

 

3. 삽입(특정 노드 이전에)

 

n이 삽입하고자 하는 새로운 노드를 가리키고 있고, tail이 가리키고 있는 노드 이전에 노드를 삽입하기로 가정해보자.

① n.prev, n.next를 각각 tail.prev가 가리키고 있는 노드, tail이 가리키고 있는 노드를 가리키게 하고,

② tail.prev.next로 n을 가리키고, ③ tail.prev를 n을 가리키면 tail노드 이전에 n노드가 삽입되게 된다. 

 

여기서 중요한 점은 ③을 ①(왼쪽 화살표),②보다 먼저 수행하면, tail.prev가 달라지게 되므로 기존의 tail.prev로 가리키고 있던 apple노드의 위치를 알 방법이 없다. 따라서, tail.prev는 마지막에 변경해야한다.

 

아래 코드에서 insert_before(s.tail, 'orange')이다. 

 

 

 

4. 삭제

먼저, 레퍼런스로 삭제하고자 하는 노드를 가리킨다. 레퍼런스 c라고 가정해보자.

c를 가리키고 있는 노드를 삭제하기 위해서는 해당노드의 이전노드.next로 c.next.next를 가리키고, 해당노드의 다음노드.prev로 c.prev를 가리킨다. 아래 코드에서 delete(2)이다. 

 

 

 

 

코드

class DList:
    
    class Node:
        def __init__(self, item, prev, next): # 노드 생성자
            self.item = item # 데이터
            self.prev = prev # 이전 노드 레퍼런스
            self.next = next # 다음 노드 레퍼런스
            
    def __init__(self): # 이중연결리스트 생성자
        # head, tail, 항목수로 구성
        # 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 isEmpty(self):
        return self.size == 0
    
    def insert_before(self, p, item): # p가 가리키는 노드 앞에 새로운 노드 삽입
        t = p.prev
        n = self.Node(item, t, p)
        t.next = n 
        p.prev = n
        self.size += 1
        
    def insert_after(self, p, item): # p가 가리키는 노드 뒤에 새로운 노드 삽입
        t = p.next
        n = self.Node(item, p, t)
        t.prev = n
        p.next = n
        self.size += 1

    def delete(self, x) : # 노드x 삭제
        c = self.head.next
        for _ in range(x):
            c = c.next
        c.next.prev = c.prev
        c.prev.next = c.next
        self.size -= 1
        
    def print_list(self): # 출력
        if self.isEmpty():
            return "비어있습니다"
        else:
            c = self.head.next
            while c != self.tail :
                if c.next != self.tail:
                    print(c.item, '=>', end='')
                else :
                    print(c.item)
                c = c.next

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()

s.delete(2)
s.print_list()
s.delete(1)
s.print_list()