리스트 함수 직접 구현해보기
리스트는 가변배열과 다르게 가변배열은 메모리가 연속되있다는 특징을 가졌고 리스트는 데이터가 뛰엄뛰엄 끊어져있다.
데이터가 필요할 때 마다 한칸한칸 동적할당해서 데이터를 직접 넣는다. 이 데이터 한칸을 노드라고한다. 하나에 노드안에는 데이터가 들어있지만 다음 데이터를 가르키는 주소도 가지고있어야 한다.
list.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include "list.h"
void init(list * pList)
{
pList->HeadNode = nullptr; //아직 데이터가 없기 때문
pList->Count = 0;
}
void PushBack(list * pList, int iData)
{
node* pNode = (node*)malloc(sizeof(node)); //노드 하나를 위한 공간을 만듬
pNode->Datd = iData; // 노드 데이터를 넣어줌
pNode->NextNode = nullptr; // 가장 마지막 공간은 널포인트
//지금 들어온 데이터가 첫번째인지 아닌지
if (pList->Count == 0)
{
pList->HeadNode = pNode;// 첫번째 노드의 넣어줌
}
else
{
// 현재 가장 마지막 노드를 찾아서,
// 그 노드의 NewxtNode 를 생성시킨 노드의 주소를 채움
node* FinalNode = pList->HeadNode; // 값이 변경되면 안되므로 따로 선언해준다.
while (FinalNode->NextNode != false) // 노드의 다음주소가 널이 아니면
{
FinalNode = FinalNode->NextNode; // 마지막 노드에 값을 넣어줌
}
FinalNode->NextNode = pNode; // 마지막 노드의 넣어줌
}
pList->Count++;
}
void PushFront(list * pList, int idata)
{
//새로 생성시킨 노드의 다음을 기존의 헤드로 지정한ㄷ.
node* newnode = (node*)malloc(sizeof(node));
newnode->Datd = idata;
newnode->NextNode = pList->HeadNode;
// 리시트로 헤드노드 포인터를 갱신한다.
pList->HeadNode = newnode;
pList->Count++;
}
//재귀함수로 메모리 해제하는 방법
void Release(node* pNode)
{
if (pNode == nullptr) //넥스트 노드가 널포인트면
{
return; // 거꾸로 가서 마지막 노드부터 순차적으로 해제
}
Release(pNode->NextNode); //넥스트 노드 먼저 해제하자
free(pNode); // 메모리 해제
}
void ReleaseList(list * pList)
{
// Release(pList->HeadNode); //Release함수한테 헤드노드를 줌(재귀함수)
node* DeleteNode = pList->HeadNode; // DelteNode에 첫번째 노드를 줌(주소)
while (DeleteNode) // 널포인트가 아니면
{
node* pNext = DeleteNode->NextNode; // pNewx에 다음 노드를 줌
free(DeleteNode); // 메모리해제
DeleteNode = pNext; // pnext노드를 DeleteNode한테 줌
}
pList->Count = 0;
}
|
cs |
list.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include<iostream>
typedef struct tnode
{
tnode* NextNode; //다음 노드의 주소
int Datd;
}node;
typedef struct tlist
{
node* HeadNode; //첫번째 노드의 주소
int Count;
}list;
// 연결형 리스트 초기화
void init(list* pList);
// 연결형 리스트 데이터 추가
void PushBack(list* pList ,int iData);
// 연결형 리시트 앞에다 데이터 추가
void PushFront(list* pList, int idata);
// 연결형 리스트 메모리 해제
void ReleaseList(list* pList);
|
cs |
main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<iostream>
#include "c.h"
#include "list.h"
using namespace std;
int main() {
list s = {}; //리스트 객체 선언
init(&s); // 초기화
PushBack(&s, 100);
PushBack(&s, 200);
PushBack(&s, 300);
PushBack(&s, 400);
PushBack(&s, 500);
node* pnode = s.HeadNode;
for (int i = 0; i < s.Count; i++)
{
cout << pnode->Datd << "\n";
pnode = pnode->NextNode;
}
ReleaseList(&s);
return 0;
}
|
cs |
