×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형




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


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


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


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



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


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




삽입 과정


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




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


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




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


1) tail->nextnewNode를 보게 한다.

2) newNode->prevtail을 보게 한다. 

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

4) 마지막으로 newNodenextNULL로 설정한다

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


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




삭제 과정


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


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


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


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


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


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



이 코드에서 주의 할 점


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


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







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}
Crocus




출력 과정


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


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


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



반응형