[Data Structure] 4. Doubly Linked List

특징

1. 헤더 노드로의 순환구조
   

   • 더미노드인 헤더노드만 존재할 경우 헤더노드의 pRLink와 pLLink는 NULL이 아닌 헤더노드 자신을 가리킴
   • 원소 추가 시 첫 노드의 pLLink와 마지막 노드의 pRLink는 헤더노드를 가리킴

장점

1. 헤더 노드로부터 첫 노드 및 마지막 노드 접근 용이
   • 찾고자 하는 노드의 위치가 current element count / 2 보다 클 경우 pLLink를 따라 순회하고, 작을 경우 pRLink를 따라 순회할 시 빠르게 접근 가능

단점

1. 동적 할당, 포인터 연산 등으로 구현과 관리가 어려움
2. 포인터의 사용으로 저장 공간의 낭비가 있음(pRLink, pLLink 사용)

구현

1. circularlist.c

#include "doublylist.h"

DoublyList *createDoublyList(void)
{
    DoublyList *new;

    new = malloc(sizeof(DoublyList));
    if (!new)
        return (NULL);
    new->currentElementCount = 0;
    new->headerNode.pLLink = &new->headerNode; // 헤더노드의 pLLink를 헤더노드에 연결
    new->headerNode.pRLink = &new->headerNode; // 헤더노드의 pRLink를 헤더노드에 연결
    return (new);
}

int addDLElement(DoublyList *pList, int position, DoublyListNode element)
{
    DoublyListNode *new;
    DoublyListNode *prev;

    if(!pList || position < 0 || position > pList->currentElementCount) // 에러 처리
        return (FALSE);
    new = malloc(sizeof(DoublyListNode)); // 새 노드 할당
    if (!new)
        return (FALSE);
    *new = element; // 정보 저장
    prev = &pList->headerNode; // 직전 노드 헤더노드로부터 탐색하기 위해 임시 저장
    for (int i = 0; i < position; i++) // 삽입 위치 직전까지 prev 이동
        prev = prev->pRLink;
    new->pRLink = prev->pRLink; // 삽입 노드의 pRLink에 직전 노드의 pRLink 연결
    new->pLLink = prev; // 삽입 노드의 pLLink에 직전 노드 연결
    prev->pRLink->pLLink = new; // 직전 노드의 다음 노드(prev->pRLink)의 pLLInk에 삽입 노드 연결
    prev->pRLink = new; // 직전 노드의 pRLink에 삽입 노드 연결
    pList->currentElementCount++; // 현재 원소 개수 갱신
    return (TRUE);
}

int removeDLElement(DoublyList* pList, int position)
{
    DoublyListNode *remove;

    if (!pList || position < 0 || position >= pList->currentElementCount) // 에러 처리
        return (FALSE);
    remove = getDLElement(pList, position); // 제거 노드 반환
	remove->pRLink->pLLink = remove->pLLink; // 제거 노드의 다음 노드(remove->pRLink)의 pLLink에 제거노드의 pLLink 연결
	remove->pLLink->pRLink = remove->pRLink; // 제거 노드의 이전 노드(remove->pLLink)의 pRLink에 제거노드의 pRLink 연결
	free(remove); // 제거 노드 할당 해제
    pList->currentElementCount--; // 현재 원소 개수 갱신
    return (TRUE);
}

DoublyListNode *getDLElement(DoublyList *pList, int position)
{
    DoublyListNode *res;

    if (!pList || position < 0 || position >= pList->currentElementCount) // 에러 처리
        return (FALSE);
    res = &pList->headerNode; // 반환값 헤더노드부터 탐색하기 위해 헤더노드 임시 저장
    if (pList->currentElementCount / 2 > position) // 현재 원소 개수 / 2 값보다 찾고자 하는 노드의 위치가 작을 경우 첫 노드 방향(pRLink)으로 position만큼 순회
    {
        for (int i = 0; i <= position; i++)
            res = res->pRLink;
    }
    else // 현재 원소 개수 / 2 값보다 찾고자 하는 노드의 위치가 크거나 같을 경우 마지막 노드 방향(pLLink)으로 현재 원소 개수 - position만큼 순회
    {
        for (int i = 0; i < pList->currentElementCount - position; i++)
            res = res->pLLink;
    }
    return (res);
}

int getDoublyListLength(DoublyList *pList)
{
    return (pList->currentElementCount);
}

void displayDoublyList(DoublyList *pList)
{
    DoublyListNode	*cur;
    int				i;

    if (!pList) // 에러 처리
    {
        printf("No List\n");
        return ;
    }
    printf("(1) Current Element count: %d\n", pList->currentElementCount);
    if (pList->currentElementCount == 0)
        printf("(2) Element: No Element\n\n");
    else
	{
		printf("(2) Element\n");
		cur = pList->headerNode.pRLink;
		for (i = 0; i < pList->currentElementCount; i++)
		{
			printf("[%d]: %d", i, cur->data);
			if (i != pList->currentElementCount - 1) // 마지막 노드 제외 쉼표 출력
				printf(", ");
			cur = cur->pRLink;
		}
		printf("\n\n");
	}
}

