[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;
    }
    🔗 完全なコード