연결형 리스트에서 데이터 가져오는게 힘든 이유?
- 동적 배열에서는 데이터 가져오는게 간단했다
- 이유: 한 주소를 가져오면 인덱스로 접근하는게 쉬웟다.
- 연결형 리스트는 특정 인덱스 접근이 느리고 어렵다.
- 이유: 내가 원하는 인덱스를 얻을려면 계속 연결해서 이어가야되기 떄문이다.
연결형 리스트 데이터 가져오는 함수 구현
main.cpp
data = GetData(&list, 0); // 1LinkedList.h
int GetData(LinkedList* _List, int _Idx); // 2LinkedList.cpp
int GetData(LinkedList* _List, int _Idx) // 3
{
Node* pNode = _List->pHeadNode; // 4
for (int i = 0; i < _Idx; ++i) // 5
{
pNode = pNode->pNext; // 6
}
return pNode->Data; // 7
}- // 1은 GetData함수를 호출해서 연결형 리스트에서 0번쨰 인덱스에 접근해서 그 인덱스 값을 가져온다.
- // 2은 함수의 헤더부분으로 주소값과, 인덱스를 선언함.
- // 3은 실제 선언부로 데이터를 가져온다.
- // 4 새로운 지역변수 pNode에 연결형 리스트 첫번쨰 주소값을 대입한다.
- // 5 인덱스 지정값으로 계속 주소를 갱신해줘서 최종적 node에 Data값이 리턴값이다.
- 실제로 표준 라이브러리에서는 리스트는 데이터 접근해서 가져오는 함수 기능을 제공하지 않는다.
- 그런 기능을 쓸거면 애초에 리스트말고 가변배열을 썻어야지라고 생각해서.
인덱스에 값이 절반보다 클경우와 작을경우 분기 처리해서 하면?
- 인덱스 몇을 주냐에 따라 처음에서 시작할지 끝에서 시작할지 정해주면 최악의 경우를 O(n/2)로 줄 일 수 있다.
- 어차피 O(N)이긴하다.
- 그래도 같은 O(빅오) 효율이여도 구현관점에서는 더 좋을것이다.
LinkedList.h
struct Node
{
int Data;
Node* pNext;
Node* pPrevious; // 1
}
struct LinkedList
{
Node* pHeadNode;
Node* pTailNode // 2
int CurCount;
}- 분기 처리할거면 구조체를 이렇게 새롭게 설계해줘야 함.
- // 1 전 주소값
- // 2 꼬리값 주소 구현한거
연결형 리스트에서 pushFront(앞쪽에 추가할 데이터 삽입) 함수 구현
main.cpp
LinkedList mylist2 = {}; // 1
PushFront(&mylist2, 10); // 2
PushFront(&mylist2, 20);
PushFront(&mylist2, 30);
PushFront(&mylist2, 40);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
data = GetData(&mylist2, 4); // 9LinkedList.h
void PushFront(LinkedList* _List, int _Data) // 3LinkedList.cpp
int GetData(LinkedList* _List, int _Idx)
{
assert(!(_List->CurCount <= _Idx)); // 10
Node* pNode = _List->pHeadNode;
for (int i = 0; i < _Idx; ++i)
{
pNode = pNode->pNext;
}
return pNode->Data;
}
void PushFront(LinkedList* _List, int _Data) // 3
{
Node* pNewNode = (Node*)malloc(sizeof(Node)); // 4
pNewNode->Data = _Data; // 5
pNewNode->pNext = _List->pHeadNode; // 6
_List->pHeadNode = pNewNode; // 7
_List->CurCount++; // 8
}- // 1 mylist2 구조체에 주소값 할당
- // 2 PushFront 함수 호출.
- mylist2의 주소값하고, 연결형리스트에 넣을 데이터 적어둠.
- // 3 실제 구현부분으로 데이터를 받아옴.
- // 4 입력된 데이터를 저장할 노드 1개 만큼의 메모리를 동적할당 한다.
- // 5 입력된 데이터를 해당 노드안에 복사한다.(_Data)
- // 6 새로 생성된 노드가 가장 처음이 되어야 하니까, 리스트가 pHeadNode로 해당 노드를 가리킨다.
- // 7 6,7번의 순서가 바뀌면 리스트랑 처음 연결은 이어지지만 두 번쨰 연결이 끊어져서 // 6부터 해야 한다.
- // 8 구동이 끝나면 데이터 카운트 증가 구문.
- PushFront는 한개의 함수를 분기 처리안하고 2가지 경우 처리가능하다.(PushBack은 두가지 경우 처리했어야됨)
- 데이터가 1개일떄도 어차피 다음의 주소값은 nullptr이기 때문에 분기 처리 안해도 문제 발생하지 않는다.
- // 9
- 이유: 노드값을 할당 안받은데에 데이터 값을 가져올려해서 예외발생함.
- // 10 리스트에 입력된 데이터 개수 이상의 인덱스를 지정할 경우.
- // 9같은 케이스를 막을려고 assert문을 해야됨.
재귀함수를 이용해서 만든 연결형 리스트를 뒤집기.
main.cpp
LinkedList mylist2 = {};
PushBack(&mylist2, 10);
PushBack(&mylist2, 20);
PushBack(&mylist2, 30);
PushBack(&mylist2, 40);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
//data = GetData(&mylist2, 4);
Reverse(&mylist2);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);LinkedList.h
// PushBack과 GetData는 이미 선언되있다고 가정
void Reverse(LinkedList* _List);LinkedList.cpp
// PushBack과 GetData는 이미 구현부분 생략.
void Reverse_Re(Node* _Node, LinkedList* _List)
{
if (nullptr != _Node->pNext) // 2
{
bool bHead = false;
if (_Node == _List->pHeadNode)
{
bHead = true;
}
Reverse_Re(_Node->pNext, _List); // 2
_Node->pNext->pNext = _Node; // 4
if (bHead) // 5
{
_Node->pNext = nullptr; // 5
}
}
else
{
_List->pHeadNode = _Node; // 3
}
}
void Reverse(LinkedList* _List)
{
Reverse_Re(_List->pHeadNode, _List); // 1
}- mylist2는 10,20,30,40의 순서로 되어있는 연결형리스트를 Reverse함수를 만나서 40,30,20,10순으로 리스트 순서를 바꾸는 함수를 재귀함수를 이용해서 구현 한것.
- // 3은 _Node가 가리키고 있는 노드가 현재 가장 마지막 노드이다.
- 리스트가 가장 마지막일때를 헤드다 라고 해버린것.
- // 4는 본인의 pNext로가서 다음 노드를 가리켜서 그 전 노드값을 넣는다.
- // 5 마지막 문자를 널로 막아주는 노드다.
- 구동 순서.
- // 1 재귀 함수를 호출한다. 재귀함수에는 인자로 기존의 리스트의 처음 주소값과, 연결형 리스트 본인을 넘긴다
- // 2 _Node를 재귀함수를 계속 돌려서 10(주소)->20(주소)->30(주소)->40(주소)->nullptr가 될대까지 돌아간다
- // 3 _Node의 주소값이 nullptr 되는순간(마지막 노드에 도착) 원래의 리스트에 헤더부분에 기존의 마지막 이였던 노드를 주소값을 저장한다.
- // 4 가 실행되기전 호출스택은 10->20->30->40이였는데 40을 가지고있는 호출 스택이 종료되면서 _Node의 3번째 호출스택에서 40<>30을 와따리 가따리한다.
- // 4 가 실행되고 호출스택이 _Node값이 20일떄 40->30->20->30->20->30->20 무한으로 돈다.
20<->30 - // 4 가 실행되고 호출스택이 또 호출되서 40->30->20->10->20->10->20 무한으로 또 돌고있는데 이 스택은 bHead값이 true였기 때문에 // 5번 if문이 참이되서 돌아서 마지막 10의 노드에 다음 주소는 nullptr이 되서 끝난다.
- 기존의 연결형 리스트의 역순 연결형 리스트가 만들어진다.
연결형 리스트 해제 구문
main.cpp
LinkedList mylist = {};
PushBack(&mylist, 10);
PushBack(&mylist, 20);
PushBack(&mylist, 30);
data = GetData(&mylist, 0);
data = GetData(&mylist, 1);
data = GetData(&mylist, 2);
// 메모리 해제.
Release(&mylist);
LinkedList mylist2 = {};
PushBack(&mylist2, 10);
PushBack(&mylist2, 20);
PushBack(&mylist2, 30);
PushBack(&mylist2, 40);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
Reverse(&mylist2);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
// 메모리 해제
Release(&mylist2);LinkedList.h
void Release(LinkedList* _List);LinkedList.cpp
void Release(LinkedList* _List)
{
Node* pNode = _List->pHeadNode; // 1
while(pNode) // 2
{
Node* pTemp = pNode->pNext; // 3
free(pNdoe); // 4
pNode->pTemp; // 5
}
}- 가변 배열은 해제하는건 쉬웠다. free(arr.pData); 해주면 된다
- 이유: 가변 배열(동적 배열)은 첫 주소값을 알면 연속적으로 존재하기 떄문이다.
- 연결형 리스트의 메모리 해제는 좀 까다로움.
- 연결이 연속적으로 되있지않고 주소값으로 연결되어있어서
- 연결형 리스트 해제 방법
- // 1 해제할 리스트의 첫번째 노드로 가서 헤드 노드를 받는다.
- // 2 pNode가 널이 될떄까지 while문을 돌린다(마지막 노드 해제하면 중단됨)
- // 3 pTemp 지역 변수에 pNodo의 다음 노드 주소를 저장해둔다.
- // 4 첫번쨰 헤드 노드를 해제한다.
- // 5 pNode 두번째 노드로 연결한다.
- 반복
- 마지막 노드 해제하면 끝.
삽입정렬(강사님)1
void InsertionSort(int* _Arr, int _Count)
{
for (int j = 1; j < _Count; ++j)
{
int Temp = _Arr[j];
for (int i = j - 1; 0 <= i; --i)
{
if (Temp < _Arr[i])
{
_Arr[i + 1] = _Arr[i];
// 끝자리 위치를 가면 넣어버리깅.
if (i == 0)
{
_Arr[i] = Temp;
}
}
else
{
_Arr[i + 1] = Temp;
break;
}
}
}
}삽입정렬(강사님) 2
void InsertionSort(int* _Arr, int _Count)
{
for (int j = 1; j < _Count; ++j)
{
int Temp = _Arr[j]; // 1
int i = j - 1;
for (; 0 <= i; --i) // 2
{
if (Temp < _Arr[i])
{
_Arr[i + 1] = _Arr[i];
}
else
{
break;
}
}
_Arr[i + 1] = Temp;
}
}- // 1은 _Arr[j]값을 일시적으로 복사해서 값을 유지하는것.
- // 2 for문은 방법이 2가지
- 방법 1 : 하나하나 체크해버릴때마다 값을 변경하는것.
- 강사님 1
- 방법 2 : 다 일일이 체크하고 작을경우 바꿔버리는 경우.
- 강사님 2
- 방법 1,2는 연산량은 같다.
- i는 개별 요소들 체크문.
- 방법 1 : 하나하나 체크해버릴때마다 값을 변경하는것.
강의 코드
main.cpp
#include <iostream>
#include <vector>
#include <list>
#include <map>
using namespace std;
#include "DArr.h"
#include "LinkedList.h"
void InsertionSort(int* _Arr, int _Count)
{
for (int j = 1; j < _Count; ++j)
{
int Temp = _Arr[j];
int i = j - 1;
for (; 0 <= i; --i)
{
if (Temp < _Arr[i])
{
_Arr[i + 1] = _Arr[i];
}
else
{
break;
}
}
_Arr[i + 1] = Temp;
}
}
int main()
{
int iArr[100] = {};
DArr arr1 = {};
DArr arr2 = {};
DArr arr3 = {};
DArr arr4 = {};
InitDArr(&arr1);
PushData(&arr1, 10);
PushData(&arr1, 20);
PushData(&arr1, 30);
PushData(&arr1, 40);
PushData(&arr1, 50);
int data = 0;
for (int i = 0; i < arr1.CurCount; ++i)
{
data = GetData(&arr1, i);
}
// data = GetData(&arr1, 5);
free(arr1.pData);
// 연결형 리스트
LinkedList mylist = {};
PushBack(&mylist, 10);
PushBack(&mylist, 20);
PushBack(&mylist, 30);
data = GetData(&mylist, 0);
data = GetData(&mylist, 1);
data = GetData(&mylist, 2);
Release(&mylist);
LinkedList mylist2 = {};
PushBack(&mylist2, 10);
PushBack(&mylist2, 20);
PushBack(&mylist2, 30);
PushBack(&mylist2, 40);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
//data = GetData(&mylist2, 4);
Reverse(&mylist2);
data = GetData(&mylist2, 0);
data = GetData(&mylist2, 1);
data = GetData(&mylist2, 2);
data = GetData(&mylist2, 3);
Release(&mylist2);
// 삽입 정렬
int Arr[4] = { 16, 4, 22, 7 };
InsertionSort(Arr, 4);
return 0;
}LinkedList.h
#pragma once
// 연결형 리스트
struct Node
{
int Data;
Node* pNext;
};
struct LinkedList
{
Node* pHeadNode;
int CurCount;
};
void PushBack(LinkedList* _List, int _Data);
int GetData(LinkedList* _List, int _Idx);
void Reverse(LinkedList* _List);
void PushFront(LinkedList* _List, int _Data);
void Release(LinkedList* _List);LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
#include <assert.h>
void PushBack(LinkedList* _List, int _Data)
{
// 입력된 데이터를 저장할 새로운 노드를 할당받고, 입력된 데이터를 노드안에 복사한다.
Node* pNewNode = (Node*)malloc(sizeof(Node));
pNewNode->Data = _Data;
pNewNode->pNext = nullptr;
// 만약 리스트에 입력되는 데이터가 처음이라면
if (nullptr == _List->pHeadNode)
{
_List->pHeadNode = pNewNode;
}
// 리스트에 입력된 데이터가 1개 이상이라면
else
{
// 1. 리스트가 보유한 노드 중, 가장 마지막 노드를 찾는다.
Node* pNode = _List->pHeadNode;
/*while (true)
{
pNode = pNode->pNext;
if (nullptr == pNode->pNext)
break;
}*/
while (pNode->pNext) { pNode = pNode->pNext; }
// 2 . 찾은 노드의 pNext 를 현재 생성된 노드를 가리킨다(연결)
pNode->pNext = pNewNode;
}
// 데이터 카운트를 1 증가시킨다.
_List->CurCount++;
}
int GetData(LinkedList* _List, int _Idx)
{
// 리스트에 입력된 데이터 개수 이상의 인덱스를 지정한 경우
assert(!(_List->CurCount <= _Idx));
Node* pNode = _List->pHeadNode;
for (int i = 0; i < _Idx; ++i)
{
pNode = pNode->pNext;
}
return pNode->Data;
}
void PushFront(LinkedList* _List, int _Data)
{
// 1. 입력된 데이터를 저장할 노드 1개 만큼의 메모리를 동적할당 한다.
// 입력된 데이터를 해당 노드안에 복사한다.
Node* pNewNode = (Node*)malloc(sizeof(Node));
pNewNode->Data = _Data;
// 2. 새로 생성된 노드가 가정 처음이 되어야 하니까, 리스트가 헤드포인터로 해당 노드를 가리킨다.
pNewNode->pNext = _List->pHeadNode;
_List->pHeadNode = pNewNode;
// 3. 데이터 카운트 증가
_List->CurCount++;
}
void Release(LinkedList* _List)
{
Node* pNode = _List->pHeadNode;
while (pNode)
{
Node* pTemp = pNode->pNext;
free(pNode);
pNode = pTemp;
}
}
// 재귀 함수
void Reverse_Re(Node* _Node, LinkedList* _List)
{
if (nullptr != _Node->pNext)
{
bool bHead = false;
if (_Node == _List->pHeadNode)
bHead = true;
Reverse_Re(_Node->pNext, _List);
_Node->pNext->pNext = _Node;
if (bHead)
_Node->pNext = nullptr;
}
else
{
// _Node 가 가리키고 있는 노드가 현재 가장 마지막 노드이다.
_List->pHeadNode = _Node;
}
}
void Reverse(LinkedList* _List)
{
Reverse_Re(_List->pHeadNode, _List);
//Node* pNode = _List->pHeadNode;
//while (pNode->pNext)
//{
// pNode = pNode->pNext;
//}
//pNode->pNext = nullptr;
}1차 23.12.20
2차 23.12.21
3차 23.12.22
4차 23.12.25
5차 23.12.26
6차 24.01.02
:D