이중연결리스트

정의 : 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트

 

핵심은 노드와 노드가 서로 연결되어 있다는 점이다. 아래 그림을 보면 단순 연결 리스트(linked list)와는 다르게 노드가 이전 노드(previous)와 다음 노드(next)로 구성되어 있다.

이것의 가장 큰 장점은 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다는 것이다.

 

 

https://blog.naver.com/holy_joon/221583745847

 

삽입 구현 과정

다음과 같이 head와 tail 노드만 존재하고 있을 때, 새로운 데이터를 가진 노드(new)를 넣고 싶다면

 

1. tail의 Llink가 가리키는 노드의 Rlink가 new를 가리키게 한다. (tail->Rlink->Rlink = new)

2. newnode의 Llink를 tail의 Llink가 기리키는 노드를 가리키게 한다. (newnode->Llink = tail->Llink)

3. tail의 Llink를 newnode를 가리키게 한다. (tail->Llink = newnode)

4. newnode의 Rlink를 tail를 가리키게 한다. (newnode->Rlink = tail)

 

의 순서로 뒤로부터 넣을 수 있다.

 

이것을 코드로 구현하면 아래와 같다.

# 노드 선언(3가지 속성을 지님)
class Node:
    def __init__(self, data):
        self.llink = None
        self.data = data
        self.rlink = None

# 주어진 연결 리스트의 내용을 출력
def print_list(head):
    p = head
    while p.rlink is not None:
        print(f"{p.data}-->", end="")
        p = p.rlink
    print(p.data)

# 이중 연결 리스트의 머리(head)와 꼬리(tail)를 초기화
def init():
    head = Node(0)
    tail = Node(0)

    head.rlink = tail
    head.llink = head
    tail.rlink = tail
    tail.llink = head

    return head, tail

# 연결 리스트의 끝에 새로운 노드를 추가
def push_back(tail, value):
    new_node = Node(value)
    p = tail
    p.llink.rlink = new_node
    new_node.llink = p.llink
    p.llink = new_node
    new_node.rlink = p

#main 함수
def main():
    head, tail = init()
    push_back(tail, 10)
    push_back(tail, 30)
    push_back(tail, 50)
    print_list(head)

if __name__ == "__main__":
    main()

 

삭제 구현 과정

1. 삭제 할 노드(delnode)의 Llink가 가리키는 노드의 Rlink를 delnode의 Rlink가 가리키는 노드를 가리키게 한다.

(delnode->Llink->Rlink = delnode->Rlink)

2. delnode의 rlink가 가리키는 노드의 Llink를 delnode의 Llink가 가리키는 노드를 가리키게 한다.

(delnode->Rlink->Llink = delnode->Llink)

3. 삭제된 노드의 메모리를 해제한다. (free)

def remove_node(head, tail, value):
    p = head.rlink
    while p.rlink != tail:
        if p.data == value:
            p.rlink.llink = p.llink
            p.llink.rlink = p.rlink
            del p
            return
        p = p.rlink

 

삽입에 비해 비교적 어렵지 않아서 편하다.

 

장점

1. 메모리를 동적으로 할당하여 메모리를 절약할 수 있고 삽입, 삭제가 간단하다.(단일 연결리스트가 배열과 비교했을 때 갖는 장점을 동일하게 갖는다.)
2. 단일 연결리스트에 비해 접근이 빠르다.
   1. 빅오 표기법으로는 단일 연결리스트와 이중 연결리스트 모두 O(N)이기는 하다.
   2. 하지만 이는 최악의 상황을 가정한 것이고 만약 노드가 1,000개인데 900번째 노드에 접근하려고 한다면 이중 연결리스트는 tail에서 부터 접근하여 100번의 이동을, 단일 연결리스트는 900번의 이동을 해야한다.

 

단점

1. 배열과 비교했을 때 접근이 느리다.
   1. 단일 연결리스트에 비해 접근이 빠르지만 배열과 비교했을 때는 여전히 head or tail로 접근을 시작해 순차적으로 접근해야 해서 비교적 속도가 느리다.
2. 단일 연결리스트에 비해 구현이 복잡하다. 별도로 tail 변수가 필요하며 양방향의 연결을 구현해야 하기에 추가, 삭제 연산이 복잡하다.
3. 데이터의 개수가 많아질 수록 접근 연산이 복잡해지고 그에 따라 장접이던 빠른 삽입, 삭제 연산이 느려진다.

 

시간복잡도 비교

	이중연결리스트	연결리스트	배
접근	O(N)	O(N)	O(1)
검색	O(N)	O(N)	O(N)
삽입	O(1)	O(1)	O(N)
삭제	O(1)	O(1)	O(N)