아래 코드는
연결형 리스트를 구현하기 위해
구조체를 선언한 LinkedList.h 파일입니다.
6번째 줄이 오류가 발생하는 부분입니다.
그래서 아래 코드로 작성해야 하죠.
이유는 구조체를 사용할 때
'struct _tagNode'의 형태로 사용해야 했는데
편하게 쓰기 위해 구조체 선언 마지막에 별명을 붙여줬죠.
위 코드에서는 'tNode'라는 별명을 붙여줬네요.
이러다 보니 6번째 줄은 아직 tNode라는 것이 만들어지기 전입니다.
그래서 멤버를 선언할 때 별명을 바로 사용하지 못하고
원래 이름인 'struct _tagNode' 형태로 멤버를 선언해야 하는 것이죠.
이제 main.cpp에서
연결형 리스트의 역할을 할 객체를 선언하겠습니다.
이를 위해서 일단 LinkedList.h 파일을 포함시켜야겠죠.
그리고 이름의 tLinkedList형 객체 list를 선언했습니다.
현재 list의 멤버들이 초기화되어 있지 않습니다.
편하게 초기화하기 위해 함수를 만들어 볼까요?
LinkedList.h에
InitList라는 이름의 초기화 함수를 선언하고
LinkedList.cpp에
초기화 함수를 정의하였습니다.
InitList 함수는 Linked List 역할을 할 객체의
주솟값을 받습니다. 그리고 해당 주솟값을 통해 가장 첫 번째 노드의
주솟값을 저장하는 멤버 pHeadNode에 접근합니다.
tLinkedList형 객체를 초기화하는 시점에는 Node가 없으므로
멤버 pHeadNode를 nullptr로 초기화합니다.
Node의 개수를 나타내는 변수 iCount도
초기화하는 시점에는 Node가 없으므로 0으로 초기화하면 되겠죠.
tLinkedList형 객체 list를 통해
관리할 수 있는 Node를 하나 만들겠습니다.
LinkedList.h에
PushBack이라는 함수를 선언하고
LinkedList.cpp에
PushBack이라는 함수를 정의하였습니다.
14
앞으로 만들 Node가 속할 tLinkedList형 객체와
Node에 들어갈 값을 인자로 받습니다.
17 ~ 19
우선 iostream 파일을 포함시켜
malloc 함수를 사용할 수 있게 합니다.
malloc 함수를 통해 tNode형 크기만큼
Heap 영역에 동적 할당 합니다.
이렇게 동적 할당한 공간을
tNode형 포인터 객체 pNode로 가리킵니다.
동적 할당한 공간에 있는 변수 iData에는 인자로 받은 값을,
동적 할당한 공간에 있는 다음 노드를 가리키는
포인터 객체 pNextNode에는 nullptr을 저장합니다.
nullptr을 저장하는 이유는 다음 노드가 아직 없기 때문이죠.
21 ~ 25
인자로 받은 객체의 노드 수를 나타내는
iCount가 0일 경우, 즉 LinkedList형 객체 list에
아무런 Node가 존재하지 않을 경우입니다.
객체의 첫 번째 노드의 주솟값을 저장하는
포인터 pHeadNode에 동적 할당한 공간의 주솟값을
바로 저장합니다.
26
객체가 관리하는 노드가 이미 있을 경우,
가장 마지막 노드로 가서 해당 노드가
새로 동적 할당한 pNode를 가리키게 해야 합니다.
28
하지만 객체가 알고 있는 것은
첫 번째 노드의 주솟값 뿐입니다.
그래서 tNode형 객체 checkNode를 만들어서
이곳에 첫 번째 노드의 주솟값을 저장한 후
다음 노드를 찾아갈 것이고, 가리키는 다음 노드가 없는
노드를 찾으면 해당 노드가 새로 동적 할당한 pNode를 가리키게 할 것입니다.
근데 이 과정에서 첫 번째 노드의 주솟값을 담은,
객체의 pHeadNode의 값이 실제로 변하면 안되기 때문에
따로 tNode형 객체 checkNode를 만들어서 추적하는 것입니다.
30
노드가 몇 개 있을지 모르기 때문에 몇 번 반복하게 될지
알 수 없어 while문으로 진행하였지만, 사실 iCount를 통해
마지막 노드가 몇 번째인지 알 수 있으므로 for문으로 진행해도 됩니다.
만약 다음 노드의 주솟값을 담은 pNextNode의 값이 nullptr일 경우,
그곳이 바로 마지막 노드라는 의미이므로 반복문을 빠져 나옵니다.
다음 노드의 주솟값을 저장하는 pNextNode에 새로 동적 할당한
pNode의 주솟값을 저장해 마지막 노드가 새로 동적 할당한 공간을
가리킬 수 있도록 합니다.
while문을 조금 더 간략하게 표현하자면
if문을 없애고 위와 같이 쓸 수 있습니다.
nullptr인 경우 0으로 보기 때문에
checkNode->pNextNode가 nullptr이면
while문을 빠져 나가게 될 것입니다.
그 외의 값이라면 while문을 실행하겠죠.
어차피 checkNode->pNextNode가 nullptr이면
반복문을 빠져 나가야 되기 때문에
위와 같이 작성해도 문제되지 않습니다.
36
근데 다음 노드의 주솟값을 저장하는 pNextNode의 값이
nullptr이 아닐 경우, 즉 해당 노드가 마지막이 아니라
다음 노드의 주솟값을 저장하고 있는 경우입니다.
그럼 다음 노드로 가서 주솟값을 얻고
그것을 checkNode에 저장합니다.
그러면 다시 반복문을 돌게 되고 다음 노드로 간 후
pNextNode의 값이 nullptr인지 아니면 다음 노드의
주솟값을 저장하고 있는지 다시 판단하게 되겠죠.
42
위 과정을 거치고 나면 Linked List 역할을 할 객체 list가
관리하는 노드가 한 개 생긴 것이므로 노드의 개수를 의미하는
iCount의 값을 하나 올려주면 됩니다.
실행 결과를 확인해 보겠습니다.
PushBack 함수를 통해 tLinkedList형 객체 list에
100과 200을 저장하고 있는 Node 두 개를 추가했습니다.
list의 멤버 pHeadNode는 첫 번째 노드의 주솟값을
저장하고 있을 것입니다.
해당 주솟값을 통해 첫 번째 노드로 가 보니
정말 100이 들어 있는 것을 확인할 수 있습니다.
다음 노드의 주솟값을 저장하는 pNextNode에
값이 들어 있는 것이 보입니다.
다음 노드의 주솟값을 저장하는
pNextNode를 통해 다음 노드로 가 보니,
200을 저장하고 있는 노드가 나타났습니다.
다음 노드가 존재하지 않으므로
pNextNode에는 nullptr가 저장되어 있네요.
Heap 영역에 동적 할당한 메모리를 해제도 해줘야겠죠?
LinkedList.h에는
동적 할당 메모리를 해제하기 위한
함수 ReleaseList를 선언하고
LinkedList.cpp에는
함수 ReleaseList를 정의하였습니다.
또한 Release라는 함수도 정의하였는데요,
이유는 List를 free 함수를 통해 바로 메모리를 해제하면
다른 노드의 주솟값을 모두 잃게 되어
다른 노드의 메모리를 해제할 수 없습니다.
그래서 안쪽 노드까지 들어가 메모리 해제를 하기 위해
함수 Release를 만들었고 이를 재귀 함수를 형태로 사용할 것입니다.
우선 ReleaseList 함수를 통해 tLinkedList형 객체를 받습니다.
tLinkedList형 객체가 관리하는 노드의 메모리를 해제하기 위해
tLinkedList형 객체의 첫 번째 노드의 주솟값을 Release 함수에 넘깁니다.
47
만약 첫 번째 노드로 가 보니 값이 존재하였다고 합시다.
그럼 다시 Release 함수를 호출하고 두 번째 노드의 주솟값을 넘깁니다.
두 번째 노드로 가 보니 또 값이 존재하였다고 합시다.
그럼 다시 Release 함수를 호출하고 세 번째 노드의 주솟값을 넘깁니다.
45
근데 세 번째 노드로 가 보니 값이 존재하지 않네요.
바로 return하여 세 번째로 호출된 Release 함수를 나옵니다.
48
두 번째로 호출된 Release 함수로
돌아왔더니 free 함수를 만났습니다.
두 번째 노드의 메모리를 해제합니다.
두 번째로 호출된 Release 함수를 나옵니다.
첫 번째로 호출된 Release 함수로
돌아왔더니 free 함수를 만났습니다.
첫 번째 노드의 메모리를 해제합니다.
첫 번째로 호출된 Release 함수를 나옵니다.
근데 재귀 함수를 사용하면 메모리를 해제하려는
데이터의 수가 많아질수록 엄청나게 많은 함수를
호출하게 되므로 성능이 많이 떨어집니다.
이런 이유로 반복문을 사용하여 메모리 해제 함수를 구현하겠습니다.
46
첫 번째 노드의 주솟값을
tNode형 포인터 deleteNode에 저장합니다.
51
그리고 free 함수를 통해서 메모리를 해제할 겁니다.
현재 deleteNode는 첫 번째 노드를 가리키고 있는데
바로 해제하면 뒤에 있는 노드들의 주솟값을
잃기 때문에 다른 노드들의 메모리를 해제할 수 없겠죠?
50
그래서 tNode형 포인터 nextNode를 만들어
메모리를 해제하기 전에 다음 노드의 주솟값을
저장해둘 겁니다. 그리고 난 후에 메모리를 해제하는 거죠.
52
메모리를 해제한 후에 50번째 줄에서 nextNode를 통해
저장해 둔 다음 노드의 주솟값을 다시 deleteNode에 저장합니다.
그럼 다시 while문을 돌 때 다음다음 노드의 주솟값을
nextNode에 저장한 후에 deleteNode에 저장된 노드의
메모리를 해제하고 nextNode를 통해 저장해 둔
다음다음 노드의 주솟값을 다시 deleteNode에 저장하겠죠.
48
근데 deleteNode에 저장된 주솟값을 가 보니 nullptr인 경우,
즉 deleteNode의 값이 nullptr이면 while문을 빠져 나가야 할 겁니다.
빈 공간의 메모리를 해제할 필요는 없기 때문이죠.
그래서 괄호 안에 deleteNode를 넣어
deleteNode가 nullptr이면 while문이 0( false )으로
인식하도록 하여, while문으로 들어가지 않게 하는 겁니다.
그 외의 값이 있으면 메모리 해제를 진행해야 하기 때문에
while문이 true(0이 아닌 다른 값)로 인식하여 while문을 실행하겠죠.
100과 200이 들어 있는 노드를 만들었는데,
Release 함수를 통해 두 노드의 메모리를 해제하겠습니다.
실행해 보면
deleteNode가 100이 들어 있는 첫 번째 노드를 가리키고 있습니다.
deleteNode가 nullptr이 아니므로
while문이 실행되겠죠.
nextNode는 200이 들어 있는 두 번째 노드를 가리키고 있습니다.
이후 free 함수로 인해
deleteNode가 가리키는 첫 번째 노드의
메모리가 해제되면서 이상한 값이 나타나고 있네요.
이제 deleteNode는
nextNode가 가리키고 있는
두 번째 노드를 가리키는 상태가 됩니다.
deleteNode의 값이
nullptr이 아니므로 while문이 실행됩니다.
nextNode의 값을 확인해 보니
메모리를 읽을 수 없다고 나옵니다. 애초에 노드는 두 개이고
이미 deleteNode는 두 번째 노드를 가리키고 있습니다.
세 번째 노드는 존재하지 않는데(nullptr)
세 번째 노드의 주솟값을 nextNode에
저장하려고 하니 인식하지 못하는 겁니다.
이후 free 함수를 통해
deleteNode가 가리키는 두 번째 노드의 메모리가 해제되었습니다.
nextNode의 값은
현재 nullptr입니다. 그래서 이를 deleteNode에 대입하니
deleteNode의 값도 nullptr이 되었네요.
deleteNode의 값이
nullptr이므로 while문이 0으로 인식해
false가 되어 더 이상 while문이 실행되지 않습니다.
이후 메모리 해제를 진행한
객체 list의 값을 확인해 보니 메모리가 해제되어
알 수 없는 값이 들어간 것을 확인할 수 있습니다.
강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB
'C++ > 기초' 카테고리의 다른 글
| C++ 기초 : 클래스 (1) (0) | 2024.04.13 |
|---|---|
| C++ 기초 : 리스트 (3) (0) | 2024.04.12 |
| C++ 기초 : 함수 포인터 (0) | 2024.04.08 |
| C++ 기초 : 버블 정렬 (0) | 2024.04.07 |
| C++ 기초 : 리스트 (1) (0) | 2024.04.07 |
