연결형 리스트
- 다음과 같이 메모리 주소를 생성하고 생성된 공간을 노드라고 한다.
- 노드에는 데이터와 주소를 담는 공간이 할당된다.
- 각 노드는 주소로 연결되어 있다.
연결형 리스트 구현하기
- 구조체를 통해서 노드를 쉽게 구현한다.
- 구조체 노드 안에는 다음 노드를 넣어 처음 접근 시 마지막 노드까지 접근할 수 있도록 한다.
- 노드만 있으면 리스트에 접근할 수 없음으로 처음 접근 할 수 있는 헤드노드를 만든다.
구조체 만들기 및 초기화, 리스트 접근
구조체를 만든다. 데이터의 형태는 리스트 형태마다 다르게 만들 수 있지만 노드에 다음 노드의 주소가 들어가는 공통으로 작성되어야한다. 또한 처음 노드에 접근할 수 있도록 노드의 값을 최초 접근하게 되는 구조체에 넣어준다.
typedef struct _tagNode
{
//해당 노드 안에는 데이터와 다음 노드의 주소값이 들어있을 것이다.
int iData;
//tNode라는 변수이름은 아직 시스템이 모르기 때문에 struct로 사용해야한다.
struct _tagNode* pNextNode;
}tNode;
// 연결 리스트는 노드단위로 생성된다.
// iCount 맴버변수를 통해 생성된 노드의 갯수를 파악한다..
// 이는 추후 노드의 갯수에 따라 원하는 노드에 접근을 도와준다.
typedef struct _tagList
{
// 처음 생성되는 리스트는 힙영역에 생성된 노드의 주소를 가르킨다.
tNode* pHeadNode;
int iCount;
}tLinkedList;
해당 구조체를 이용하여 초기화 한다.
List.h
void InitList(tLinkedList* _pList);List.cpp
void InitList(tLinkedList* _pList)
{
_pList->pHeadNode = nullptr;
_pList->iCount = 0;
}노드의 접근은 최초 헤드노드가 들어있는 구조체로 접근할 것이다.
main함수
tLinkedList list;
InitList(&list);데이터 추가하기
함수를 이용하여 포인터 구조체와 데이터를 받아 첫번째 노드일때 헤드노드에 할당하고 그렇지 않을 경우에는 헤드 노드로부터 다음 노드를 검사하면서 다음 노드의 주소가 nullptr일 때 마지막 노드임을 확인하다.
void PushBack(tLinkedList* _pList, int _Data)
{
//새로운 노드를 만든다.
tNode* pNode = (tNode*)malloc(sizeof(tNode));
// 해당 노드의 Data변수에는 Data를 넣는다.
pNode->iData = _Data;
// 다음 노드가 들어 있는지 아직 모르지 nullptr로 할당한다.
pNode->pNextNode = nullptr;
//현재 pNode는 Data가 할당되어 있으며 pNextNode는 아직 없는 상태이다.
// 첫번째 노드인지 확인
if (0 == _pList->iCount)
{
// 첫번째 노드라면 iCount가 0이거나 NextNode가 nullptr일 것이다.
_pList->pHeadNode = pNode;
}
else
{
//데이터가 첫번째가 아닌 경우
// pNextNode에는 다음 노드의 주소가 할당되어 있을 것이다.
// 마지막 노드는 처음 노드로부터 접근이 가능한데 처음노드를 바로 사용하면 무결성이 해칠 위험이 있어
// 아래와 같이 새로운 노드 변수를 만들어 해드노드로 접근한다.
tNode* pCurFinalNode = _pList->pHeadNode;
//pCurFinalNode의 pNextNode가 있다면 마지막 노드가 아닐 것이다.
while (pCurFinalNode->pNextNode)
{
//pCurFinalNode의 pNextNode에 다음 노드의 정보가 들어있다.
// pCurFinalNode에 다음 노드의 주소를 넣으면 다음 노드가 포인팅 된다.
pCurFinalNode = pCurFinalNode->pNextNode;
}
// 함수가 실행 될 때 생성된 pNode의 헤드노드의 pNextNode에 할당한다.
pCurFinalNode->pNextNode = pNode;
}
// 새로운 노드가 넣어질 때마다 iCount를 증가시킨다.
++_pList->iCount;
}pushback함수는 새로운 노드를 저장하는 함수로 처음으로 시작하는 노드라면 iCount가 0이거나 연결리스트에 저장된 노드의 헤더노드가 nullptr일 것이다.
따라서 새로운 노드를 만들어 자료를 먼저 할당하고 헤더노드에 만들어진 노드를 할당하면 된다.
헤더 노드는 변경되면 안됨으로 새로운 노드 타입 변수를 만들어서 헤더노드를 포인팅한다.
마지막 노드인지 확인을 하려면 헤더노드의 pNextNode 값을 계속 할당해 나아가면서 FinalNode의 포인팅을 옮겨간다. 마지막 노드라면 while문이 종료 되고 다음 노드를 넣을 것이다.
노드를 넣고 나면 count를 올려준다.
pushfront으로 구현하기
void PushFront(tLinkedList* _pList, int _Data)
{
// 새로운 노드를 만든다.
tNode* _pNode = (tNode*)malloc(sizeof(tNode));
//데이터를 할당하고
_pNode->iData = _Data;
//새로 생성된 노드의 pNextNode에는 헤드노드가 들어가고
_pNode->pNextNode = _pList->pHeadNode;
// 헤드노드에 다시 이후 노드 정보를 넣어야 한다.
_pList->pHeadNode = _pNode;
++_pList->iCount;
}
메모리 해제
동적할당을 이용하였다면 메모리 해제는 필수적이다.
리스트는 힙 메모리 영역에 pNextNode에 주소값이 연결된 형태로 지속적으로 해제해 나아가려면
재귀함수적으로 메모리를 해제해 나가는 방법을 고려할 수 있다.
재귀함수는 자기자신을 호출하는 방법으로 무한반복으로 메모리 오버플로우를 유의하여 반드시 탈출하는 조건문을 걸어준다.
void Release(tNode* _pNode)
{
//1. 검사하는 노드가 nullptr로 메모리 해제 완료되면 return하여 탈출한다.
if (nullptr == _pNode) return;
//2. 해당 노드의 pNextNode에 접근하여
Release(_pNode->pNextNode);
//3. 메모리를 해제한다.
free(_pNode);
}
//함수는 노드를 직접 받는 것이 아닌 tLinkedList타입으로 헤드부터 이어나간다.
void ReleaseList(tLinkedList* _pList)
{
//재귀 함수 적 메모리 해제 함수 호출
Release(_pList->pHeadNode);
}
한번 함수가 실행되면 모든 함수가 nullptr가 될때까지 2 ~ 3을 반복하면서 pNextNode들을 해제해 나간다.
아니면 헤더노드를 포인터 변수에 받아놓아서 헤더부터 시작하는 반복문을 이용하여 메모리를 해제해 나아가도 된다.
void ReleaseList(tLinkedList* _pList)
{
//반복문으로 해보기
//헤더를 받아서
tNode* pDeleteNode = _pList->pHeadNode;
// 헤더가 nulptr이 될때까지 반복한다.
while (pDeleteNode)
{
//pNextNode를 포인터 변수 받고
tNode* pNext = pDeleteNode->pNextNode;
// 메모리를 해제한다.
free(pDeleteNode);
// 다음 pNextNode를 받아 다음 해제를 준비한다.
pDeleteNode = pNext;
}
}