Requires : C언어 기본 문법(Syntax), 포인터(Pointer), 구조체(Struct), 동적 할당(Dynamic allocation)
이 포스팅 내용은 C언어 기반으로 쓰여졌으며, C언어 기본 문법과 포인터, 구조체, 동적할당을 이해하고 있다는 가정 하에 설명합니다. 만약 위에서 언급한 개념들과 기본 문법이 익숙치 않으시다면, 그것들을 먼저 학습하시는 것을 권장드립니다.
우리는 프로그래밍 언어를 배우면서, 배열(Array)를 배워왔다.
배열은 쉽게 말해서, 같은 자료형을 가진 변수들의 묶음이다.
같은 자료형이고, 같은 용도로 쓸 것인데 각각의 변수로 모두 따로 선언하면 복잡하기 때문이다.
이러한 배열만 해도 당시에는 아주 혁명적인 아이디어였을 것이다.
하지만 우리는 점점 더 멋진 프로그램을 만들어 가면서, 배열의 정적인, 가변적이지 않은 사이즈를 불편해했다.
(배열은 크기를 한 번 선언하면 프로그램 실행 도중 바꿀 수 없기 때문이다.)
그때 나타난 구세주가 연결 리스트라는 것인데, 이 연결 리스트(영어로 Linked List)는 (포인터 기능과 동적 할당을 사용하여) 길이를 프로그램 실행 도중에 가변적으로 늘리거나 줄일 수 있다.
(사실 연결 리스트가 배열에 비해 좋은 것만 있는 것은 아니다. 배열은 연결 리스트보다 정의하고 사용하기 쉽고, 연결 리스트는 어떤 노드를 검색할 때 바로 찾아낼 수가 없다. 연결 리스트 전부를 탐색해야 할 수도 있기 때문에.
그럼에도 불구하고 알아놓으면 도움이 많이 될 개념이니, 아래에서 정확하게 알아보자.)
연결 리스트(Linked List, 링크드 리스트)는 노드를 연결시키는 자료구조이다.
(여기서 노드는 데이터를 갖고 있는 데이터의 묶음이다)
그럼 더 이해하기 쉽게 그림으로 보자.
바로 위 사진에서, 데이터(숫자)를 갖고 있는 하나의 박스가 노드이다.
하나의 노드에 데이터를 저장할 공간과 다른 노드를 가리키는 공간이 각각 있는 것을 알 수 있다.
이러한 노드들이 서로 이어져 있는 구조가 연결 리스트(링크드 리스트)이다.
가리키는 것? 바로 포인터이다.
아래 예제에서 우리는 next 필드(위 사진 참고)에 다른 노드의 주소를 저장해서, 포인터로 다른 노드를 가리킬 것이다.
(모든 노드의 구조는 구조체(struct)를 이용해 정의할 것이다.)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일
typedef struct NODE ND;
struct NODE { // 연결 리스트의 노드 구조체
struct NODE* next; // 다음 노드의 주소를 저장할 포인터
int data; // 데이터를 저장할 멤버
};
int main(void)
{
struct NODE* head = malloc(sizeof(struct NODE)); // 머리 노드 생성
//ND* head = malloc(sizeof(ND)) // 머리 노드는 데이터를 저장하지 않음
struct NODE* node1 = malloc(sizeof(struct NODE)); // 첫 번째 노드 생성
head->next = node1; // 머리 노드 다음은 첫 번째 노드
node1->data = 10; // 첫 번째 노드에 10 저장
struct NODE* node2 = malloc(sizeof(struct NODE)); // 두 번째 노드 생성
node1->next = node2; // 첫 번째 노드 다음은 두 번째 노드
node2->data = 20; // 두 번째 노드에 20 저장
node2->next = NULL; // 두 번째 노드 다음은 노드가 없음(NULL)
struct NODE* curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
printf("%d\n", curr->data); // 현재 노드의 데이터 출력
curr = curr->next; // 포인터에 다음 노드의 주소 저장
}
free(node2);
free(node1);
free(head);
return 0;
}
위에서 NODE(혹은 ND) 라는 구조체를 정의하고 사용할 수 있다.
NODE 구조체는 다음 노드의 주소를 저장할 포인터와, 데이터를 저장할 변수가 멤버 변수로 있다.
아래 main 함수로 가보면, NODE 구조체의 포인터를 만들고, malloc 함수로 메모리 공간을 받아와 그 공간의 주소를 대입하고 있다. (굳이 구조체 자체가 아니라 구조체 포인터를 사용하는 이유는, 동적으로 메모리를 할당받아서 그 주소를 저장하기 위함에 있다. 동적 할당을 사용하면 free() 함수로 중간에 메모리를 해제할 수도 있는 이점이 생기기 때문이다. 포인터로 사용하면 다른 노드의 주소를 저장할 때도 사용하기 쉽고, curr 등의 다른 포인터로 탐색할 때에도 사용하기 쉽다.)
위의 head->next = node1; 코드를 분석해보자.
head->next는 (*head).next로 바꿔쓸 수 있다. 즉, head가 구조체 '포인터'이기 때문에 -> 연산자를 써서 할당받은 진짜 구조체의 값에 접근하는 것이다.
그리고 next는 포인터 멤버변수이기 때문에, node1(주소값)을 바로 대입할 수 있는 것이다.
위 소스코드는 이러한 구조로 이루어져 있다.
head에서는 node1의 주소값을 next 필드에 넣고,
node1에서는 node2의 주소값을 next 필드에 넣는다.
node2의 next 필드 값은 NULL을 가리킨다.
(이 소스코드에서는 NULL값이 연결 리스트의 마지막을 의미한다.)
소스코드의 아래에 있는 while문은 연결 리스트의 모든 노드를 순회하는 것이다.
위에서 node2에 대입했던 NULL 값을 이용해 연결 리스트의 끝을 알 수 있다.
연결 리스트 순회용으로 사용할 포인터 curr을 만들고, 첫 번째 노드의 주소(head->next)를 저장한다.
여기서는 curr에 node1의 주소값이 처음 저장될 것이다.
(절대 연결 리스트 자체를 건드리면 안 된다!!)
그 다음 curr이 가리키는 구조체의 data(curr->data)를 출력하고, curr->next를 curr에 저장한다. (다음 노드로 이동하는 과정)
맨 마지막으로, 연결 리스트의 사용이 끝났다면(동적 메모리의 사용이 끝났다면) free() 함수를 사용해 메모리를 해제한다.
▶ 참고
위 연결 리스트 관련 그림과 소스코드를 보면 head 노드가 있는 것을 볼 수 있다.
(head와 함께 나중에는 tail 노드도 등장할 것이다. head는 리스트의 시작을, tail은 리스트의 끝을 의미한다.)
이 head와 tail 노드는, 다른 노드와 같이 데이터 data 필드와 다른 노드의 주소를 저장할 next 필드가 있지만, 구현의 용이함을 위해 데이터 필드를 사용하지 않을 것이다.
만약 head, tail 노드의 데이터 필드도 탐색한다면,
'추가, 삭제할 노드가 맨 앞인가?'
'추가, 삭제할 노드가 중간에 있나?'
'추가, 삭제할 노드가 마지막에 있나?'
이 3가지 사항을 모두 고려해야 한다.
하지만 head, tail 노드에 데이터를 넣지 않는다면 중간에 있는 경우만 고려하면 되기 때문에 구현하기 편하다.
head, tail처럼 아무 데이터가 없는 노드를 더미(dummy)노드라고 한다.
▶ 참고
연결 리스트에서 노드를 추가하는 규칙
1. 노드에 메모리 할당
2. next 멤버 변수에 다음 노드의 메모리 주소 저장
3. data 멤버 변수에 데이터(숫자, 문자 등) 저장
4. 마지막 노드라면 next 멤버 변수에 NULL 저장
