연결리스트의 확장 Circular linked list, Double linked list

자료구조

연결리스트의 확장 Circular linked list, Double linked list

아옳이 2021. 7. 19. 18:46

	공통점	차이점
단순 연결 리스트	포인터를 이용하여 구현
원형 연결 리스트		연결 리스트의 가장 마지막 노드가 첫 번째 노드와 연결
이중 연결 리스트		양방향 링크를 사용하기 떄문에, 특정 노드 이전 노드에 대한 직접 접근이 가능

원형 연결 리스트 : 마지막 노드가 첫 번째 노드와 연결, 단순 연결 리스트와 마찬가지로 단방향

이중 연결 리스트 : 마지막 노드가 헤더노드와 연결, 양방향

- 노드의 이전 노드의 다음 노드 == 노드의 다음 노드의 이전노드 == 노드

원형 연결 리스트

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct CircularListNodeType {
	int data;
	struct CircularListNodeType *pLink;
} CircularListNode;

typedef struct CircularListType {
	int     currentCount;
	CircularListNode headerNode;
} CircularList;

CircularList *createCircularList()
{
	CircularList *pReturn = (CircularList *)malloc(sizeof(CircularList));
	memset(pReturn, 0, sizeof(CircularList));
	return (pReturn);
}

int getCircularListData(CircularList* pList, int position)
{
	int i = 0;

	CircularListNode *pCurrentNode = &(pList->headerNode);
	for (i = 0; i <= position; i++)
		pCurrentNode = pCurrentNode->pLink;

	return (pCurrentNode->data);
}

int addCircularListData(CircularList* pList, int position, int data)
{
	int i = 0;

	CircularListNode *pNewNode = NULL;
	CircularListNode *pPreNode = NULL;

	pNewNode = (CircularListNode*)malloc(sizeof(CircularListNode));
	pNewNode->data = data;

	pPreNode = &(pList->headerNode);
	for (i = 0; i < position; i++)
		pPreNode = pPreNode->pLink;

	pNewNode->pLink = pPreNode->pLink;
	pPreNode->pLink = pNewNode;

	pList->currentCount++;
	if (pNewNode->pLink == NULL)	// 마지막 노드를 첫 번째 노드에 링크
		pNewNode->pLink = pList->headerNode->pLink;

	return (0);
}

int removeCircularListData(CircularList* pList, int position)
{
	int i = 0;
	CircularListNode *pDelNode = NULL;
	CircularListNode *pPreNode = NULL;

	pPreNode = &(pList->headerNode);
	for (i = 0; i < position; i++)
		pPreNode = pPreNode->pLink;

	pDelNode = pPreNode->pLink;
	pPreNode->pLink = pDelNode->pLink;

	pList->currentCount--;
	if (0 == pList->currentCount)
		pList->headerNode.pLink = NULL;

	free(pDelNode);

	return 0;
}

void deleteCircularList(CircularList* pList)
{
	int i = 0;
	CircularListNode *pDelNode = NULL;
	CircularListNode *pPreNode = pList->headerNode.pLink;
	for (i = 0; i < pList->currentCount; i++)
	{
		pDelNode = pPreNode;
		pPreNode = pPreNode->pLink;

		free(pDelNode);
	}

	free(pList);
}

void displayCircularList(CircularList* pList)
{
	int i = 0;
	CircularListNode* pNode = NULL;

	pNode = pList->headerNode.pLink;
	if (0 == pList->currentCount)
		printf("자료가 없습니다\n");
	else
	{
		printf("노드 개수: %d\n", pList->currentCount);

		for (i = 0; i < pList->currentCount; i++)
		{
			printf("[%d],%d\n", i, pNode->data);
			pNode = pNode->pLink;
		}
	}
}

int main(void)
{
	CircularList *pList = NULL;

	pList = createCircularList();

	addCircularListData(pList, 0, 10);
	displayCircularList(pList);
	addCircularListData(pList, 0, 20);
	displayCircularList(pList);
	addCircularListData(pList, 1, 30);
	displayCircularList(pList);

	removeCircularListData(pList, 2);
	displayCircularList(pList);
	removeCircularListData(pList, 1);
	displayCircularList(pList);
	removeCircularListData(pList, 0);
	displayCircularList(pList);

	deleteCircularList(pList);

	return (0);
}

이중 연결 리스트

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct DoublyListNodeType {
	int data;
	struct DoublyListNodeType* pLLink;	// 이전 노두
	struct DoublyListNodeType* pRLink;	// 다음 노드, 단순 연결 리스트의 pLink
} DoublyListNode;

typedef struct DoublyListType
{
	int	currentCount;
	DoublyListNode	headerNode;
} DoublyList;

DoublyList* createDoublyList()
{
	DoublyList *pReturn = (DoublyList *)malloc(sizeof(DoublyList));
	if (pReturn != NULL)
		memset(pReturn, 0, sizeof(DoublyList));

		pReturn->headerNode.pLLink = &(pReturn->headerNode);
		pReturn->headerNode.pRLink = &(pReturn->headerNode);
	}

	return pReturn;
}

int getDoublyListData(DoublyList* pList, int position)
{
	int i = 0;
	DoublyListNode* pCurrentNode = &(pList->headerNode);
	for (i = 0; i <= position; i++)
		pCurrentNode = pCurrentNode->pRLink;
	return pCurrentNode->data;
}

// 추가와 제거에서 이전 노드와 다음 노드 처리

int addDoublyListData(DoublyList* pList, int position, int data)
{
	int ret = 0, i = 0;
	DoublyListNode *pPreNode = NULL, *pNewNode = NULL;
	pNewNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));
	if (pNewNode != NULL)
	{
		memset(pNewNode, 0, sizeof(DoublyListNode));
		pNewNode->data = data;

		pPreNode = &(pList->headerNode);
		for (i = 0; i < position; i++)
			pPreNode = pPreNode->pRLink;

		pNewNode->pRLink = pPreNode->pRLink;
		pNewNode->pLLink = pPreNode;
		pPreNode->pRLink = pNewNode;			// 이전 노드 처리
		pNewNode->pRLink->pLLink = pNewNode;	// 다음 노드 처리

		pList->currentCount++;
	}
	else
	{
		printf("오류, 메모리 할당 addListData()\n");
		return 1;
	}

	return ret;
}

int removeDoublyListData(DoublyList* pList, int position)
{
	int ret = 0, i = 0;
	DoublyListNode *pPreNode = NULL, *pDelNode = NULL;

	pPreNode = &(pList->headerNode);
	for (i = 0; i < position; i++)		// 이전 노드 찾기
		pPreNode = pPreNode->pRLink;

	pDelNode = pPreNode->pRLink;
	pPreNode->pRLink = pDelNode->pRLink;
	pDelNode->pRLink->pLLink = pPreNode;

	free(pDelNode);
	pList->currentCount--;

	return ret;
}

int getDoublyListLength(DoublyList* pList)
{
	int ret = 0;
	if (pList != NULL)
		ret = pList->currentCount;

	return ret;
}

void displayDoublyList(DoublyList* pList)
{
	int i = 0;
	DoublyListNode* pNode = NULL;
	pNode = pList->headerNode.pRLink;
	if (0 == pList->currentCount)
		printf("자료가 없습니다\n");
	else
	{
		printf("노드 개수: %d\n", pList->currentCount);

		for (i = 0; i < pList->currentCount; i++)
		{
			printf("[%d],%d\n", i, pNode->data);
			pNode = pNode->pRLink;
		}
	}
}

void deleteDoublyList(DoublyList* pList)
{
	if (pList != NULL) {
		while (pList->currentCount > 0) {
			removeDoublyListData(pList, 0);
		}
		free(pList);
	}
}

int main(int argc, char *argv[])
{
	DoublyList *pList = pList = createDoublyList();

	if (pList != NULL)
	{
		addDoublyListData(pList, 0, 10);
		addDoublyListData(pList, 1, 20);
		addDoublyListData(pList, 1, 30);
		displayDoublyList(pList);

		removeDoublyListData(pList, 0);
		displayDoublyList(pList);

		deleteDoublyList(pList);
	}

	return 0;
}

연결 리스트를 이용한 다항식 계산 예제

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TermType {	// 항을 나타내는 구조체
	double	coef;			// 계수
	int		degree;			// 상수
} Term;

typedef struct LinkedListNodeType {	//노드
	Term data;
	struct LinkedListNodeType *pLink;
} LinkedListNode;

typedef struct LinkedListType {
	int             currentCount;
	LinkedListNode headerNode;
} LinkedList, PolyList;

LinkedList *createLinkedList()
{
	LinkedList *pReturn = (LinkedList *)malloc(sizeof(LinkedList));
	memset(pReturn, 0, sizeof(LinkedList));
	return (pReturn);
}

Term getLinkedListData(LinkedList* pList, int position)
{
	int i = 0;

	LinkedListNode *pCurrentNode = &(pList->headerNode);
	for (i = 0; i <= position; i++)
		pCurrentNode = pCurrentNode->pLink;

	return (pCurrentNode->data);		// 구조체 리턴
}

int addLinkedListData(LinkedList* pList, int position, Term data)
{
	int i = 0;
	LinkedListNode *pNewNode = NULL;
	LinkedListNode *pPreNode = NULL;

	pNewNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
	pNewNode->data = data;

	pPreNode = &(pList->headerNode);
	for (i = 0; i < position; i++)
		pPreNode = pPreNode->pLink;

	pNewNode->pLink = pPreNode->pLink;
	pPreNode->pLink = pNewNode;
	pList->currentCount++;
	return (1);
}

int removeLinkedListData(LinkedList* pList, int position)
{
	int i = 0;
	LinkedListNode *pDelNode = NULL;
	LinkedListNode *pPreNode = NULL;

	pPreNode = &(pList->headerNode);
	for (i = 0; i < position; i++)
		pPreNode = pPreNode->pLink;

	pDelNode = pPreNode->pLink;
	pPreNode->pLink = pDelNode->pLink;
	free(pDelNode);
	pList->currentCount--;
	return (1);
}

void deleteLinkedList(LinkedList* pList)
{
	LinkedListNode *pDelNode = NULL;
	LinkedListNode *pPreNode = pList->headerNode.pLink;
	while (pPreNode != NULL)
	{
		pDelNode = pPreNode;
		pPreNode = pPreNode->pLink;

		free(pDelNode);
	}

	free(pList);
}

int getLinkedListLength(LinkedList* pList)
{
	if (NULL != pList)
		return pList->currentCount;
	return (0);
}

//	여기서부터 새로운 함수

int addPolyNodeLast(PolyList* pList, double coef, int degree)	// 마지막 위치에 노드 추가
{
	int ret = 0, position = 0;

	Term term = { 0, };
	term.coef = coef;
	term.degree = degree;

	if (pList != NULL)
	{
		position = pList->currentCount;
		ret = addLinkedListData(pList, position, term);
	}

	return (ret);
}

void displayPolyList(PolyList* pList)
{
	int i = 0;
	LinkedListNode* pNode = NULL;
	pNode = pList->headerNode.pLink;
	if (0 == pList->currentCount)
		printf("자료가 없습니다\n");
	else
	{
		for (i = 0; i < pList->currentCount; i++)
		{
			if (i > 0)
				printf(" + ");
			printf("%.1fx^%d", pNode->data.coef, pNode->data.degree);
			pNode = pNode->pLink;
		}
		printf("\n");
	}
}

PolyList* polyAdd(PolyList* pListA, PolyList* pListB)
{
	PolyList* pReturn = NULL;
	LinkedListNode *pNodeA = NULL, *pNodeB = NULL;
	double coefSum = 0;

	if (pListA != NULL && pListB != NULL) {
		pReturn = createLinkedList();
		if (pReturn == NULL) {
			printf("메모리 할당 오류, polyAdd()\n");
			return NULL;
		}

		pNodeA = pListA->headerNode.pLink;
		pNodeB = pListB->headerNode.pLink;
		while (pNodeA != NULL && pNodeB != NULL)
		{
			int degreeA = pNodeA->data.degree;
			int degreeB = pNodeB->data.degree;
			if (degreeA > degreeB)	// 노드A의 차수 > 노드B의 차수 인 경우
			{
				coefSum = pNodeA->data.coef;
				addPolyNodeLast(pReturn, coefSum, degreeA);
				pNodeA = pNodeA->pLink;
			}
			else if (degreeA == degreeB)	// 노드A의 차수 == 노드B의 차수 인 경우
			{
				coefSum = pNodeA->data.coef + pNodeB->data.coef;
				addPolyNodeLast(pReturn, coefSum, degreeA);
				pNodeA = pNodeA->pLink;
				pNodeB = pNodeB->pLink;
			}
			else	// 노드A의 차수 < 노드B의 차수 인 경우
			{
				coefSum = pNodeB->data.coef;
				addPolyNodeLast(pReturn, coefSum, degreeB);
				pNodeB = pNodeB->pLink;
			}
		}
		//	한쪽 노드가 먼저 끝난 경우 남은 노드 모두처리
		while (pNodeA != NULL) {
			coefSum = pNodeA->data.coef;
			addPolyNodeLast(pReturn, coefSum, pNodeA->data.degree);
			pNodeA = pNodeA->pLink;
		}

		while (pNodeB != NULL) {
			coefSum = pNodeB->data.coef;
			addPolyNodeLast(pReturn, coefSum, pNodeB->data.degree);
			pNodeB = pNodeB->pLink;
		}
	}
	else
	{
		printf("오류, NULL 다항식이 전달되었습니다, polyAdd()\n");
	}

	return (pReturn);
}

int main(int argc, char *argv[])
{
	PolyList *pListA = NULL;
	PolyList *pListB = NULL;
	PolyList *pListC = NULL;

	pListA = createLinkedList();
	pListB = createLinkedList();

	if (pListA != NULL && pListB != NULL)
	{
		// pListA: 7x^6 + 3x^5 + 5x^2
		// pListB: 1x^5 + 2x^4 + 3x^2 + 4x^0
		addPolyNodeLast(pListA, 7, 6);
		addPolyNodeLast(pListA, 3, 5);
		addPolyNodeLast(pListA, 5, 2);
		displayPolyList(pListA);

		addPolyNodeLast(pListB, 1, 5);
		addPolyNodeLast(pListB, 2, 4);
		addPolyNodeLast(pListB, 3, 2);
		addPolyNodeLast(pListB, 4, 0);
		displayPolyList(pListB);

		pListC = polySub(pListA, pListB);
		if (pListC != NULL)
		{
			displayPolyList(pListC);
			deleteLinkedList(pListC);
		}

		deleteLinkedList(pListA);
		deleteLinkedList(pListB);
	}

	return (0);
}