void clearDoublyList(DoublyList* pList)
{
    DoublyListNode* node;
    DoublyListNode* tmp;

    if (pList->currentElementCount == 0)
        return ;
    node = pList->headerNode.pRLink;
    while (node != &pList->headerNode) // node가 헤더노드로 돌아오기 전까지
    {
        tmp = node->pRLink; // 현재 노드의 다음 노드 저장을 위한 임시 변수
        free(node); // 현재 노드 할당 해제
        node = tmp; // 이전에 저장해 놓은 임시 변수 값을 가져와 연속적으로 리스트 순회
    }
    node->pRLink = &pList->headerNode; // node가 헤더노드로 돌아왔기 때문에 그 노드의 pLList 헤더노드로 연결
    node->pLLink = &pList->headerNode; // node가 헤더노드로 돌아왔기 때문에 그 노드의 pRList 헤더노드로 연결
    pList->currentElementCount = 0; // 현재 원소 개수 갱신
}

void deleteDoublyList(DoublyList *pList)
{
    clearDoublyList(pList); // clear를 통해 리스트 내부 모든 노드 할당 해제
    free(pList); // 리스트 구조체 할당 해제
}

2. circularlist_main.c

#include "doublylist.h"

int main(void)
{
    DoublyList		*pList;
    DoublyListNode	*node;
    DoublyListNode	DoublyListNode;
    int             loop;
    int             opt;
	int				position;

    pList = NULL;
    while (loop)
    {
        printf("[1] Create [2] Add [3] Remove [4] Get Element [5] Length [6] Display [7] Clear [8] Delete [9] Exit ");
        scanf("%d", &opt);
        switch (opt)
        {
            case 1:
                pList = createDoublyList();
                if (pList)
                    printf("Create Doubly List: Success\n");
                else
                    printf("Create Doubly List: Failed\n");
                break;
            case 2:
                printf("Position: ");
                scanf("%d", &position);
                printf("Data: ");
                scanf("%d", &DoublyListNode.data);
                if (addDLElement(pList, position, DoublyListNode))
                {
                    printf("Add: Success\n");
                    displayDoublyList(pList);
                }
                else   
                    printf("Add: Failed\n\n");
                break;
            case 3:
                printf("Position: ");
                scanf("%d", &position);
                if (removeDLElement(pList, position))
                {
                    printf("Remove: Success\n");
                    displayDoublyList(pList);
                }
                else 
                    printf("Remove: Failed\n\n");
                break;
            case 4:
                printf("Position: ");
                scanf("%d", &position);
                node = getDLElement(pList, position);
                if (node)
                    printf("[%d]: %d\n", position, node->data);
                else
                    printf("Failed\n");
                break;
            case 5:
                printf("Length: %d\n", getDoublyListLength(pList));
                break;
            case 6:
                displayDoublyList(pList);
                break;
            case 7:
                if (!pList)
                    printf("Clear: Failed\n\n");
                else
                {
                    clearDoublyList(pList);
                    printf("Clear: Success\n");
                }
                break;
            case 8:
                if (!pList)
                    printf("Delete: Failed\n");
                else
                {
                    deleteDoublyList(pList);
                    pList = NULL;
                    printf("Delete: Success\n");
                }
                break;
            case 9:
                loop = 0;
                break;
            default:
                printf("Please Enter a Valid Option\n");
                break;
        }
    }
}

3. circularlist.h

#ifndef _DOUBLYLIST_
#define _DOUBLYLIST_

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

typedef struct DoublyListNodeType
{
	int data;
	struct DoublyListNodeType* pLLink; // 현 노드의 오른쪽 노드 연결을 위한 포인터
	struct DoublyListNodeType* pRLink; // 현 노드의 왼쪽 노드 연결을 위한 포인터
} DoublyListNode;

typedef struct DoublyListType
{
	int	currentElementCount; // 현재 삽입된 원소의 개수	
	DoublyListNode	headerNode; // 더미노드
} DoublyList;

DoublyList* createDoublyList();
void deleteDoublyList(DoublyList* pList);
int addDLElement(DoublyList* pList, int position, DoublyListNode element);
int removeDLElement(DoublyList* pList, int position);
void clearDoublyList(DoublyList* pList);
int getDoublyListLength(DoublyList* pList);
DoublyListNode* getDLElement(DoublyList* pList, int position);
void displayDoublyList(DoublyList* pList);

#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE		1
#define FALSE		0

#endif