C언어 | 링크드리스트 기초 총정리 | 삽입, 삭제, 정렬, 검색, 메모리 외
C언어 링크드 리스트는 많은 학생들에게 학업에 대한 스트레스를 줬을 것이라 생각한다.
특히 프로그래밍 학습의 진도가 너무 빨리 나갈 때 배워야 할 것은 많고 시간은 짧아 보인다.
하지만 이런 알고리즘을 배우는데는 시간이 필요하다. 다행인 것은 그래도 한번 이해하면 오래도록 기억할 수 있다.
새로운 기술은 유행을 타서 부침이 있지만 알고리즘은 기초원리라서 한번 배워두면 두고두고 사용할 수 있다.
특히 C언어로 배우는 알고리즘은 거의 모든 언어로 코드를 이식할 수 있다.
물론 타 언어에서 C언어를 모듈로 사용하는 것도 가능하다. 성능이 필요한 프로그램의 경우 그렇게 하는 경우도 있다.
알고리즘은 수학과 비슷한게 앞쪽의 기초공사(학습)를 하지 않고 그 다음 단계의 알고리즘을 이해하기가 어렵다.
예를 들어 포인터와 동적 메모리 할당에 대하여 모른체로 링크드 리스트를 만들 수는 없다.
-> 포인터를 알기위해서는 배열을 알아야 한다.
-> 배열을 알기 위해서는 변수를 알아야 한다.
-> 변수를 알기 위해서는 메모리의 저장 단위를 알아야 한다.(byte)
-> 바이트를 알기 위해서는 이진법을 알아야 한다.
-> 제일 중요한 것: 메모리 구조를 이해해야 한다. (stack, heap 등)
그리고 구조체, 함수, 지역변수 등의 개념이 없다면 코드를 따라해도 응용에 어려움을 겪을 것이다.
링크드 리스트 챕터에서 진행이 안된다면 잠시 내려 놓는 것도 방법이다. 처음으로 다시 돌아가 변수부터 배워야 한다. 한번에 끝을 내려는 자세보다 프로그래밍 학습이란 긴 여정에서 알고리즘을 내것으로 만드는게 중요하다. 4차 산업 시대에는 누구나 다 프로그래밍을 하게 될 날이 온다. 길게 봐도 이 지식들이 헛되지 않을 것이다.
학습시간이 길어져 봤자 아무것도 아니다. 한번 정도 복습하면 대부분의 학생들은 링크드 리스트에 대하여 충분히 이해할 수 있을 것이다. 링크드 리스트를 잘 다룰 수 있다면 그 다음은 실전을 통해 지식을 쌓을 단계이다.
링크드 리스트 코드는 인터넷에 많이 있는데 종합적으로 모아 놓은 코드가 별로 없어서 이 포스트에 총정리를 해둔다.
가장 기본 기능인 리스트 삽입, 추가, 삭제, 정렬, 검색 그리고 리스트의 메모리 상태 출력에 대한 함수가 들어있다.
기본 링크드 리스트를 만들어 본 후 자신만의 자료형으로 확장시킬 수 있을 것이다. 문자의 배열을 담는 리스트, float 형 리스트 등 생각해볼 수 있는 리스트는 무궁무진하다. 그런 생각을 하던 프로그래머들이 결국 class 를 만들어서 보통의 사람들이 직접 자료구조를 만들지 않아도 된다. 자신만의 편리한 기능을 추가하다 보면 언젠가 자신만의 훌륭한 코드를 갖게 될 것이다.
지금은 매니지드 언어가 인기가 많고 또 가성비가 좋기 때문에 C를 배우는 사람이 줄어드는 것 같지만, 여전히 컴퓨터에 대한 원초적인 호기심을 충족시키고 싶다면 거쳐야 하는 관문이다.
*매니지드 언어 : 메모리 관리를 가상머신이 하는 언어
전체 소스코드는 길기 때문에 모든 것을 상세하게 기술하지는 않을 것이다.
링크드 리스트는 몇가지 중요한 기법만 알면 다른 문제는 스스로 풀리게 된다.
*먼저 위와 같은 구조체를 정의한다. 구조체 안에는 하나의 포인터와 하나의 정수형 데이터가 들어있다. 나중에 다른 데이터를 확장하는 것은 어렵지 않다. 구조체 안에 구조체를 포함시키는 것도 가능하다. 여기서는 링크드 리스트의 구조를 만드는 것이므로 데이터 하나만 사용한다.
*링크드 리스트의 기능들을 위해 필요한 함수들을 선언한다. 대부분 구조체 포인터와 데이터를 받아서 조작하는 함수가 많다.
*리스트를 생성한다. 정확히는 리스트의 헤드(머리) 부분이다. 리스트를 생성과 초기화 함수도 뒤에 만들어 뒀다.
* 가장 기본적인 맨 앞에다 추가하는 함수다.
매개변수는 리스트의 첫번째 노드인 헤드다.
1. 새로운 노드를 생성하면 헤드의 next (다음 노드 주소)를 대입한다.
2. 새로운 노드의 데이터를 입력한다.
3. 헤드노드의 next를 새로운 노드의 주소로 바꾼다.
요 기본은 어디나 동일하게 적용된다.
링크드 리스트의 모양이 위와 같기 때문에 어떻게 연결해야 하는지 알 수 있다. 새로운 노드가 들어가는 곳을 연결시키는 일이다.
* append 는 리스트의 끝에다가 추가하는 함수이다.
리스트의 다음이 NULL 이면 (리스트가 비어있으면) NULL을 자신의 주소로 바꾼다.
리스트가 두개 이상이면 끝자리를 찾아야한다. List를 traverse 횡단하며 찾는다.
Node *cur 는 검색을 위한 노드다. 이 *cur 가 상당히 중요한게 다른 함수에도 같은 원리로 작동한다. 리스트는 for문을 루프하듯이 데이터에 접근할 수가 없다. 이 cur가 손가락 처럼 리스트를 여기저기 횡단하며 원하는 주소와 데이터를 찾아준다.
while 문을 돌리면 cur 노드는 cur->next 가 NULL 을 가리키게 된다. 즉 마지막 노드이다.
다시 새로운 노드를 생성하여 마지막 노드의 next에 새로운 노드의 주소를 연결시킨다.
메모리를 가리키기 때문에 cur 노드가 곧 매개변수로 받은 *list 와 동일하다.
(포인터로 하는 것은 매개변수의 실제 메모리 값을 조작하는 것이다. )
* 리스트를 보여주는 함수다.
여기서도 리스트의 손가락 노드를 만들어 리스트의 끝까지 이동시킨다. (cur = cur->next)
리스트에 들어있는 모든 값을 출력한다.
* 동적 메모리 할당을 한 후 사용이 끝났다면 메모리를 해제시켜줘야 한다.
여기서도 cur 노드로 while 루프를 돌면서 하나씩 메모리를 해제시키고 있다.
Node *next 는 cur의 메모리를 해제시켜버리면 다음 주소도 사라져버리므로 next 에 주소를 임시로 저장해뒀다가 whlie 조건식 전에 cur 에 전달한다.
* 리스트 특정 위치에 삽입하는 함수이다.
position (위치) 를 찾아서 입력한다. 이게 위치를 찾기가 좀 어렵다. cur로 루프하면서 위치를 찾은 다음에 찾은 요소의 앞요소의 next를 새로운 노드의 next 에 대입하고 앞요소의 next는 현재 새로운 노드의 주소로 바꾼다. 위치 찾기가 어려우면 printf ("%d") 로 카운터를 돌리면서 찾으면 한층 수월하다.
* 버블소트 함수다. 여기도 cur 로 중첩 for문 안에서 루프한다. 바깥의 for문이 돌때 마다 cur 를 다시 list->next로 초기화 시켜줘야 한다. 그렇지 않으면 중첩 for문을 한번만 돌고 끝나버린다.
cur->next == NULL 이 곧 리스트의 끝임에 주의한다. 루프를 도는 것은 같은데 루프의 조건이 일반 변수를 다루는 for문 하고 다르다.
* 그 밖에 검색함수나 배열을 입력하는 함수 등의 함수도 거의 비슷한 알고리즘으로 작동한다. 대부분 cur 노드를 활용한다.
재귀 함수는 만들지 않았다. 함수의 안정성을 위한 코드는 추가하지 않았다. 그런 부분들을 조금씩 보완하다보면 실력도 늘고 좋은 코드를 작성할 수 있을 것이다.
코딩은 함수 한 개라도 직접 짜보는 것이 실력 향상에 중요하다.
이 포스팅이 C언어 수업을 듣는 사람들에게 도움이 되다면 기쁠 것이다.
* 전체 소스 코드
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define toString(variable) #variable
typedef struct Node {
struct Node *next;
int data;
}Node;
void appendFirst(Node *ptr, int newData);
void append(Node *ptr, int newData);
void showList(Node *ptr);
void deleteList(Node *ptr);
int getNodeLength(Node *ptr);
void insert(Node *ptr, int position, int NewData);
void swapNodeData(Node *node1, Node *node2);
void bubbleSortNode(Node *ptr, int size);
void showListMemory(Node *ptr);
void arrayToList(Node *ptr, int array[], int arraySize);
bool searchList(Node *ptr, int number);
Node* getList();
void generateLottoList(Node *list);
int main(int argc, char const *argv[])
{
int count = 0;
int length = 0;
// list1 리스트 맨 앞에 추가하기
printf("[맨 앞에 리스트 추가하기]\n");
Node *list1 = malloc(sizeof(Node));
list1->next = NULL;
count = 10;
for (int i = 1; i <= count; i++)
{
if(i % 2 == 0) appendFirst(list1, i);
}
showList(list1);
length = getNodeLength(list1);
printf("list1 length : %d\n\n", length);
deleteList(list1);
// list2 리스트 마지막에 추가하기
printf("[마지막에 리스트 추가하기]\n");
Node *list2 = malloc(sizeof(Node));
list2->next = NULL;
count = 10;
for (int i = 1; i <= count; i++)
{
if(i % 2 == 1) append(list2, i);
}
showList(list2);
length = getNodeLength(list2);
printf("list2 length : %d\n\n", length);
deleteList(list2);
// list3 주어진 위치에 리스트 삽입하기
printf("[특정 위치에 리스트 추가하기]\n");
Node *list3 = malloc(sizeof(Node));
list3->next = NULL;
count = 5;
for (int i = 1; i <= count; i++)
{
append(list3, i);
}
printf("*삽입전: ");
showList(list3);
length = getNodeLength(list3);
printf("list3 length : %d\n\n", length);
insert(list3, 0, 1523);
insert(list3, 0, 7);
printf("*위치 (0) 에 (1523,7) 삽입후:\n");
showList(list3);
length = getNodeLength(list3);
printf("list3 length : %d\n\n", length);
insert(list3, 1, 99);
insert(list3, 5, 23);
insert(list3, getNodeLength(list3), 777);
printf("*위치 (1, 5, 마지막)에 (99, 23, 777) 삽입후:\n");
showList(list3);
length = getNodeLength(list3);
printf("list3 length : %d\n", length);
deleteList(list3);
// list4 버블소트로 정렬하기
printf("\n[배열을 리스트에 입력하고 버블소트로 정렬하기]\n");
int array[] = {14, 80, 99, 77, 5, 300, 55, 70, 7, 24, 9, 150, 3, 70, 1};
Node *list4 = malloc(sizeof(Node));
list4->next = NULL;
// 배열을 리스트에 입력한다.
int arrSize = sizeof(array)/sizeof(int);
arrayToList(list4, array, arrSize);
printf("\n*정수형 배열을 리스트에 입력\n");
showList(list4);
bubbleSortNode(list4, getNodeLength(list4));
printf("\n*버블소트로 정렬 후 리스트\n");
showList(list4);
printf("\n*80의 인덱스 찾기\n");
searchList(list4, 80);
printf("\n*55의 인덱스 찾기\n");
searchList(list4, 55);
printf("\n*999의 인덱스 찾기(없는 경우)\n");
searchList(list4, 999);
// 리스트의 메모리 확인하기
printf("[리스트의 메모리 데이터 확인하기]\n");
showListMemory(list4);
deleteList(list4);
// list5 리스트 생성과 초기화 함수
printf("\n[랜덤 로또 리스트 생성 및 초기화]\n");
Node *list5 = getList();
generateLottoList(list5);
bubbleSortNode(list5, getNodeLength(list5));
showList(list5);
deleteList(list5);
printf("\nLinked List closed");
return 0;
}
// 함수 영역
void appendFirst(Node *list, int newData){
struct Node *newNode = malloc(sizeof(Node));
newNode->next = list->next;
newNode->data = newData;
list->next = newNode;
}
void append(Node *list, int newData){
if(list->next == NULL){
Node *newNode = malloc(sizeof(Node));
newNode->data = newData;
newNode->next = NULL;
list->next = newNode;
}
else
{
Node *cur = list;
while(cur->next != NULL)
{
cur = cur->next;
}
Node *newNode = malloc(sizeof(Node));
newNode->data = newData;
newNode->next = NULL;
cur->next = newNode;
}
}
void showList(Node *list){
Node *cur = list->next;
printf("[ ");
while(cur != NULL)
{
printf("%d, ", cur->data);
cur = cur->next;
}
printf("]\n");
}
void deleteList(Node *list){
Node *cur = list;
Node *next;
while(cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
}
int getNodeLength(Node *list)
{
int count = -1; // except for list head
Node *cur = list;
while(cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
void insert(Node *list, int pos, int data)
{
// 현재 노드
Node *cur = list;
// 새로운 노드 초기화
Node *newNode = malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
// 위치가 0인 경우
if(pos == 0){
newNode->next = list->next;
list->next = newNode;
}
// 그밖에
else{
int count = 0;
while(count != pos){
if(count == (pos-1)){
newNode->next = cur->next;
cur->next = newNode;
}
cur = cur->next;
count++;
}
}
}
/* 두 노드의 데이터를 바꾼다. */
void swapNodeData(Node *node1, Node *node2)
{
int temp;
temp = node1->data;
node1->data = node2->data;
node2->data = temp;
}
/* 노드를 버블 소트로 정렬한다 */
void bubbleSortNode(Node *list, int size){
// head node
Node *cur;
cur = list;
// head 노드 사용안하니까 초기화한다.
cur->data = 0;
cur = cur->next;
for (int i = 0; i < size; i++)
{
if(cur->next == NULL) break;
for (int j = 0; j < size-1-i; j++)
{
// if 문 작성
if(cur->data > cur->next->data){
swapNodeData(cur, cur->next);
}
cur = cur->next;
}
cur = list->next;
}
}
void showListMemory(Node *list){
Node *cur = list;
int i;
int size = getNodeLength(list);
printf("\n=======================================\n");
printf("====== show list memory and data ======\n");
printf("=======================================\n\n");
for(i = 0; i <= size; i++){
printf("cur : %p | \n", cur);
printf("cur->next : %p | ", cur->next);
printf("cur->data : %d\n", cur->data);
cur = cur->next;
}
}
void arrayToList(Node *list, int array[], int size){
for (int i = 0; i < size; i++)
{
append(list, array[i]);
}
}
bool searchList(Node *list, int number){
Node *cur = list;
int count = 0;
while(cur != NULL)
{
if(cur->data == number){
printf("-> found at index : %d, cur->data : %d\n", count, cur->data);
return true;
}
cur = cur->next;
count++;
}
printf("-> nothing found searching for [%d]\n\n", number);
return false;
}
Node* getList(){
Node *newList = malloc(sizeof(Node));
newList->data = 0; // 초기화 0
newList->next = NULL; // 초기값 NULL
return newList;
}
void generateLottoList(Node *list){
int i, j;
int random[6];
srand(time(NULL));
for (i = 0; i < 6; i++)
{
random[i] = rand() % 45 + 1;
for(j=0; j<i; j++)
{
if (random[i] == random[j])
{
i--;
break;
}
}
}
int arrSize = sizeof(random)/sizeof(int);
arrayToList(list, random, arrSize);
}
