Dummy 노드를 이용한 연결 리스트(Dummy Linked List) 소스코드

- LinkedList.h -

#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;
    int numOfData;
    int(*comp)(LData d1, LData d2);
} LinkedList;
 
typedef LinkedList List;
 
void ListInit(List *plist);
void LInsert(List *plist, LData data);
 
int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);
 
LData LRemove(List *plist);
int Lcount(List *plist);
 
void SetSortRule(List *plist, int(*comp)(LData d1, LData d2));
 
#endif
 
 

- LinkedList.c -

#include <stdio.h>
#include <stdlib.h>
#include "LinkedList.h"
 
void ListInit(List *plist)
{
    plist->head = (Node*)malloc(sizeof(Node)); // head를 생성
    plist->head->next = NULL; // head의 next 즉 dummy 노드를 생성
    plist->comp = NULL; 
    plist->numOfData = 0;
}
 
void FInsert(List *plist, LData data)
{
    Node *newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
    newNode->data = data; // 새 노드에 데이터 저장
 
    newNode->next = plist->head->next; // 새 노드의 next가 dummy 노드가 가리키는 곳을 가리키게 한다
    plist->head->next = newNode; // dummy노드가 newnode를 가리키게 한다.
 
    (plist->numOfData)++; // 데이터 값을 +1한다.
}
 
void SInsert(List *plist, LData data)
{
    Node *newNode = (Node*)malloc(sizeof(Node)); // 새 노드의 생성
    Node *pred = plist->head; // pred는 더미 노드를 가리킴
    newNode->data = data; // 새 노드에 데이터 저장
 
    // 새 노드가 들어갈 위치를 찾기 위한 반복문
    while (pred->next != NULL && plist->comp(data, pred->next->data) != 0)
    {
        pred = pred->next;
 
        newNode->next = pred->next; // 새 노드의 오른쪽을 연결
        pred->next = newNode; // 새 노드의 왼쪽을 연결
 
        (plist->numOfData)++; // 저장된 데이터의 수 하나 증가
    }
}
 
void LInsert(List *plist, LData data)
{
    if (plist->comp == NULL)
    {
        FInsert(plist, data);
    }
    else
        SInsert(plist, data);
}
 
int LFirst(List *plist, LData *pdata)
{
    if (plist->head->next == NULL)
        return FALSE;
    
    plist->before = plist->head;
    plist->cur = plist->head->next;
 
    *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 *rpos = plist->cur;
    LData rdata = rpos->data;
 
    plist->before->next = plist->cur->next;
    plist->cur = plist->before;
 
    free(rpos);
    (plist->numOfData)--;
 
    return rdata;
}
 
int LCount(List *plist)
{
    return plist->numOfData;
}
 
void SetSortRule(List *plist, int(*comp)(LData d1, LData d2))
{
    plist->comp = comp;
}
 
 
 
 

- LinkedListMain.c - 

#include <stdio.h>
#include "LinkedList.h"
 
int main(void)
{
    //리스트 생성 및 초기화
    List list;
    int data;
    ListInit(&list);
 
    //데이터 저장
    LInsert(&list, 11);
    LInsert(&list, 22);
    LInsert(&list, 22);
    LInsert(&list, 33);
    LInsert(&list, 33);
 
    // 저장된 데이터 전체 출력
    printf("현재 데이터의 수 : %d\n", LCount(&list));
 
    if (LFirst(&list, &data))
    {
        printf("%d ", data);
 
        while (LNext(&list, &data))
            printf("%d ", data);
    }
 
    printf("\n\n");
 
    // 숫자 22를 검색하여 모두 삭제
    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;
}