이중 연결 리스트(Double Linked List) 개념

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

단일 연결 리스트와는 다르게 Node가 앞, 뒤로 서로 연결되어 있는 모습을 취하게 된다.

이 과정에서 단일 연결 리스트에 비해 조금 코드가 늘어나기는 하지만, 

이전 게시물의 연결 리스트를 정확히 이해 하고 있다면 별로 어렵지 않을 것이라 생각된다.

이중 연결리스트의 알고리즘은 다음과 같다.

초기화 상태로는 head와 tail이 NULL을 가리키는 상태로 시작한다.

삽입 과정

처음 삽입 시 head와 tail이  처음 생긴 노드를 가리키게 된다.

그리고 (head 또는 tail)->next 및 (head 또는 tail)->prev = NULL을 가리키도록 한다.

(이때 head->prev이나 tail->prev이나 모두 같다.(노드가 한 개뿐이니))

그다음 2개 이상의 노드가 생길 때 부터는 다음과 같은 과정을 이행한다.

1) tail->next가 newNode를 보게 한다.

2) newNode->prev가 tail을 보게 한다. 

3) tail이 이동하여 newNode를 보도록 한다. 

4) 마지막으로 newNode의 next는 NULL로 설정한다. 

계속 이 작업을 반복하며 삽입한다.

이 과정은 그림으로 표현하면 다음과 같다.

삭제 과정

삭제 부분 또한 앞, 뒤 삭제두가지 과정이 존재하는데 앞에서 부터의 삭제 과정만 설명하겠다. 

뒤에서 부터 삭제 과정은 앞에서 부터 삭제와 방향만 다르다.

 앞에서 삭제는 cur->next가 NULL이 아니면 즉, 노드가 2개 이상이라는 것 이므로 

cur->next->prev가 처음 노드가 될 것이니 NULL이 되도록 하고,

 head = cur->next를 보게 한뒤, 현재 cur이 가리키고 있던 노드를 삭제한다.

( 연습장을 펴서 그림을 그려보자. 자료구조는 보고 있을때는 이해가 되지만, 직접 작성하려 하면 쉽게 되지 않는다. 직접 그려보는 것이 좋다. ) 

이 코드에서 주의 할 점

이전 단일 리스트 게시물 처럼 삽입 시 오름차순으로 자동 정렬을 하는 기능이 포함되어있다.

만약 정렬 기능을 없애고 싶다면 아래 코드를 삭제하면 된다.

Node *tmp = head;
Node *tmp_1 = head->next;
while (tmp != tail->next)
{
    int swap;
 
    while(tmp_1 != tail->next)
    {
        if (tmp->data > tmp_1->data)
        {
            swap = tmp->data;
            tmp->data = tmp_1->data;
            tmp_1->data = swap;
        }
 
        tmp_1 = tmp_1->next;
 
    }
 
    tmp = tmp->next;
 
    if(tmp != NULL) // 설명 부연 하기
    tmp_1 = tmp->next;
}

출력 과정

출력 과정은 위의 과정만 이해한다면 이해 할 수 있으므로 많은 설명은 생략한다.

출력 부분은 앞에서부터 출력은 tail->next 즉, NULL이 아닐 때 까지 반복이고,

뒤에서부터 출력은 head->prev 즉, NULL이 아닐 때 까지 반복하여 출력하도록 한다.