연결 리스트(Linked List)란 ?
어떤 데이터 덩어리(노드 : Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 방법이다.
단순 연결 리스트와 이중 연결 리스트, 순환 연결 리스트와 같은 종류가 있다.
그 중에서 나는 단순 연결 리스트를 C의 구조체를 배우고 직접 구현해보았다.
포인터의 표현이나 메모리 할당 등 앞서 배운 내용들이 한번에 나오니 어려웠지만 차근차근 복습해가며 단계별로 구현해보았다.
단순 연결리스트
출처 : https://devowen.com/210위 사진과 같이 'Data'와 '다음 Data를 가르키는 포인터'로 구현된 Node를 연속으로 구현하여 자료를 관리하는 방법을 단순 연결 리스트라고 부른다.
어떠한 프로그램을 만들때 정적 메모리 할당을 사용하면, 컴파일 시점에 메모리 크기를 결정하기 때문에 동적으로 메모리를 할당하는 방법보다 단점이 많다.
수치로 예를 들면 1000만큼을 쓰는 사용자도 있을 것이고, 100만큼만 필요한 사용자도 있다면 개발자가 무작정 1500쯤으로 메모리를 할당했다가는 갑자기 1600을 쓰는 사용자의 등장으로 공간이 부족해질수도 있고, 100만큼만 사용하는 사용자는 1400만큼을 낭비하는 격이 되기 때문이다.
그래서 주로 동적으로 메모리를 할당하지만, 동적으로 메모리를 할당하기 위해서는 사용자가 필요한 메모리 크기를 항상 알아둬야하는 ("숫자 몇 개를 더하시겠어요 ? : "와 같은) 단점이 있다.
이러한 단점을 보완하기 위해 사용자가 숫자를 입력할 때마다 숫자를 저장하는 동적 메모리를 하나씩 늘려가는 방법을 사용하면 좋을 것이다.
이때 사용될 수 있는 방법이 앞서 설명한 연결 리스트이다.
연결 리스트로 더하기 프로그램 만들기
구조체로 노드(Node) 선언하기
typedef struct node{
int number; //정수값을 저장할 변수
struct node *p_next; // 다음 노드를 가리킬 포인터 변수
}NODE;위와 같이 앞서 배운 구조체 문법을 이용해 Data 역할을 하는 int 변수, 다음 노드를 가르킬 포인터 변수인 p_next를 선언했다.
main 함수 설계하기
void main(){
NODE *p_head = NULL, *p_tail = NULL, *p;
int sum = 0, temp;
while(1){
printf("숫자를 입력하세요 (9999를 누르면 종료) : ");
scanf("%d", &temp);
if(9999==temp) break;
'NODE를 추가해주는 함수'(&p_head, &p_tail, temp);
}
...더하기 결과 출력
...free함수 등노드의 시작뿐만 아니라 p_tail(테일 포인터)를 하나 더 사용함으로써
마지막 노드를 빠르게 찾아 효율적으로 돌아가는 프로그램 설계
노드(Node)를 추가해 숫자를 대입해주는 함수 AddNumber 설계
void AddNumber(NODE **pp_head, NODE **pp_tail, int data){
if(NULL != *pp_head){
(*pp_tail)->p_next = (NODE *)malloc(sizeof(NODE));
*pp_tail = (*pp_tail)->p_next;
}else{
*pp_head = (NODE *)malloc(sizeof(NODE));
*pp_tail = *pp_head;
}
(*pp_tail)->number = data;
(*pp_tail)->p_next = NULL;
}
기존 연결 리스트에 노드가 없을 시 전달된 p_head와 p_tail 값을 수정해야 하므로
p_head와 p_tail의 주소값을 받기위해
포인터 변수의 주소값을 받을때 사용하는 2차원 포인터(**)를 사용하여 매개변수를 설정
2차원 포인터로 인해 이해가 어려울 수 있지만, 위의 설명을 참고하고
(*pp_tail)->number 표기법은 *(*pp_tail).number로 이해하면 큰 문제없이 이해할 수 있을 것이다.
연결 리스트에서 할당된 메모리를 순차적으로 해제해주는 코드
while(NULL != p_head){
p = p_head;
p_head = p_head -> p_next;
free(p);
}
p_tail = p_head; //반복문을 빠져나오면 p_head값은 NULL이므로 p_tail 값도 NULL로 변경다음 노드로 이동하며 free 함수를 실행할때 p에 주소를 저장하지 않고 p_head에 free 함수를 실행한다면 주소값을 잃어버려 메모리를 모두 해제할 수 없어 p에 주소값을 저장해놓고 다음 노드로 주소값을 변경해가며 진행한다.
프로그램 완성
#include <stdio.h>
#include <malloc.h>
//사용자에게 숫자를 입력 받아 합산에 출력하는 프로그램 만들기
typedef struct node{
int number; //정수값을 저장할 변수
struct node *p_next; // 다음 노드를 가리킬 포인터 변수
}NODE;
//연결 리스트의 노드를 구조체로 선언하기
void AddNumber(NODE **pp_head, NODE **pp_tail, int data){
if(NULL != *pp_head){
(*pp_tail)->p_next = (NODE *)malloc(sizeof(NODE));
*pp_tail = (*pp_tail)->p_next;
}else{
*pp_head = (NODE *)malloc(sizeof(NODE));
*pp_tail = *pp_head;
}
(*pp_tail)->number = data;
(*pp_tail)->p_next = NULL;
}
void main(){
NODE *p_head = NULL, *p_tail = NULL, *p;
int sum = 0, temp;
while(1){
printf("숫자를 입력하세요 (9999를 누르면 종료) : ");
scanf("%d", &temp);
if(9999==temp) break;
AddNumber(&p_head, &p_tail, temp);
}
p = p_head;
while(NULL != p){
if(p != p_head) printf("+");
printf("%d", p->number);
sum = sum + p->number;
p = p->p_next;
}
printf(" = %d\n", sum);
while(NULL != p_head){
p = p_head;
p_head = p_head -> p_next;
free(p);
}
p_tail = p_head; //반복문을 빠져나오면 p_head값은 NULL이므로 p_tail 값도 NULL로 변경
}쉽지 않은 부분이었고, 직접 코드도 쳐보고 이렇게 velog에 복습겸 정리까지 했음에도 어려운 부분임에는 틀림없다.
이 부분의 연습문제도 풀어보며 좀 더 머리와 손에 익히고, 나중에 자료구조를 본격적으로 공부하며 다시 만났을땐 쉽게 다뤄보겠다.
