二重接続リスト

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;
}

🔗 完全なコード