[C言語]二重接続リストの実装
二重接続リスト
Doubly Linked List
前ノードと後ノードのアドレスリスト
インプリメンテーション
作成
ノードの追加
1.古いノードを新しいノードの左側に接続する
2.次のノードを新しいノードの右側(現在位置のノード)に接続します.
3.新しいノードを前のノードの右側に接続する
4.次のノード(現在位置ノード)の左側に新しいノードを接続する
5.ノード数の変更
ノードの削除
1.次のノードを前のノードの右側に接続する
2.前のノードを次のノードの左側に接続する
3.現在位置ノードを除去する
4.ノード数の変更
構造体と関数のプロトタイプ
typedef struct DoublyListNodeType
{
int data;
struct DoublyListNodeType* pLLink;
struct DoublyListNodeType* pRLink;
} DoublyListNode;
typedef struct DoublyListType
{
int currentElementCount;
DoublyListNode headerNode;
} DoublyList;
DoublyList* createDoublyList();
int addDLElement(DoublyList* pList, int position, DoublyListNode element);
int removeDLElement(DoublyList* pList, int position);
DoublyListNode* getDLElement(DoublyList* pList, int position);
void displayDoublyList(DoublyList* pList);
void clearDoublyList(DoublyList* pList);
int getDoublyListLength(DoublyList* pList);
void deleteDoublyList(DoublyList** pList);
関数の定義
DoublyList* createDoublyList() // list 생성
{
DoublyList *list;
list = (DoublyList *)malloc(sizeof(DoublyList));
if (list == NULL)
return (NULL);
list->currentElementCount = 0;
list->headerNode.pLLink = &list->headerNode;
list->headerNode.pRLink = &list->headerNode;
return (list);
}
int addDLElement(DoublyList *pList, int position, DoublyListNode element) // 노드 추가
{
DoublyListNode *new;
DoublyListNode *prev;
int i;
if (pList == NULL || position < 0 || position > pList->currentElementCount)
return (FALSE);
new = (DoublyListNode *)malloc(sizeof(DoublyListNode));
if (new == NULL)
return (FALSE);
*new = element;
prev = &pList->headerNode;
for (i = 0; i < position; i++)
prev = prev->pRLink;
new->pLLink = prev;
new->pRLink = prev->pRLink;
prev->pRLink = new;
new->pRLink->pLLink = new;
pList->currentElementCount++;
return (TRUE);
}
int removeDLElement(DoublyList *pList, int position) // 노드 제거
{
DoublyListNode *prev;
DoublyListNode *temp;
int i;
if (pList == NULL || position < 0 || position >= pList->currentElementCount)
return (FALSE);
prev = &pList->headerNode;
for (i = 0; i < position; i++)
prev = prev->pRLink;
temp = prev->pRLink;
prev->pRLink = temp->pRLink;
temp->pRLink->pLLink = prev;
free(temp);
temp = NULL;
pList->currentElementCount--;
return (TRUE);
}
DoublyListNode *getDLElement(DoublyList *pList, int position) // 노드 가져오기
{
int i;
DoublyListNode *curr;
if (position < 0 || position >= pList->currentElementCount)
return (NULL);
// position이 currentElementCount / 2보다 같거나 작으면 오른쪽으로 순회
if (position <= pList->currentElementCount / 2)
{
curr = pList->headerNode.pRLink;
for (i = 0; i < position; i++)
curr = curr->pRLink;
}
// 아니면 왼쪽으로 순회
else
{
curr = pList->headerNode.pLLink;
for (i = pList->currentElementCount - 1; i > position; i--)
curr = curr->pLLink;
}
return (curr);
}
void displayDoublyList(DoublyList *pList)
{
DoublyListNode *curr;
int i;
if (pList == NULL)
return;
if (pList->currentElementCount == 0)
printf("empty list");
curr = pList->headerNode.pRLink;
for (i = 0; i < pList->currentElementCount; i++)
{
printf("%d ", curr->data);
curr = curr->pRLink;
}
printf("\n");
}
void clearDoublyList(DoublyList *pList) // list 초기화
{
DoublyListNode *curr;
DoublyListNode *next;
if (pList == NULL)
return;
curr = pList->headerNode.pRLink;
while (pList->currentElementCount)
{
next = curr->pRLink;
free(curr);
curr = next;
pList->currentElementCount--;
}
pList->headerNode.pLLink = &pList->headerNode;
pList->headerNode.pRLink = &pList->headerNode;
}
int getDoublyListLength(DoublyList *pList) // list 노드의 개수 확인
{
if (pList == NULL)
return (ERROR);
return (pList->currentElementCount);
}
void deleteDoublyList(DoublyList **pList) // list free
{
if (pList == NULL || *pList == NULL)
return;
clearDoublyList(*pList);
free(*pList);
*pList = NULL;
}
🔗 完全なコードReference
この問題について([C言語]二重接続リストの実装), 我々は、より多くの情報をここで見つけました https://velog.io/@chez_bono/C언어-이중-연결-리스트Doubly-Linked-List-구현하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol