4. 더미노드 있는 연결 리스트(DummyLinkedList)

더미노드란?

유효한 데이터를 지니지 않는 그냥 빈(empty) 노드

처음 추가되는 노드는 무조건 두번째이후의 노드가 되기 때문에

노드를 삽입(추가), 삭제, 조회 할때 일관된 형태로 구성 가능

 

더미노드의 장점

더미노드를 통해서 삽입/삭제/참조가 이루어지기에, 코드가 간결해진다.(첫번째 노드일 경우와 2번째노드 이후의 경우를 안나눠줘도 됨)

더미노드가 있으면 이중 연결리스트에서 head와 tail이 움직일 필요가 없어진다.

전 포스팅에서의 코드

더미노드를 사용하면 위와같은 조건문(if/else)으로, 굳이 case분류를 해주지 않아도 된다

(노드가 0개인가, 1개인가...할 필요 X)

Why? 더미노드가 이미 1개가 만들어져 있기 때문

 

이전 단일 연결리스트와의 차이점 

1. Node구조체 포인터들을 하나의 구조체로 묶음

2. 헤더파일을 정의하고 ADT를 활용하여 연결리스트 구성함

3.이전은 head 포인터로 연결리스트를 구성했다면, 이번엔 더미(Dummy)노드로 구성

4. 새 노드를 연결리스트의 꼬리에 추가하지 않고 머리(더미노드)에 추가함

 

새 노드를 연결리스트의 머리에 추가한다면?

장점: tail 포인터가 불필요함

단점: 역순으로 삽입되어 저장된 순서를 유지하지 못함

새 노드를 연결리스트의 꼬리에 추가한다면?

장점: 순행삽입되어 저장된 순서를 유지함

단점: tail 포인터가 필요함

 

기본 ADT

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE    1
#define FALSE    0

typedef int LData;

typedef struct _node
{
    LData data;
    struct _node * next;
} Node;

typedef struct _linkedList
{
    Node * head; //더미노드
    Node * cur; //참조 및 삭제를 위함
    Node * before; //삭제를 위함(이전의 delNextNode 떠올리기)
    int numOfData; //데이터 개수
} LinkedList;

typedef LinkedList List;

void ListInit(List * plist);//리스트 생성
void FInsert(List * plist, LData data); //데이터 삽입
void SInsert(List * plist, LData data);

int LFirst(List * plist, LData * pdata); //첫번째 데이터 참조 및 순회
int LNext(List * plist, LData * pdata); //첫번째 이후의 데이터 참조 및 순회

LData LRemove(List * plist);
int LCount(List * plist);


#endif

 

각 기능 함수 구현

#include <stdio.h>
#include <stdlib.h>
#include "DLinkedList.h"

void ListInit(List * plist){
    //더미노드 생성후 head포인터로 지정
    plist -> head = (Node*)malloc(sizeof(Node));
    plist -> head -> next = NULL; //더미노드가 가리키는 값이 없으므로 NULL초기화
    plist -> cur = NULL;
    plist -> before = NULL;
    plist -> numOfData = 0;
}

void FInsert(List * plist, LData data){
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;
    newNode -> next = NULL;
    
    //더미노드가 첫 노드이므로 조건문으로 첫 노드일 경우를 나눠줄 필요가 없음
    //생성한 노드는 항상 2번째 이후의 노드가 된다.
    newNode -> next = plist -> head -> next; //기존에 생성한 노드가 있다면 그걸로 next 연결
    plist -> head -> next = newNode; //더미노드는 항상 첫 노드를 가리킴
    (plist -> numOfData++);
}

int LFirst(List * plist, LData * pdata){
    if(plist -> head -> next == NULL)
        return FALSE;
    
    plist -> before = plist -> head; //before는 더미노드를 가리킴
    plist -> cur = plist -> head -> next; //cur는 (더미노드 다음의) 첫 노드를 가리킴
    
    *pdata = plist -> cur -> data;
    
    return TRUE;
}

int LNext(List * plist, LData * pdata){
    if(plist -> cur -> next == NULL)
        return FALSE;
    
    plist -> before = plist -> cur;
    plist -> cur = plist -> cur -> next;
    
    *pdata = plist -> cur -> data;
    return TRUE;
}

LData LRemove(List * plist){
    Node * delNode = plist -> cur;
    
    plist -> before -> next = delNode -> next;
    plist -> cur = plist -> before;
    
    LData removeData = delNode -> data;
    free(delNode);
    (plist -> numOfData)--;
    return removeData;
}


int LCount(List * plist){
    return plist -> numOfData;
}

 

main함수

#include <stdio.h>
#include "DLinkedList.h"


int main(void)
{
    List list;
    int data;
    ListInit(&list);

    FInsert(&list, 11);  FInsert(&list, 11);
    FInsert(&list, 22);  FInsert(&list, 22);
    FInsert(&list, 33);

    printf("현재 데이터 수: %d \n", LCount(&list));

    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        while(LNext(&list, &data))
            printf("%d ", data);
    }
    printf("\n\n");

    //
    if(LFirst(&list, &data))
    {
        if(data == 22)
            LRemove(&list);
        
        while(LNext(&list, &data))
        {
            if(data == 22)
                LRemove(&list);
        }
    }

    //
    printf("현재 데이터 수: %d \n", LCount(&list));

    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        while(LNext(&list, &data))
            printf("%d ", data);
    }
    printf("\n\n");
    return 0;
}