✔연결 리스트
- 연결 리스트는 비연속적인 선형 자료구조이다.
- 리스트의 노드는 데이터 필드와 링크 필드로 구성되어 있고, 링크 필드는 포인터를 통해 다음 노드의 메모리 주소를 저장한다.
-> 헤드 노드(첫 번째 노드)를 가리키는 헤드 포인터의 값만 알고 있어도 모든 노드에 접근할 수 있다. - 데이터를 추가할 때마다 데이터 크기만큼의 메모리 공간을 동적 할당한다.
-> 동적 할당을 하기 때문에, 가변 배열과 똑같이 힙 메모리 공간을 사용한다. - 논리적 저장 순서와 물리적 저장 순서가 달라서 검색이 불편하다.
가변 배열 : 검색 용이
연결 리스트 : 삽입/삭제 용이
(단방향) 연결 리스트 객체 구현
- 데이터 추가할 때 데이터 개수를 기억해야 한다.
- 가변 배열은 배열 크기가 선언된 만큼 고정되어 있기 때문에 데이터 수의 최대치를 알아야 했지만, 연결 리스트는 정해진 크기가 없으므로 최대치를 알 필요가 없다.
- 데이터 주소가 각각 다르기 때문에, 리스트는 첫 번째 노드의 주소값을 알아야 한다.
- ❗ 헤더에 구조체 정의할 때 주의
-> 구조체 내부는 정의 마치기 전 상태이기 때문에, 정의 후에 생성되는 구조체 별명을 사용할 수 없음.
-> 이렇게 정의해 주기.
1) 데이터 초기화 함수
: 연결리스트 객체를 생성한 후엔 초기화해줘야 한다.
선언
void InitList(tLinkedList* _pList);정의
void InitList(tLinkedList* _pList)
{
//데이터 안 들어온 상태에선 노드 만들 이유 없으니 널포인터 넣기
_pList->pHeadNode = nullptr;
_pList->iCount = 0;
}2) 데이터 추가 함수
: 현재 데이터 중 가장 마지막에 데이터 추가하기.
- 데이터를 추가하려면 먼저 노드가 필요하다.
tNode node = {}; // XtNode* pNode = (tNode*)malloc(sizeof(tNode)); // O-> 지역변수로 노드를 생성하면 함수 종료될 때 사라지기 때문에, 동적 할당을 이용하여 힙 메모리를 사용해야 한다.
-> 그리고 노드 단위로 데이터에 접근하고 사용할 것이기 때문에, 힙 메모리 주소를 노드 포인터로 받아와야 한다.
-
리스트의 시작 주소와, 추가할 데이터를 인자로 받는다.
-
인자로 받는 데이터를 리스트 맨 뒤에 추가할 것이므로, 그 다음 노드는 존재하지 않는다.
pNode->pNextNode = nullptr;-
추가할 데이터가 처음이면 리스트의 헤드가 새로 생성한 노드를 가리키고,
처음이 아니라면 현재 가장 마지막에 있는 노드가, 새로 생성시킨 노드의 주소를 가리키게 한다. -
코드 작성 중 리스트의 헤드 노드가 변경되면 안 되므로 지역 변수를 활용한다.
// _pList->pHeadNode; 위험!
tNode* pCurFinalNode = _pList->pHeadNode;선언
void PushBack(tLinkedList* _pList, int _iData);정의
void PushBack(tLinkedList* _pList, int _iData)
{
//데이터 저장할 노드 생성하고 데이터 복사
tNode* pNode = (tNode*)malloc(sizeof(tNode));
pNode->iData = _iData;
pNode->pNextNode = nullptr;
//추가할 데이터가 처음인지 아닌지 확인
if(0 == _pList->iCount)
{
_pList->pHeadNode = pNode;
}
else
{
tNode* pCurFinalNode = _pList->pHeadNode;
while (pCurFinalNode->pNextNode)
{
pCurFinalNode = pCurFinalNode->pNextNode;
}
pCurFinalNode->pNextNode = pNode;
}
++_pList->iCount;
}3) 메모리 해제 함수
- 힙 메모리는 비연속적이기 때문에 데이터 하나하나 찾아서 할당 해제시켜줘야 한다.
- 포인터
pDeletNode로 삭제할 리스트의 헤드 노드를 가리킨다. - 헤드 노드가 null이 아닐 때,
1-1. 포인터pNext로pDeletNode의 다음 노드를 가리킨다.(주소 기억해두려고)
1-2.pDeletNode이 가리키던 헤드 노드를 할당 해제한다.
1-3.pDeletNode가 이제pNext를 가리킨다. (한 칸씩 이동하기) - 리스트의 헤드 노드가 null이면(삭제할 데이터가 없으면) 종료한다.
선언
void ReleaseList(tLinkedList* _pList);정의
void ReleaseList(tLinkedList* _pList)
{
tNode* pDeletNode = _pList->pHeadNode;
while (pDeletNode)
{
tNode* pNext = pDeletNode->pNextNode;
free(pDeletNode);
pDeletNode = pNext;
}
}과제 - PushFront() 구현
- PushBack()과 반대로, 데이터가 리스트 앞에서부터 추가되는 함수 구현
가변배열의 경우)
만약 맨 앞에 데이터를 추가하려고 한다면, 기존 데이터를 모두 한 칸씩 뒤로 이동시켜야 한다. O(n) 매우 비효율적
리스트의 경우)
데이터 개수와 관계없이, 포인터가 가리키는 관계만 바꾸면 됨. O(1)
선언
void PushFront(tLinkedList* _pList, int _iData);정의
void PushFront(tLinkedList* _pList, int _iData)
{
//기존의 헤드는, 새로 생성시킨 노드의 다음 노드로 지정된다.
tNode* pNewNode = (tNode*)malloc(sizeof(tNode));
pNewNode->iData = _iData;
pNewNode->pNextNode = _pList->pHeadNode;
//리스트의 헤드노드 포인터를 갱신한다.
_pList->pHeadNode = pNewNode;
//데이터 카운트 증가
++_pList->iCount;
}[참고]
https://youtu.be/8HVfEul9nqk 리스트(1)
https://youtu.be/rbB3xbJN4qE 리스트(2)
https://youtu.be/V9mByvOuCac 리스트(3)
https://velog.io/@kon6443/Data-Structure-C-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-list
https://seohyune.tistory.com/18
https://thinking-developer.tistory.com/68
