[Data Structure] 4. Doubly Linked List

9442 ワード

特長


  • ヘッドノードのループ構造

    スタックノードとしてヘッダノード
  • のみが使用される場合、ヘッダノードのprlinkおよびpLLLinkは、NULLではなくヘッダノード自身を指す
  • 要素を追加すると、最初のノードのpLLLinkと最後のノードのpRLinkはヘッダノード
  • を指す.

    長所

  • ヘッダノードから最初のノードと最後のノードに簡単にアクセス
  • 現在の要素count/2よりも検索するノードの位置が大きい場合は、pLLLinkに沿ってループすることができ、小さい場合は、prlinkに沿ってループするときに
  • にすばやくアクセスすることができる.

    短所

  • 動的割当、ポインタ計算等は、
  • の実施・管理が困難である.
  • ポインタを使用すると、ストレージスペースが浪費されます(prlink、pLLLinkを使用します)
  • インプリメンテーション


    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