컴공 일기97

Doubly Linked List 구현 예제입니다. 

단방향 연결 리스트 논리만 잘 숙지하고 있으면, 양방향은 공짜 :)

#include <stdio.h>

#include <stdlib.h>

typedef struct tagNode

{

    int Data;

    struct tagNode* PrevNode;

    struct tagNode* NextNode;

} Node;

Node* DLL_CreatNode(int NewData)

{

    Node * NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = NewData;

    NewNode->PrevNode = NULL;

    NewNode->NextNode = NULL;

    return NewNode;

}

void DLL_DestroyNode(Node* Node)

{

    free(Node);

}

void DLL_AppendNode(Node** Head, Node* NewNode)

{

    if ((*Head) == NULL)

    {

        *Head = NewNode;

    }

    else

    {

        Node* Tail = (*Head);

        while (Tail->NextNode != NULL)

        {

            Tail = Tail->NextNode;

        }

        Tail->NextNode = NewNode;

        NewNode->PrevNode = Tail;

    }

}

Node* DLL_GetNodeAt(Node* Head, int Location)

{

    Node* Current = Head;

    while (Current != NULL && (--Location) >= 0)

    {

        Current = Current->NextNode;

    }

    return Current;

}

void DLL_RemoveNode(Node** Head, Node* Remove)

{

    if (*Head == Remove)

    {

        *Head = Remove->NextNode;

        if (*Head != NULL)

        {

            (*Head)->PrevNode = NULL;

        }

        Remove->NextNode = NULL;

        Remove->PrevNode = NULL;

    }

    else

    {

        Node* Temp = Remove;

        Remove->PrevNode->NextNode = Temp->NextNode;

        if (Remove->NextNode != NULL)

            Remove->NextNode->PrevNode = Temp->PrevNode;

        Remove->PrevNode = NULL;

        Remove->NextNode = NULL;

    }

}

void DLL_InsertAfter(Node* Current, Node* NewNode)

{

    NewNode->NextNode = Current->NextNode;

    NewNode->PrevNode = Current;

    if (Current != NULL)

    {

        Current->NextNode->PrevNode = NewNode;

    }

        Current->NextNode = NewNode;

}

int DLL_GetNodeCount(Node* Head)

{

    unsigned int Count = 0;

    Node* Current = Head;

    while (Current != NULL)

    {

        Current = Current->NextNode;

        Count++;

    }

    return Count;

}

void PrintReverse(Node* Head)

{

    int Count = 0;

    Node* Current = NULL;

    Count = DLL_GetNodeCount(Head);

    for (int i = 0; i < Count; i++)

    {

        Current = DLL_GetNodeAt(Head, Count - (i+1));

        printf("Reversed List[%d] : %d\n", i, Current->Data);

    }

}

int main()

{

    int i = 0;

    int Count = 0;

    Node* List = NULL;

    Node* NewNode = NULL;

    Node* Current = NULL;

    for (i = 0; i < 5; i++)

    {

        NewNode = DLL_CreatNode(i);

        DLL_AppendNode(&List, NewNode);

    }

    Count = DLL_GetNodeCount(List);

    for (i = 0; i < Count; i++)

    {

        Current = DLL_GetNodeAt(List, i);

        printf("List[%d] : %d\n", i, Current->Data);

    }

    printf("\nInserting 3000 After[2]...\n\n");

    Current = DLL_GetNodeAt(List, 2);

    NewNode = DLL_CreatNode(3000);

    DLL_InsertAfter(Current, NewNode);

    Count = DLL_GetNodeCount(List);

    for (i = 0; i < Count; i++)

    {

        Current = DLL_GetNodeAt(List, i);

        printf("List[%d] : %d\n", i, Current->Data);

    }

    printf("\n");

    PrintReverse(List);

    printf("\nDestroying List...\n");

    Count = DLL_GetNodeCount(List);

    for (i = 0; i < Count; i++)

    {

        Current = DLL_GetNodeAt(List, 0);

        if (Current != NULL)

        {

            DLL_RemoveNode(&List, Current);

            DLL_DestroyNode(Current);

        }

    }

    return 0;

}

[실행결과]

List[0] : 0

List[1] : 1

List[2] : 2

List[3] : 3

List[4] : 4

Inserting 3000 After[2]...

List[0] : 0

List[1] : 1

List[2] : 2

List[3] : 3000

List[4] : 3

List[5] : 4

Reversed List[0] : 4

Reversed List[1] : 3

Reversed List[2] : 3000

Reversed List[3] : 2

Reversed List[4] : 1

Reversed List[5] : 0

Destroying List...