단일 연결 목록에 대해 알기 전에 노드라는 개념을 먼저 알아야할 필요가 있습니다.
노드란? 데이터 구조에서 데이터와 연결 정보를 포함하는 기본 요소로, 비트와 바이트를 포함할 수 있습니다. 노드는 데이터 저장 및 연결의 역할을 합니다. 우리가 지난 글들에서 자주 다뤘던 비트와 바이트 단위의 데이터와 포인터를 포함하는 구조체를 구현합니다. 연결 리스트, 트리, 그래프 등의 데이터 구조에서 다른 노드와의 관계를 표현합니다.
그림으로 설명드리겠습니다.
노드는 받아들이는 데이터(Data)와 다음 노드와의 연결 정보(Next)로 구성되어있습니다. 이제 그 노드를 다루는 리스트 중에서 단일 연결 리스트에 대해 알아보겠습니다.
위의 그림은 리스트를 표현한 것입니다. 풀어서 정리하겠습니다.
- 리스트 길이: 노드의 개수
- 리스트의 1번 노드를 헤드(Head)라고 표현
- 리스트의 마지막 노드를 테일(Tail)이라고 표현
- 노드의 Data에는 값, Next에는 다음 노드 주소 즉, 포인터가 들어가있습니다.
- 테일 노드는 다음 노드가 없기 때문에 주소값이 없어 NULL이 들어가있습니다.
- 리스트는 구조체를 주로 다뤄 표현합니다. (struct문)
리스트의 기초 개념을 알아보았으니 이제 코드를 확인하겠습니다.
<선언>
#include <stdio.h>
#include <malloc.h>
//노드 구조체 설정
typedef struct _SNode //_SNode 구조체 따로 별칭을 붙이겠다.
{
int data; //노드가 저장하는 데이터
struct _SNode* pNext; //다음 노드를 가리키는 포인터
} SNode; //SNode라는 별칭을 말이다.
SNode* g_pHead = NULL; //g(lobal)_p(ointer)Head 전역 포인터 값을 NULL로 초기화
void PushFront(int _data); //헤드에 새 노드를 삽입할 함수
void PushBack(int _data); //테일에 새 노드를 삽입할 함수
void Insert(int _idx, int _data); //_idx 위치 노드에 데이터를 삽입할 함수
void RemoveFront(); //헤드 노드 삭제할 함수
void RemoveBack(); //테일 노드 삭제할 함수
void Remove(int _idx); //리스트 중간 노드 삭제할 함수
void RemoveWithData(int _data); //리스트 내 특정 데이터 삭제할 함수
void Clear(); //리스트의 모든 노드를 삭제하는 함수
// 재귀함수(Recursive) //함수나 과정이 자기 자신을 호출하여 문제를 해결하는 기법
void ClearRecursive(SNode* _pNode); //재귀함수로 자신의 상태에 따라 노드를 삭제하는 함수
// 배열: Length, 리스트: Count
int Count(); //리스트 함수
void PrintAll(); //출력 함수코드에 맞춰 주석으로 어떤 기능을 하는 함수인지와 어떤 뜻을 가진 코드인지를 적어놓았습니다. 여기서 RemoveWithData 함수는 이 글에서는 제외하겠습니다.
<삽입 기능 함수>
void PushFront(int _data) //헤드에 새 데이터 추가
{
SNode* pNewNode = //pNewNode(새 노드 주소) =
(SNode*)malloc(sizeof(SNode)); //SNode구조체의 크기만큼 메모리 동적 할당하고 그 시작 주소를
//반환하여 SNode* 타입 포인터로 캐스팅해 새 노드를 가리킴
if (pNewNode) //pNewNode는
{
pNewNode->data = _data; //pNewNode의 data는 _data;
pNewNode->pNext = g_pHead; //pNewNode의 pNext는 g_pHead; (기존 헤드 노드가 2번째 노드)
g_pHead = pNewNode; //g_pHead는 pNewNode다. (새로운 노드가 헤드 노드가 된다)
}
}
void PushBack(int _data) //테일에 새 데이터 추가
{
if (g_pHead == NULL) //헤드가 없을 경우에 대한 NULL 예외처리
{ //헤드가 없는 경우는 리스트가 비어있다는 뜻
//g_pHead = (SNode*)malloc(sizeof(SNode));
//g_pHead->data = _data;
//g_pHead->pNext = NULL;
PushFront(_data); //PushFront 함수 호출해서 헤드 노드 추가
return; //함수 종료
}
SNode* pIter = g_pHead; //pIter라는 SNode포인터는 헤드 노드 주소값
while (pIter->pNext != NULL) //pIter의 pNext포인터가 NULL이 될 때까지 반복
pIter = pIter->pNext; //pIter는 다음 노드로 이동
SNode* pNewNode = //SNode* 형태의 pNewNode라는 새 노드 =
(SNode*)malloc(sizeof(SNode)); //SNode구조체의 크기만큼 메모리 동적 할당하고 그 시작 주소를
//반환하여 SNode* 타입 포인터로 캐스팅해 새 노드를 가리킴
pNewNode->data = _data; //새 노드의 데이터는 _data
pNewNode->pNext = NULL; //새 노드의 Next주소는 NULL (테일 노드이기 때문에)
pIter->pNext = pNewNode; //pIter의 pNext는 pNewNode (리스트의 테일 노드이기 때문에)
}
void Insert(int _idx, int _data) //int_data를 int _idx위치에 데이터 삽입 함수
{//예외처리
if (_idx < 0 || _idx >= Count()) //인덱스가 0미만: 리스트가 존재하지 않는 상황이거나
{ //인덱스가 리스트의 크기보다 크거나 같을 경우
printf("ERROR] Out of index!\n"); //ERROR] Out of index! 출력
return; //함수 종료
}
//예외처리
if (_idx == 0) //인덱스가 0일 경우 (리스트가 없음)
{
PushFront(_data); //PushHead함수 호출해서 리스트를 생성해라
return; //함수 종료
}
SNode* pIter = NULL; //SNode* 형식의 pIter가 NULL일 경우 (NULL 예외처리)
for (int i = 0; i < _idx; ++i) //인덱스보다 작을 때까지 반복문
{
if (pIter == NULL) //pIter이 NULL일 경우
{
pIter = g_pHead; //pIter는 헤드 노드
continue; //계속 for문 진행
}
pIter = pIter->pNext; //pIter은 다음 노드를 가리키는 포인터
}
SNode* pNewNode = //새 노드의 SNode* 형식는
(SNode*)malloc(sizeof(SNode)); //SNode구조체의 크기만큼 메모리 동적 할당하고 그 시작 주소를
//반환하여 SNode* 타입 포인터로 캐스팅해 새 노드를 가리킴
pNewNode->data = _data; //새 노드의 데이터는 _data
pNewNode->pNext = NULL; //새 노드의 pNext는 NULL로 초기화
pNewNode->pNext = pIter->pNext; //새 노드의 다음 노드 주소는 현재 노드의 다음 노드 주소
pIter->pNext = pNewNode; //현재 노드의 다음 노드 포인터는 새 노드 주소 포인터
}위의 코드는 삽입 기능의 함수들에 대한 설명입니다. 위를 이해하기 위해선 2가지를 알고 있어야 합니다.
- pIter: 현재 노드의 포인터를 의미합니다.
- pNext: 다음 노드의 포인터를 의미합니다.
- NewNode: 새로운 노드를 의미합니다.
void RemoveFront() //헤드 노드를 없애는 함수
{
if (g_pHead == NULL) return; //헤드 노드 포인터가 NULL일 경우 함수 종료 (예외 처리)
SNode* pDelNode = g_pHead; //SNode*형식의 pDelNode는 헤드 노드 포인터
g_pHead = pDelNode->pNext; //헤드 노드 포인터는 pDelNode의 Next포인터
if (pDelNode != NULL) //pDelNode가 NULL이 아니라면 조건문
{
printf("RemoveFront: %d\n", //RemoveFront: pDelNode의 data값 출력
pDelNode->data);
free(pDelNode); //pDelNode의 공간 해제
pDelNode = NULL; //pDelNode의 해제한 공간을 NULL로 초기화
}
}
void RemoveBack() //테일 노드를 없애는 함수
{
if (g_pHead == NULL) return; //헤드 노드 포인터가 NULL일 경우 함수 종료 (예외 처리)
if (g_pHead->pNext == NULL) //헤드 노드 포인터의 pNext가 NULL일 경우
{
if (g_pHead != NULL) //헤드 노드 포인터가 NULL일 경우
{
free(g_pHead); //g_pHead의 공간 해제
g_pHead = NULL; //g_pHead의 해제한 공간을 NULL로 초기화
}
return; //함수 종료
}
SNode* pIter = g_pHead; //SNode*형태의 pIter는 헤드 노드 포인터
while (pIter->pNext->pNext != NULL) //pIter의 다음 노드의 다음 노드의 주소가 NULL이 될 때까지
pIter = pIter->pNext; //pIter는 pIter의 다음 노드 포인터
if (pIter->pNext != NULL) //pIter의 pNext가 NULL이 아니라면 조건문
{
printf("RemoveBack: %d\n", //RemoveBack: pIter의 다음 주소의 포인터의 값
pIter->pNext->data);
free(pIter->pNext); //pIter의 pNext의 공간 해제
pIter->pNext = NULL; //pIter의 pNext를 NULL로 초기화
}
}
void Remove(int _idx)
{
// if (CheckEmpty()) return; //밑의 조건문을 함수로 정리해도 좋다.
if (g_pHead == NULL) return; //헤드 노드 포인터가 NULL이라면 함수 종료 (예외 처리)
// if (CheckOutOfIndex(_idx)) //밑의 조건문을 함수로 정리해도 좋다.
if (_idx < 0 || _idx >= Count())//인덱스가 0미만이거나 리스트 길이보다 크거나 같을 경우
{
printf("ERROR] Out of index!\n"); //ERROR] Out of index!를 출력
return; //함수 종료
}
if (_idx == 0) //인덱스가 0일 때
{
RemoveFront(); //RemoveFront 함수 호출해서 헤드 노드 없애라
return; //함수 종료
}
SNode* pIter = NULL;
for (int i = 0; i < _idx; ++i) //인덱스값보다 작은 경우 반복문
{
if (pIter == NULL) //pIter가 NULL이라면
{
pIter = g_pHead;//pIter는 헤드 노드 포인터
continue; //계속 진행
}
pIter = pIter->pNext; //pIter는 pIter의 pNext(다음 노드 주소)
}
SNode* pDelNode = pIter->pNext; //SNode* 형식의 pDelNode는 pIter의 pNext(다음 노드 주소)
pIter->pNext = pDelNode->pNext; //pIter의 pNext는 pDelNode의 pNext
if (pDelNode != NULL) //pDelNode가 NULL이 아니라면 조건문
{
printf("Remove: %d\n", pDelNode->data); //Remove: pDelNode의 data값
free(pDelNode); //pDelNode에 할당된 공간 해제
pDelNode = NULL; //pDelNode의 해제된 공간 NULL로 초기화
}
}위는 리스트에 존재하는 노드를 삭제할 때 사용되는 함수들의 정의에 대한 해석들입니다.
<리스트에 사용될
void Clear() //없애는 함수
{
if (g_pHead == NULL) return; //헤드 노드 포인터가 NULL일 경우 함수 종료 (예외 처리)
ClearRecursive(g_pHead); //ClearRecursive(g_pHead) 함수 호출
g_pHead = NULL; //헤드 노드 포인터는 NULL로 초기화
}
void ClearRecursive(SNode* _pNode) //SNode* 형식의 _pNode를 제거하는 함수
{
if (_pNode == NULL) return; //_pNode가 NULL일 경우 함수 종료 (예외 처리)
ClearRecursive(_pNode->pNext); //_pNode의 pNext를 ClearRecursive함수 호출 (재귀 함수)
if (_pNode != NULL) //_pNode가 NULL이 아닐 경우
{
printf("Clear: %d\n", _pNode->data); //Clear: _pNode의 data를 출력
free(_pNode); //_pNode에 할당된 공간 해제
_pNode = NULL; //_pNode의 해제된 공간을 NULL로 초기화
}
}
int Count() //리스트의 크기 표시 함수
{
if (g_pHead == NULL) return 0; //헤드 노드 포인터가 NULL이라면 0 반환
SNode* pIter = g_pHead; //SNode* 형식 pIter는 헤드 노드 포인터
int cnt = 0; //cnt 변수를 0으로 초기화
while (pIter != NULL) //pIter이 NULL이 될 때까지 반복
{
pIter = pIter->pNext; //pIter는 pIter의 pNext
++cnt; //cnt 변수를 반복할 때마다 +1씩 해라
}
return cnt; //cnt를 반환
}
void PrintAll() //출력 함수
{
// STL: 반복자(Iterator)
SNode* pIter = g_pHead; //SNode* 형식의 pIter은 헤드 노드 포인터
if (pIter == NULL) //pIter이 NULL이라면
{
printf("List is empty!\n"); //List is empty! 출력
return; //함수 종료
}
int cnt = 0; //cnt 변수 0으로 초기화
while (pIter != NULL) //pIter이 NULL이 될 때까지 반복
{
printf("[%d]-", pIter->data); //[pIter의 data] 출력
pIter = pIter->pNext; //pIter은 pIter의 pNext
++cnt; //cnt에 반복할 때마다 +1씩 증가
}
printf("(%d)\n", cnt); //(cnt) 출력
}위는 Clear함수와 Count, PrintAll함수에 대한 설명들입니다. 위의 함수들을 다루는 main( )를 다뤄보겠습니다.
<Main함수>
void main()
{
// Single Linked-List(단일 연결 목록)
// 슈도코드, 수도코드(Pseudo-Code)
// 의사코드
PushFront(1); //헤드 노드에 1을 추가 [1]
PushFront(2); //헤드 노드에 2를 추가 [2][1]
PushBack(10); //테일 노드에 10을 추가 [2][1][10]
PushBack(20); //테일 노드에 20을 추가 [2][1][10][20]
PrintAll(); //[2][1][10][20](4)
printf("Count: %d\n", Count()); //Count: 4
printf("\n");
Insert(-1, 100); //ERROR] List is empty! (-1이기 때문에)
Insert(10, 100); //ERROR] List is empty! (10은 count 4보다 높기 때문에)
Insert(0, 100); //[100][2][1][10][20](4)
Insert(Count() - 1, 200); //[100][2][1][10][200][20] (0부터 시작하기 때문에 5번째 자리)
PrintAll(); //[100][2][1][10][200][20](6)
Insert(3, 777); //[100][2][1][777][10][200][20] (0부터 시작하기 때문에 4번째 자리)
PrintAll(); //[100][2][1][777][10][200][20](7)
printf("\n");
//RemoveFront();
//RemoveBack();
Remove(0); //RemoveFront: 10 \ [2][1][777][200][10][20](6)
Remove(Count() - 1); //Remove: 20 \ [2][1][777][10][200](5)
PrintAll(); //[2][1][777][10][200](5)
Remove(2); //Remove: 777
PrintAll(); //[2][1][10][200](4)
Clear(); //Clear: 200 \ Clear: 10 \ Clear: 1 \ Clear: 2
}main 함수의 출력값들입니다.
끝
'프로그래밍 C언어' 카테고리의 다른 글
| 이진 트리 (BinaryTree) (0) | 2024.08.25 |
|---|---|
| 이중 연결 리스트 (Double Linked-List) (0) | 2024.08.25 |
| 큐 (Queue) (0) | 2024.08.21 |
| 스택 (Stack) (0) | 2024.08.21 |
| 다차원배열 (Multi-Dimensional Array) (0) | 2024.08.21 |