[C] 링크드 리스트 LinkedList

[C] 링크드 리스트 LinkedList

---

- 진행

연결형 리스트(Linked List)는 한 배열에 모든 게 들어있는 게 아니라,

리스트가 자신의 첫번째 노드인 headnode와 총 몇 개의 노드가 있는지 count만 가지고 있다.

 

즉,

리스트는 첫번째 노드와 리스트 길이만을 가지고 있다. 
노드는 자신의 들고있는 data와 다음 노드를 가리키는 포인터를 가지고 있다.

 

---

이번에도 파일은 main.cpp, LinkedList.h, LinkedList.cpp로 나눠서 진행한다.

 

1. 먼저 LinkedList.h 파일에 typedef로 list와 node를 정의해준다.
2. main.c 에서 typedef로 정의한 리스트 변수를 하나 만든다.
3. 이 링크드리스트를 사용하기 위해 필요한 기능은 3가지가 있다. (데이터 추가 방식은 취향이라 상관없다)

1. 리스트 초기화(InitList)
2. 데이터 추가(PushFront, PushBack) 
3. 메모리 해제(ReleasedList)

 4. 위 기능을 LinkedList.h에 선언만 하고 구현은 LinkedList.cpp에 했다.

 5. 잘되는지 main에서 테스트.

 

---

-LinkedList.h

#pragma once

//노드
typedef struct _tagNode
{
	int iData;
	struct _tagNode* pNextNode;
}tNode;

//리스트
typedef struct _tagList
{
	tNode* pHeadNode; // 첫번째 노드(head)
	int iCount;
}tLinkedList;


/* 함수 선언들*/

//링크드 리스트 초기화
void InitList(tLinkedList* _pList);

//링크드 리스트 데이터 추가
void PushBack(tLinkedList* _pList, int _iData); //data 뒤에 추가
void PushFront(tLinkedList* _pList, int _iData); //data 앞에 추가

//링크드 리스트 메모리 해제
void ReleaseList(tLinkedList* _pList);

 

---

-LinkedLists.cpp

#include"LinkedList.h"
#include<iostream>

void InitList(tLinkedList* _pList)
{
	_pList->pHeadNode = nullptr; 
	_pList->iCount = 0;
}

void PushBack(tLinkedList* _pList, int _iData) //실시간 추가니까 힙 메모리영역, 동적
{	
	//데이터를 저장할 노드 생성
	//데이터 복사
	tNode* pNode = (tNode*)malloc(sizeof(tNode));

	pNode->iData = _iData;
	pNode->pNextNode = nullptr;  //채우고 그 다음은 null
    
	//리스트는 첫번째 노드만 아니까 지금 push한게 최초의(첫번째) 데이터인지 아닌지를 따져봐야한다.
	//추가한 데이터가 처음인지 아닌지
	if (0 == _pList->iCount) //처음이면
	{
		_pList->pHeadNode = pNode;
	}
	else //이미 리스트는 headnode가 있으면
	{
		//내가 들어오기전 현재 가장 마지막 노드를 찾아서,
		//해당 노드의 pNext에, 이번에 생성시킨 노드의 주소로 채움.

		tNode* pCurFinalNode = _pList->pHeadNode;  //headnode는 바뀌면 안되는 중요한거니까 지역변수를 하나 만들어준다. 지역변수도 똑같은 headnode주소를 가리키니까 상관x
		
		while (pCurFinalNode->pNextNode) // while문을 돌면서 다음 노드가 nullptr일때까지 돈다. pNextNode가 null이면 false로 while문이 끝난다.
		{
			pCurFinalNode = pCurFinalNode->pNextNode;
		}

		pCurFinalNode->pNextNode = pNode;  //next노드에 현재 만든 pNode를 넣어준다.
	}

	++_pList->iCount;  //count 증가
}

void PushFront(tLinkedList* _pList, int _iData)
{
	// 새로 생성시킨 노드(pNode2)의 다음을 기존의 헤드로 지정한다.
	tNode* pNode2 = (tNode*)malloc(sizeof(tNode));
	pNode2->iData = _iData;
	pNode2->pNextNode = _pList->pHeadNode;


	// 리스트의 헤드노트 포인터를 갱신한다.
	_pList->pHeadNode = pNode2;
	
	// 데이터 카운트 증가
	++_pList->iCount;
}


/* 링크드리스트 메모리 해제 방법 1번 재귀로 구현하기*/
/*
void Release(tNode* _pNode)
{
	if (nullptr == _pNode)
		return;

	Release(_pNode->pNextNode); //제일 끝부터가서 free하면서 재귀함.

	free(_pNode);
}
void ReleaseList(tLinkedList* _pList)
{
	Release(_pList->pHeadNode);  //재귀함수 호출(효율이 좋진 않다 ->2번 방법)
}
*/


/*링크드리스트 메모리 해제 방법 2번 */
void ReleaseList(tLinkedList* _pList)
{
	tNode* pDeleteNode = _pList->pHeadNode; //맨 처음 노드

	while (pDeleteNode) //null되면 끝난다.
	{
		tNode* pNext = pDeleteNode->pNextNode; //free전 미리 다음 노드를 받아둔다
		free(pDeleteNode); //free시킨다.
		pDeleteNode = pNext; 
	}
}

 

---

- main.cpp

#include<iostream>
#include "LinkedList.h"

int main()
{
	tLinkedList list = {}; //생성
	InitList(&list);  //초기화

	//실제로 데이터 집어넣기
	//PushBack(&list, 100);
	//PushBack(&list, 200);
	//PushBack(&list, 300);

	PushFront(&list, 300);
	PushFront(&list, 200);
	PushFront(&list, 100);
    
	//끝났으면, 데이터 집어넣은거 힙메모리에 집어넣었으니 종료할 땐 해제해줘야한다
	ReleaseList(&list);

	return 0;
}