[C언어] 연결리스트 구현하기

먼저 노드를 구현한다. C에서 구조체(struct)로 node를 정의할 수 있다. 배열처럼 인접한 셀들의 메모리 chunk가 아니라, 떨어진 메모리를 연결하는 것이기 때문에 자신의 값과 다음 노드의 주소를 가리키는 값(포인터)을 가지고 있어야 한다. 이 구조체를 node라고 한다면 다음 노드의 주소를 가리키는 next라는 포인터 변수는 node 타입을 값으로 갖고 있으므로 node *로 선언한다.

그러면 아래처럼 node라는 struct를 구성할 수 있을 것 같다. 하지만 여기서 하나 문제는, 맨 마지막 줄을 읽을 때까지 C는 여기에 node라는 struct가 있음을 알지 못하는데, 이미 그 전에 node *next 를 선언한다는 것이다.

typedef struct
{
  int number;
  node *next; // but, 이 줄에서 node라는 구조체는 아직 없다. 
} 
node;

이 것을 해결하려면 첫째줄에 node라고 정의해주면 된다. 이 부분은 그냥 문법적인 것인데, 맨 첫째줄에 정의하는 것은 해당 구조체의 정식 이름을 의미하고, 맨 밑줄에 정의하는 것은 구조체의 별명(alias) 이라고 한다. 이름과 별명이 꼭 일치할 필요는 없으며, 만약 다르게 정의한다면 구조체 괄호 안에는 타입명을 구조체 이름으로 적어줘야 한다.

// 첫째 줄에 node 추가
typedef struct node 
{
  int number;
  node *next;
}
node; 

이제 node 구조체를 정의했으니, 연결리스트의 시작점을 만들어보자.

node *list = NULL; // 이 node는 연결리스트의 첫 번째 노드를 가리킬 것이다. 

list라는 이름의 포인터변수를 정의하고, 이 변수는 연결리스트의 첫 번째 노드의 주소를 값으로 가질 것이다. 일단은 첫 번째 노드가 없으므로 NULL로 초기화 한다.

그러면 이제 연결리스트의 첫 번째 노드를 만들어보자. 노드를 만드는 순서는,

1. 먼저 malloc으로 node를 저장할 주소를 할당받는다.
2. malloc함수의 반환값이 NULL이 아니라면(=메모리를 정상적으로 할당받았다면) 그 노드에 number 값을 정한다.
3. 마지막으로 그 노드의 next는 아직 없으므로 NULL로 저장한다.

node *n = malloc(sizeof(node)); // 정수와 주소값을 합한 만큼의 크기인 node size만큼 할당 
if (n != NULL) // malloc을 사용할 때마다 반환값이 NULL이 아닌지 체크해줘야 한다. NULL이 아닌 것이 확인되기 전까지는 n을 건드리지 말아야 한다.
{
    (*n).number = 2; // n->number = 2; 와 같다. 
    n->next = NULL; 
}

여기서 (*n).number 는 n이 가리키는 주소로 가서, 그 구조체의 number에 접근한다는 의미이다. 이 문법이 다소 못생겼으므로 C에서는 이 코드를 n->number라고 표기하는 syntatic sugar를 사용한다.

이제 n이라는 포인터 변수는 number 값이 2이고 next가 NULL인 node를 가리키고 있다.

이것을 이제 list 변수와 연결하려면, list에 n이 갖고 있는 포인터 값을 넣어주면 된다. 그러면 list가 첫 번째 노드를 가리키게 된다.

list = n; 

이제 두 번째 노드를 만들었다고 하자.

n = malloc(sizeof(node)); // n 변수에 새로운 메모리 재할당
if (n != NULL)
{
  n->number = 3;
  n->next = NULL;
}

number가 3인 이 node를 number가 2인 node가 가리키게 하고 싶다면, 아래처럼 한다.

list->next = n;

그 다음에 또 만들어서 연결하려면?

list->next->next = n;

그런데 언제까지고 이렇게 하드코딩할 수는 없는 노릇이다. 그래서 이를 일반화하면 아래 코드로 나타낼 수 있다.

list가 가리키고 있는 첫 번째 노드의 주소를 tmp가 갖고 있도록 한다. 이제 tmp는 next가 NULL이 나올 때까지 계속 루프를 돌면서 재할당한다. 루프를 탈출한다는 건 tmp가 마지막 노드의 주소를 가리키고 있다는 뜻이다. 그러므로 tmp->next = n;을 해주면 된다.

node *tmp = list; 
while (tmp->next != NULL) 
{
  tmp = tmp->next;
}
tmp->next = n; 

중간에 노드 연결하기

여태까지는 마지막 노드에 이어서 다음 노드를 연결하는 것만 했는데, 만약 중간에 삽입하고 싶다면 어떻게 해야할까?

예를 들어 number값이 1, 3, 5 순서대로 연결되어있고, 여기에 number값이 2인 노드를 1과 3 사이에 삽입하고자 한다면 어떻게 해야할까?

일단 연결하기 위해서 2가지가 이뤄져야 한다.

1. 중간에 삽입하고자 하는 노드의 next가 number가 3인 노드를 가리키도록 해야한다.
2. number가 1인 노드의 next가 삽입하고자 하는 노드를 가리키도록 해야한다.

문제는 이 2가지 작업을 어떤 순서로 할 것이냐이다. 둘 다 이뤄져야 하는 작업이긴 한데, 만약 2번을 먼저 수행한다고 하면 기존에 1이 가리키고 있던 3, 5에 대한 연결고리가 사라진다. 즉 1이 그것을 기억하고 있었는데, 1이 2를 가리키게 되어버리면 더 이상 3, 5을 기억하고 있는 아이가 없어지므로 다시는 3, 5에 접근할 수 없어진다.

그러므로 반드시 1 -> 2 순서대로 수행되어야 한다. 삽입하고자 하는 노드가 3을 가리키도록 한다. 그러면 지금 3을 가리키고 있는 노드는 삽입 노드와 1이다. 그리고 이제 1이 삽입 노드를 가리키도록 하면 된다.

이 과정은 위에서처럼 while문이나 for문을 돌면서 number값을 대소비교해서 삽입할 장소를 찾고 작업을 진행하면 된다.

n = malloc(sizeof(node));
if (n != NULL)
{
  n->number = 2;
  n->next = NULL;
}

node *prevTmp = list; 
while (prevTmp->number < 1) // tmp->number가 1일 때 탈출하도록
{
  prevTmp = prevTmp->next;
} 
node *nextTmp = prevTmp->next // nextTmp는 3, 5 노드를 가리키게 된다
n->next = nextTmp; // 1번 작업 완료: n이 3, 5 노드를 가리키게 된다
prevTmp->next = n; // 2번 작업 완료: prevTmp의 next가 n을 가리키게 된다