이중 연결 리스트

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

🔗 전체 코드