자료구조 5강 원형 연결리스트의 이해와 소스 코드

단순 연결리스트를 꼭 처음부터 끝까지 스스로 구현할 수 있지 않아도 되며, ADT의 변경 및 추가로 함수의 일부를 변경하거나 추가하는 정도를 할 수 있다면 충분히 공부했다고 말할 수 있다.

원형 연결리스트

단순 연결리스트의 마지막 노드는 NULL을 가르켰지만, 이 마지막 노드가 첫 번째 노드를 가리키게 하면 그것이 '원형 연결리스트'.

단순 연결리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다는 것이 원형 연결리스트의 장점.

즉, 꼬리를 가리키는 포인터 변수는 'tail', 머리를 가리키는 변수는 'tail->next' 관계가 성립됨.

코드 구현

// CLinkedList.h
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE        1
#define FALSE       0

typedef int Data;

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

typedef struct _CLL
{
    Node * tail;
    Node * cur;
    Node * before;
    int numOfData;
} CList;

typedef CList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);          // 꼬리에 노드를 추가
void LInsertFront(List * plist, Data data);     // 머리에 노드를 추가

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);

#endif

// CLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"

void ListInit(List * plist)
{
    plist->tail = NULL;
    plist->cur = NULL;
    plist->before = NULL;
    plist->numOfData = 0;
}

void LInsertFront(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    if(plist->tail == NULL)
    {
        plist->tail = newNode;
        newNode->next = newNode;
    }
    else
    {
        newNode->next = plist->tail->next;
        plist->tail->next = newNode;
    }
    (plist->numOfData)++;
}

void LInsert(List * plist, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    if(plist->tail == NULL)
    {
        plist->tail = newNode;
        newNode->next = newNode;
    }
    else 
    {
        newNode->next = plist->tail->next;
        plist->tail->next = newNode;
        plist->tail = newNode;
    }
    (plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if(plist->tail == NULL)
        return FALSE;

    plist->before = plist->cur;
    plist->cur = plist->cur->next;

    *pdata = plist->cur->data;
    return TRUE;       
}

int LNext(List * plist, Data * pdata)
{
    if(plist->tail == NULL)
        return FALSE;

    plist->before = plist->cur;
    plist->cur = plist->cur->next;

    *pdata = plist->cur->data;
    return TRUE;
}

Data LRemove(List * plist)
{
    Node * rpos = plist->cur;
    Data rdata = rpos->data;

    if(rpos == plist->tail)
    {
        if(plist->tail == plist->tail->next)
            plist->tail = NULL;
        else
            plist->tail = plist->before;
    }

    plist->before->next = plist->cur->next;
    plist->cur = plist->before;

    free(rpos);
    (plist->numOfData)--;
    return rdata;
}

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

// CLinkedListMain.c
#include <stdio.h>
#include "CLinkedList.h"

int main(void)
{
    // 원형 연결 리스트의 생성 및 초기화 ////////
    List list;
    int data, i, nodeNum;
    ListInit(&list);

    LInsert(&list, 3);
    LInsert(&list, 4);
    LInsert(&list, 5);
    LInsertFront(&list, 2);
    LInsertFront(&list, 1);

    // 리스트에 저장된 데이터를 연속 3회 출력 ///////
    if(LFirst(&list, &data))
    {
        printf("%d ", data);

        for(i = 0; i < LCount(&list)*3-1; i++)
        {
            if(LNext(&list, &data))
                printf("%d ", data);
        }
    }
    printf("\n");

    nodeNum = LCount(&list);
    
    if(nodeNum != 0)
    {
        LFirst(&list, &data);
        if(data%2 == 0)
            LRemove(&list);

        for(i = 0; i < nodeNum-1; i++)
        {
            LNext(&list, &data);
            if(data%2 == 0)
                LRemove(&list);
        }
    }

    if(LFirst(&list, &data))
    {
        printf("%d ", data);

        for(i = 0; i < LCount(&list)-1; i++)
        {
            if(LNext(&list, &data))
                printf("%d ", data);
        }
    }
    return 0;
}

실행 결과

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 3 5

양방향 연결 리스트(doubly linked list, = 이중 연결리스트)

왼쪽 노드가 오른쪽 노드를 가리키고 오른쪽 노드도 왼쪽 노드를 가리키는 양방향 연결구조 리스트.

양방향 연결 리스트이면서 원형 연결 리스트의 구조를 동시에 지니는 리스트도 존재한다.

// DBDLinkedList.h
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct _DLinkedList
{
    Node * head;
    Node * cur;
    int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List *plist);
void LInsert(List *plist, Data data);      // 꼬리에 노드를 추가
void LInsertFront(List *plist, Data data); // 머리에 노드를 추가

int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);
Data LRemove(List *plist);
int LCount(List *plist);

#endif



// DBDLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "DBDLinkedList.h"

void ListInit(List * plist)
{
    plist->head = (Node*)malloc(sizeof(Node));
    plist->tail = (Node*)malloc(sizeof(Node));

    plist->head->prev = NULL;
    plist->head->next = plist->tail;

    plist->tail->next = NULL;
    plist->tail->prev = plist->head;

    plist->numOfData = 0;
}

void LInsert(List *plist, Data data)
{
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;

    newNode->prev = plist->tail->prev;
    plist->tail->prev->next = newNode;

    newNode->next = plist->tail;
    plist->tail->prev = newNode;

    (plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if (plist->head->next == plist->tail)
        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->head->next;
    *pdata = plist->cur->data;

    return TRUE;
}

int LRemove(List * plist)
{
    Node * rpos = plist->cur;
    Data remv = rpos->data;

    plist->cur->prev->next = plist->cur->next;
    plist->cur->next->prev = plist->cur->prev;

    plist->cur = plist->cur->prev;

    free(rpos);
    (plist->numOfData)--;;
    return remv;
}

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

// DBDLinkedListMain.c
#include <stdio.h>
#include "DBDLinkedList.h"

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

    // 8개의 데이터 저장 ///////
    LInsert(&list, 1); LInsert(&list, 2);
    LInsert(&list, 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);

        printf("\n\n");
    }

    return 0;
}

실행 결과

1 2 3 4 5 6 7 8 
1 3 5 7