[Data Structure] 4. Doubly Linked List
9442 ワード
特長
ヘッドノードのループ構造
スタックノードとしてヘッダノード
長所
短所
インプリメンテーション
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
Reference
この問題について([Data Structure] 4. Doubly Linked List), 我々は、より多くの情報をここで見つけました https://velog.io/@highcho/DoublyLinkedListテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol