연결 리스트 Linked list

구분	구현 방식	순차적 저장을 구현한 방법	자료 접근 속도	구현 복잡도
배열 리스트	배열	물리적 저장 순서가 순차적	빠름 O(1)	낮음	최대 저장 개수 필요
연결 리스트	포인터	논리적 저장 순서가 순차적	느림 O(n)	높은

배열리스트는 특정 인덱스에 바로 접근이 가능하기 때문에 자료접근 속도가 O(1)이고

연결리스트는 헤더노드부터 포인터로 노드를 탐색해야 하기 때문에 n번째 자료에 접근하려면 O(n)

-- 다만 배열리스트는 노드를 추가, 삭제 하려면 추가, 삭제하려는 노드 오른쪽에 있는 모든 노드를 이동시켜야해서

자료의 추가 삭제가 많으면 연결 리스트로 구현하는 것을 추천 

 

-연결 리스트의 노드 구조 : 자료 + 연결 정보(링크)

-연결 리스트 마지막 노드의 링크 = NULL

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

typedef struct LinkedListNodeType {
	int data;								// 데이터
	struct LinkedListNodeType *pLink;		// 연결 정보(링크)
} LinkedListNode;

typedef struct LinkedListType {
	int             currentCount;
    LinkedListNode  headerNode;		// 가르길 노드 저장을 위한 헤더노드
} LinkedList;

LinkedList *createLinkedList(void)
{
	LinkedList *pReturn = (LinkedList *)malloc(sizeof(LinkedList));
	if (pReturn == NULL)
		return (NULL);

	memset(pReturn, 0, sizeof(LinkedList));
	return pReturn;
}

int getLinkedListData(LinkedList* pList, int position)
{
	if (pList == NULL)
		return (1);
	if (position < 0 || position >= pList->currentCount)
		return (1);

	int i = 0;

	LinkedListNode *pCurrentNode = &(pList->headerNode);
	for (i = 0; i <= position; i++)		// 헤더노드에서 시작하기 때문에 position + 1번
		pCurrentNode = pCurrentNode->pLink;

	return (pCurrentNode->data);
}

int addLinkedListData(LinkedList* pList, int position, int data)
{
	if (pList == NULL )
		return (1);
	if (position < 0 || position > pList->currentCount)
		return (1);

	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 (0);
}

int removeLinkedListData(LinkedList* pList, int position)
{
	if (pList == NULL)
		return (1);
	if (position < 0 || position >= pList->currentCount)
		return (1);

	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 (0);
}

int deleteLinkedList(LinkedList* pList)
{
	if (pList == NULL)
		return (1);

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

		free(pDelNode);
	}
	free(pList);

	return (0);
}

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

	return (0);
}

int iterateLinkedList(LinkedList* pList)
{
	if (pList == NULL)
		return (1);

	int count = 0;
	LinkedListNode* pNode = NULL;

	pNode = pList->headerNode.pLink;
	while (pNode != NULL)
	{
		printf("[%d],%d\n", count, pNode->data);
		count++;

		pNode = pNode->pLink;
	}
	printf("노드 개수: %d\n", count);
	return (0);
}

void concatLinkedList(LinkedList* pListA, LinkedList* pListB)
{
	LinkedListNode* pNodeA = NULL;

	if (pListA != NULL && pListB != NULL)
	{
		pNodeA = pListA->headerNode.pLink;
		if (pNodeA != NULL)
		{
			while (pNodeA->pLink != NULL)
				pNodeA = pNodeA->pLink;

			pNodeA->pLink = pListB->headerNode.pLink;
		}
		else
			pListA->headerNode.pLink = pListB->headerNode.pLink;

		pListB->headerNode.pLink = NULL;
	}
}

void reverseLinkedList(LinkedList* pList)
{
	LinkedListNode *pNode = NULL, *pCurrentNode = NULL, *pPrevNode = NULL;

	if (pList != NULL) {
		pNode = pList->headerNode.pLink;
		while (pNode != NULL) {
			pPrevNode = pCurrentNode;
			pCurrentNode = pNode;
			pNode = pNode->pLink;
			pCurrentNode->pLink = pPrevNode;
		}

		pList->headerNode.pLink = pCurrentNode;
	}
}

int main(void)
{
	LinkedList *pListA = NULL;
	LinkedList *pListB = NULL;

	pListA = createLinkedList();
	pListB = createLinkedList();
	addLinkedListData(pListA, 0, 10);
	addLinkedListData(pListA, 1, 20);
	addLinkedListData(pListA, 2, 30);
	addLinkedListData(pListB, 0, 40);
	addLinkedListData(pListB, 1, 50);

	printf("연결 리스트 결합 전\n");
	printf("\n연결 리스트 A\n");
	iterateLinkedList(pListA);
	printf("\n연결 리스트 B\n");
	iterateLinkedList(pListB);

	concatLinkedList(pListA, pListB);

	printf("\n연결 리스트 결합 후\n");
	printf("\n연결 리스트 A\n");
	iterateLinkedList(pListA);
	printf("\n연결 리스트 B\n");
	iterateLinkedList(pListB);

	reverseLinkedList(pListA);
	printf("\nreverseLinkedList()\n");
	iterateLinkedList(pListA);

	deleteLinkedList(pListA);
	deleteLinkedList(pListB);

	return (0);
}