[연결리스트] Doubly Linked List

양방향 연결리스트를 구현하는 방법은 많지만, 개인적으로 head와 tail이라는 dummy node를 할당하여 구현하는 것이 좀 더 이해하기 쉽다고 생각하기 때문에 2개의 dummy node를 두어 구현하고자 한다.

 

1. 헤더 파일

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

// rename
#define TRUE 1
#define FALSE 0

// rename
typedef int Data;

// 노드
typedef struct _node
{
    Data data;
    struct _node *next;
    struct _node *prev;
} Node;

// 연결리스트
typedef struct _DLinkedList
{
    Node *head; // dummy node
    Node *tail; // dummy node
    Node *cur; // 리스트 순회 시 필요한 노드
    int numOfData; // 노드 개수
} DBLinkedList;

// rename
typedef DBLinkedList List;

// ADT
void ListInit(List *plist);
void LInsert(List *plist, Data data);
int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);
int LPrevious(List *plist, Data *pdata);
int LRemove(List *plist);
int LCount(List *plist);

#endif

 

2. ADT 

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

void ListInit(List *plist)
{
    // dummy node 생성
    plist->head = (Node *)malloc(sizeof(Node));
    plist->tail = (Node *)malloc(sizeof(Node));

    // head의 next, prev 설정
    plist->head->next = plist->tail;
    plist->head->prev = NULL;

    // tail의 next, prev 설정
    plist->tail->next = NULL;
    plist->tail->prev = plist->head;

    // 노드 0개
    plist->numOfData = 0;
}

void LInsert(List *plist, Data data)
{
    // 새로운 노드 생성
    Node *newNode = (Node *)malloc(sizeof(Node));

    // 새로운 노드 설정
    newNode->data = data;
    newNode->prev = plist->tail->prev;
    newNode->next = plist->tail;
    
    // 새로운 노드 연결
    plist->tail->prev->next = newNode;
    plist->tail->prev = newNode;

    // 노드 개수 증가
    (plist->numOfData)++;
}

int LFirst(List *plist, Data *pdata)
{
    if (plist->head->next == plist->tail)
    {
        // 노드 0개
        return FALSE;
    }

    // 현재 참조하고 있는 노드 설정
    plist->cur = plist->head->next;
    *pdata = plist->cur->data;

    return TRUE;
}

int LNext(List *plist, Data *pdata)
{
    if (plist->cur->next == plist->tail)
    {
        // 더 이상 순회할 노드가 없다.
        return FALSE;
    }

    // 다음 노드 설정
    plist->cur = plist->cur->next;
    *pdata = plist->cur->data;

    return TRUE;
}

int LPrevious(List *plist, Data *pdata)
{
    if (plist->cur->prev == plist->head)
    {
        // 더 이상 순회할 노드가 없다.
        return FALSE;
    }

    // 이전 노드 설정
    plist->cur = plist->cur->prev;
    *pdata = plist->cur->data;

    return TRUE;
}

int LRemove(List *plist)
{
    // 삭제할 노드 따로 저장
    Node *rpos = plist->cur;
    Data ret = rpos->data;

    // 노드 삭제
    rpos->prev->next = rpos->next;
    rpos->next->prev = rpos->prev;

    // 현재 참조하고 있는 노드 설정
    plist->cur = plist->cur->prev;

    // 메모리 없애기
    free(rpos);
    
    // 노드 개수 감소
    (plist->numOfData)--;

    return ret;
}

int LCount(List *plist)
{
    // 노드 개수
    return plist->numOfData;
}

 

3. main 함수

#include <stdio.h>
#include "DBLinkedList.h"
#include "DBLinkedList.c"

int main()
{
    // 지역 변수
    List list;
    int data;

    // 리스트 초기화
    ListInit(&list);

    // 삽입
    LInsert(&list, 1); // 1
    LInsert(&list, 2); // 1 2
    LInsert(&list, 3); // 1 2 3
    LInsert(&list, 4); // ...
    LInsert(&list, 5);
    LInsert(&list, 6);
    LInsert(&list, 7);
    LInsert(&list, 8);

    // 리스트 출력
    if (LFirst(&list, &data))
    {
        printf("%d ", data);

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

    // 2의 배수인 노드 삭제
    if (LFirst(&list, &data))
    {
        if (data % 2 == 0)
        {
            LRemove(&list);
        }
        while (LNext(&list, &data))
        {
            if (data % 2 == 0)
            {
                LRemove(&list);
            }
        }
    }

    // 리스트 출력
    if (LFirst(&list, &data))
    {
        printf("%d ", data);

        while (LNext(&list, &data))
            printf("%d ", data);
    }

    return 0;
}