[자료구조와 STL] 17. list 만들기 – 더미 노드없는 이중 연결 리스트

3. 2 list 만들기 – 더미 노드없는 이중 연결 리스트

 

 이번에는 더미노드가 없는 이중 연결 리스트를 만들어 봅시다. 더미노드가 없는 이중 연결 리스트에도 node의 정의나 iterator의 정의는 차이가 없습니다. 여기에서는 차이가 있는 부분만 언급하겠습니다.

 

 먼저, list를 생성했을 때의 초기 모습이 다를 것입니다.

 

[그림 12] 더미노드 없는 이중 연결 리스트 초기화 모습

 

list()

{

    head = tail = 0;

    bsize = 0;

}

 

 생성자 메서드 외에 차이가 있는 부분은 노드를 매다는 hang_node와 노드의 연결을 끊는 dehang_hode와 시작 iterator를 반환하는 begin, 마지막 iterator를 반환하는 end가 있습니다.

 

 hang_node 메서드에서는 보관된 자료가 없을 때, 맨 앞에 매달 때, 중간에 매달 때, 맨 뒤에 매달 때 논리가 서로 다릅니다. 중간에 매달 때는 더미 노드 있는 이중 연결 리스트에서 매다는 논리와 같으므로 설명을 생략하겠습니다.

 

 보관된 자료가 없을 때에는 인자로 전달된 now가 가리키는 노드의 위치 정보를 head와 tail이 가리키게 해야겠지요.

 

head = tail = now;

[그림 13] 아무것도 없을 때 보관 전 후 모습

 

 맨 앞에 매달 때에는 head가 가리키는 노드 앞에 입력 인자로 전달된 now 노드를 매달아야 합니다. 이를 위해서는 now가 가리키는 노드의 next 링크가 현재의 head가 가리키는 노드를 가리켜야 할 것입니다. 그리고 현재 head가 가리키는 노드의 prev 링크는 now를 가리켜야겠지요. 마지막으로 head를 now로 변경해 주어야 할 것입니다.

 

now->next = head; //새로운 노드의 next에 head를 대입

head->prev = now; //head가 가리키는 노드의 prev를 now로 변경

head = now; //head를 새로운 노드 위치 정보로 변경

 

[그림 14] 맨 앞에 매달 때

 

 맨 뒤에 매달 때에는 tail이 가리키는 노드 뒤에 입력 인자로 전달된 now 노드를 매달아야 합니다. 이를 위해서는 now가 가리키는 노드의 prev 링크를 tail이 가리키는 노드를 가리키게 해야겠지요. 그리고 tail이 가리키는 노드의 next 링크를 now를 가리키게 해야 할 것입니다. 그리고 tail을 now로 변경해 주어야겠지요.

 

tail->next = now; //tail이 가리키는 노드이 next를 now로 변경

now->prev = tail; //새로운 노드의 prev에 tail을 대입

tail = now; //tail을 새로운 노드의 위치 정보로 변경

[그림 15] 맨 뒤에 매달 때

 

 이처럼 각 경우를 판단하여 상황에 맞는 코드를 작성해야 합니다.

 

 그런데 hang_node 메서드 내에서 어떠한 경우인지를 어떻게 판단을 해야 할까요? 각각의 경우에 노드를 매달기 전후의 모습을 그리고 난 후에 차이를 비교하시기 바립니다.

 

 아무것도 보관된 것이 없을 때 보관을 할 때나 맨 뒤에 보관할 때는 pos가 0이 오고 맨 앞에 매달거나 중간에 매달 때에는 pos가 0이 아닙니다. 그리고 pos가 0이면서 head도 0이면 아무것도 보관된 것이 없을 때 보관하는 경우이고 pos가 0이면서 head가 0이 아닌 경우는 맨 뒤에 보관해야 하는 경우입니다. 또한, pos가 0이 아니면서 head와 pos가 같으면 맨 앞에 보관하는 경우이고 같지 않다면 중간에 매다는 경우입니다.

 

if(pos){

    if(pos == head) { //맨 앞에 매달 경우 }

    else { //중간에 매달 경우 }

}

else

{

    if(pos == head) { //아무것도 없을 때 처음으로 매달 경우 }

    else { //맨 뒤에 매달 경우 }

}

 

 erase 메소드에서는 더미 노드가 있는 이중 연결 리스트와 마찬가지로 노드의 연결을 끊고 난 후에 노드를 소멸해야 할 것입니다. 차이가 있는 것은 노드의 연결을 끊는 dehang_node입니다.

 

 더미 노드가 없는 이중 연결 리스트에서는 dehang_node에서는 연결을 끊어야 하는 노드의 prev나 next 링크가 0을 가리키는 경우가 발생합니다. 만약, 끊어야 할 노드가 prev가 없는 경우는 맨 앞 노드를 끊어야 하는 경우이기 때문에 prev 링크가 0입니다. 그리고 끊어야 할 노드가 next가 없는 경우는 맨 뒤 노드를 끊어야 하는 경우이기 때문에 next 링크가 0입니다. 이를 고려하여 작성해야 합니다.

 

if(pos->prev) //pos의 이전 노드가 있다면

{

    //pos의 이전 노드의 next를 pos의 next로 변경

    pos->prev->next = pos->next;

}

else //pos의 이전 노드가 없다면 , pos가 head임

{

    head = head->next; //head를 head의 다음 노드 위치 정보로 변경

}

if(pos->next) //pos의 다음 노드가 있다면

{

    //pos의 다음 노드의 prev를 pos의 prev로 변경

    pos->next->prev = pos->prev;

}

else //pos의 다음 노드가 없다면, pos가 tail임

{

    tail = tail->prev; //tail을 tail의 이전 노드 위치 정보로 변경

}

 

 그리고 더미 노드가 없는 경우에는 head가 가리키는 노드부터 자료가 보관된 노드이고 tail이 가리키는 노드도 자료가 보관된 노드입니다. 이에 begin 메서드와 end 메서드도 변경해 주어야 할 것입니다.

 

iterator begin()

{

    //더미 노드가 없으므로 맨 앞에 보관된 요소의 노드를 head가 가리키고 있음

    return head; //head를 반환(node *를 반복자로 묵시적 형변환)

}

iterator end()

{

     //더미 노드가 없으므로 맨 뒤에 보관된 노드의 다음 위치는 tail의 next이므로 0임

    return 0; //0을 반환(node *를 반복자로 묵시적 형변환)

}

 리스트를 사용하는 방법은 벡터와 비슷합니다. 리스트에서는 인덱스 연산자와 capacity 메서드를 제공하지 않지만 그 외에 다른 메서드는 벡터처럼 제공하고 있으며 사용하는 관점에서 논리적인 의미는 같기 때문에 사용 방법이 비슷합니다. 벡터를 이용하는 프로그램을 다시 한 번 리스트를 이용하여 만들어 보세요.

 

 6장과 7장에서는 벡터와 리스트 그리고 5장에서 다루는 맵을 동시에 사용하는 응용을 설계하고 구현해 볼 것이므로 미리 한 번 살펴보는 것도 학습에 도움이 될 수 있습니다.