[CS] TIL 19. 연결 리스트(1)
- 연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까?
- 연결 리스트를 구현하고 사용할 수 있을까?
boostcourse의 모두를 위한 컴퓨터 과학 (CS50 2019) 강의를 듣고 정리한 필기입니다. 😀
이번 주는 자료구조를 공부하게 될 텐데, 자료구조는 우리의 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 도와주는 것이다. 이번 주에 C에서 하려는 것은 구조체(struct), .(dot), * 기능을 만들 수 있어야 한다.
첫 번째, 구조체란 자신만의 구조를 만들 수 있는 키워드이다. 예를 들어서 TIL11에서 구조체를 만들었던 적이 있다. person이라는 구조체는 이름과 번호로 구성되어있고, 이것은 우리만의 데이터타입을 만들 수 있었다. 비트맵이나 바이트맵 헤더 등과 관련된 문제에서도 구조체를 사용한다. 이런 것들 또한 자료구조에 해당한다.
두 번째인 .(dot)은 속성값을 가져올 때 사용했다. (TIL11 참고) person이라는 구조체에서 이름이나 번호에 접근하기 위해서는 변수 이름과 .(dot)을 사용했다.
*연산자는 저번 주에 배운 내용과는 약간 다른 의미를 가질 수 있다. 하지만 마찬가지로 항상 메모리와 관련이 있다. 여하튼 이 연산자는 포인터를 이용해서 메모리 덩어리로 접근할 수 있는 역참조 연산자이다.
1. 연결 리스트: 개념
오늘내일 공부할 연결리스트는 값들의 리스트를 저장하는 방법이다. 배열도 값들의 리스트를 저장할 수 있지만, 배열은 고정된 메모리 덩어리이기 때문에 배열의 크기를 조절해서 더 많은 값을 넣고 싶으면, 그만큼의 메모리를 할당해야 한다는 번거로움이 있다. 당장 어제 공부했던 것만 떠올려도 값들을 모조리 다 복사한 다음 free를 해주고, 물론 realloc를 이용하던 더 간단해질 수 있다. 하지만 realloc 간단해 보일 뿐, 완전히 같은 일을 한다. 그 때문에 배열을 늘릴 때의 과정은 O(n)이었다. 느린 과정이다. 하지만 배열은 쉽게 인덱싱을 할 수 있다는 장점이 있다. 대괄호를 통해 문법적으로 쉽게 접근할 수 있고, 하지만 이것 또한 몇 번째 인덱스에 무슨 값이 있는지를 기억해야 할 것이다. 여하튼 때문에 배열은 또 빠르다고 할 수도 있다. 그리고 배열은 바이너리 검색 같은 곳에도 적용할 수 있다. 하지만 꼭 배열처럼 연이어 저장할 필요가 있을까.
연결리스트란, 각 값이 메모리상의 여러 군데 나누어져 있다고 하더라도 바로 다음 값의 메모리 주소를 기억하고 있어 여전히 값을 연이어서 읽어드릴 수 있다는 데이터 구조이다.
수많은 EMMA가 저장되어있는 메모리에 1, 2, 3을 저장한다고 하자. 위는 임의의 위치에 1을 저장한 것이다.
여기서 2를 추가하면 위 그림과 같은 형태가 될 것이다. 다른 칸들은 데이터가 이미 저장되어있기 때문에 컴퓨터가 사용할 수 있는 메모리에 2를 저장한 것이다.
마지막으로 세 번째 값을 저장하면 사용할 수 있는 가장 가까운 위치에 3을 저장하게 된다. 물론 이것은 1, 2, 3이 인접해 있지 않기 때문에 정의상의 배열은 아니며, 대괄호로 접근할 수도 없다. 위와 같은 사진을 크기가 3인 연결리스트라고 한다.
크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에 자신의 값과 바로 다음 값의 주소(포인터)를 저장한다.
이 리스트에는 3 이외에 더 남은 것이 없다는 것을 나타내기 위해 3을 저장한 메모리 주소에는 3과 null을 저장한다. 문자 \0과는 엄밀히 다른 것이다. null은 16진법의 0(0x0)이며, 포인터이다. 하지만 둘 다 그 값을 보면 0이다. 이제 리스트의 끝을 알리는 값을 다음 값의 주소로 저장했다. 만약, 리스트가 추가된다면 3이 저장된 리스트에는 3과 그 다음 값을 알리는 주소가 저장될 것이다.
이제 관례로 자신의 값은 NUMBER라고 할 것이고, 바로 다음 값의 주소(포인터)는 next라고 할 것이다. 그리고 이러한 덩어리를 NODE라고 부를 것이다. 컴퓨터 공학에서 node라는 단어는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미한다. 이것을 이제 코드로 알아보자.
typedef struct
{
string name;
string number;
}
person;
TIL11에서 typedef와 구조체에 대해서 배울 때, 위와 같은 코드를 사용했다. 연결리스트를 코드로 나타내면 위의 코드와 매우 비슷하다.
typedef struct node
{
int number;
struct node *next;
}
node;
node 라는 이름의 구조체는 number 와 *next 두 개의 필드가 함께 정의되어 있다. number는 각 node가 가지는 값, *next 는 다음 node를 가리키는 포인터가 된다. 또한, *next는 다음 number 그 자체가 아니라, node라는 구조로 되어있는 것을 가리키기 때문에 struct node를 자료형으로 갖는다. 여기서 typedef struct 대신에 typedef struct node 라고 node를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함이다.
2. 연결 리스트: 코드
앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현할 것이다.
node *list = NULL;
첫 연결 리스트는 비어있을 것이다. 그리고 코드에는 비어있는 무언가를 나타내는 최소한 무언가가 필요하다. 위 그림처럼 빈 박스가 있고 이것을 node를 가리키는 포인터라고 생각해보자. 그리고 이것을 코드로 나타내면 그림 아래에 있는 코드와 같다. 노드는 비어있기 때문에 적어도 리스트가 없다는 것을 알려주는 변수가 있어야 한다.
그리고 값이 없을 때를 표현하는 가장 간단한 방법은 0을 저장해서 NULL이라는 새로운 별명을 가지도록 하는 것이다.
node *n = malloc(sizeof(node));
(*n).number = 2;
이제 이 리스트에 숫자를 넣어보자. 2를 추가할 것인데, 2뿐만 아니라 숫자2와 포인터를 넣을 공간을 할당해야 한다. (이 둘을 합쳐서 node라고 부른다.) 이것을 코드로 치면 위 그림 아래에 있는 것과 같다. node의 크기만큼 메모리를 할당해야하는데 우리는 node의 크기를 알 수 없다. 수학 계산을 통해서 정수와 포인터를 더할 수도 있지만 node자체를 sizeof 함수의 매개변수로 둔다면 해결될 것이다. 이제 이 코드는 ndoe의 크기만큼의 메모리를 할당해준다. 그리고 이것을 임시로 변수 n에 저장한다. (여기서 n은 node를 의미한다.) malloc은 주소를 반환해주고, 이를 n이라는 변수에 넣는다.
그리고 (*n).number = 2;를 해줌으로써 n이라는 node의 number를 2로 설정한다. *n은 * 연산자 때문에 가리키는 곳을 가라 라는 뜻이 된다. ()는 연산의 순서를 위해서 넣어줬다. 그럼 컴파일러는 이를 인식해서 괄호를 먼저 처리하게 된다. 어찌 되었건 이 코드는 number 필드에 접근하는 것이다.
n->number = 2;
C는 (*n).number = 2;를 더 간단하게 표현할 수 있는 문법이 있다. 이는 하이픈(-)과 부등호(>)를 사용한 화살표 기호를 활용하는 것으로 위 코드처럼 활용된다. (*n).number = 2;와 완전히 같지만, 이 코드는 치기 귀찮고, 보기에 좋지 않기 때문에 화살표를 사용한다.
node *n = malloc(sizeof(node));
n->number = 2;
n->next = NULL;
이제 node에 넣어야 할 것은 이 node의 다음 주소이다. 하지만 아직 다음 node가 없기 때문에 null을 쓴다. 그리고 이것 또한 n 변수의 next 필드에 저장하는 것이기 때문에 화살표 기호를 사용한다.
node *n = malloc(sizeof(node));
if (n! = NULL)
{
n->number = 2;
n->next = NULL;
}
이제 코드 위의 그림과 비슷해 졌지만, malloc을 사용할 때마다 반환되는 값을 확인해야 한다. n이 NULL인지 아닌지를 검사하고 나서 나머지 부분을 실행해야 한다는 것이다. 만약 n이 NULL이면 프로그램을 끝내거나 return을 해도 된다. 어쨌거나 n가 NULL이 아니라는 것이 확인되기 전까지는 n의 내용을 수정하거나 화살표 기호를 사용해서는 안 된다.
하지만 이것이 연결리스트라는 것은 아니다. 위 그림을 다시 보더라도 둘은 연결되어있지 않기 때문이다. 어떤 포인터에서 어떤 포인터로 향하도록 하는 것이 필요하다는 것이다.
list = n;
궁극적으로는 위 그림처럼 빨간 화살표가 필요한 것이고, 그림 아래는 이것을 코드로 구현한 것이다.
원래 NULL로 초기화된 list라는 변수에 새로운 노드를 가지고 있는 임시 변수 n을 할당한다. 이제 list는 NULL이 아니게 되었으며, n에 할당한 메모리 주소와 같은 값을 가지게 된다.
node *n = malloc(sizeof(node));
if (n != NULL)
{
n->number = 3;
n->next = NULL;
}
몇 가지를 더 진행해보자. 또 다른 list에 3을 추가 하고 싶다고 하자. 3 자체는 node 안에 들어가 있고, 그렇기 때문에 위 그림에 대한 코드는 그 아래와 같을 것이다. 하지만 그러면 3이 들어 있는 node는 어디에도 속하지 않은 node 되기 때문에 이렇게 노드를 만들기만 해서는 안 된다.
3이 들어 있는 node를 가리키는 화살표를 하나 추가해야 한다. 연결 리스는next가 NULL인 것이 끝이다. 이는 next를 하나하나 확인하면서 null을 찾기 전까지는 끝을 모른다는 말과도 같다. 끝을 모른다고 해서 만약 list가 3이 들어 있는 node를 가리키게 설정해버리면 2가 들어 있는 node가 버려지게 되니 주의하자.
node *tmp = list;
while (tmp->next != NULL);
{
tmp = tmp -> next;
}
tmp->next = n;
이것을 하기 위해서는 임시 변수가 필요하다. tmp는 list가 가리키고 있는 것을 확인하고, list가 가리킨 구조체의 next가 NULL인지 체크한다. NULL이 맞는다면 우리가 추가한 node를 가리키게 수정한다. 만약 next가 NULL 아니라 다음 구조체를 가리키고 있다면, 또 그 구조체로 가서 next를 확인할 것이다.
tmp는 연산자 *를 이용해서 list와 같은 곳을 가리키게 해준다. 그리고 next가 NULL인지 아닌지를 확인하는 코를 while을 이용해 작성할 수 있다. 만약 next가 NULL이 아니라면, tmp는 tmp의 next와 같은 주소를 가리키게 된다. 이것은 next가 NULL인 것을 확인할 때까지 반복될 것이다. 그리고 만약 next가 NULL이 맞는다면 tmp의 next는 3을 저장하고 있는 n을 가리키게 된다.
이것은 리스트가 얼마나 크든 계속해서 임시 포인터를 움직여 next가 NULL인 마지막 node을 찾게 하는 것이다.
숫자 1이 들어가 있는 노드가 새로 생겼다. 이 연결리스트에 1을 넣으면서 동시에 정렬되도록 하기 위해서는 어떤 점을 고려하면 될까?
ndoe *n = malloc(sizeof(node));
if (n != NULL)
{
n->number = 1;
n->next = NULL;
}
list = n;
위는 숫자 1이 들어가 있는 node 만들고, list가 1이 들어간 node를 가리키게 하는 코드를 작성했다. 코드 자체에는 문제가 없지만, 그림을 보면 무언가 잘못되었다는 것을 알 수 있다. 2를 가리키는 것이 없기 때문에 2뿐만이라 2가 가리키는 3, 3이 가리키는 4가 들어가 있는 node는 버려지게 된 것이다. 이 값을 모두 잃어버린 것이며, 이것이 메모리 누수를 발생시킨다. Valgrind를 사용할 때, 메모리가 누수되어서 경고가 발생한다면, 그것은 아마 메모리를 해제(free)하는 것을 잊었기 때문일 것이다. 어쩌면 우리가 사용하던 메모리를 완전히 잃어버린 것이 될 수도 있다. 위 코드에 따르면 2, 3, 4를 가리키는 node는 다시는 접근할 수 없게 되었다. 즉, 이 값이 어디에 있는지 기억하고 있는 변수가 없기 때문에 컴퓨터 요청할 수는 있지만, 다시 되돌려 받을 수 없다.
n->next = list;
이것을 해결하기 위해서는 1이 2를 먼저 가리키도록 해, 2를 가리키는 화살표가 중복되도록 하는 것이다. 코드를 보면 list 가 가리키고 있는 곳을 n의 next 필드에 할당했다. (list 자체가 2를 가진 node를 가리키고 있는 포인터이기 때문에 가능) 하지만 이렇게만 하면 리스트의 시작점이 어딘지를 모르게 된다.
list = n;
이제 list를 1을 가진 node를 가리키게 하면 된다.
아래는 위 코드를 한번에 볼 수 있는 것이다.
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의한다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정한다.
int number;
//다음 node의 주소를 가리키는 포인터를 *next로 지정한다.
struct node *next;
}
node;
int main(void)
{
// list라는 이름의 node 포인터를 정의한다. 연결 리스트의 가장 첫 번째 node를 가리킬 것이다.
// 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화한다.
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킨다.
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미이다.
// 즉, n이 가리키는 node의 number 필드를 의미하는 것이다.
// 간단하게 화살표 표시 ‘->’로 쓸 수 있다. n의 number의 값을 1로 저장한다.
n->number = 1;
// n 다음에 정의된 node가 없으므로 NULL로 초기화한다.
n->next = NULL;
// 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 준다.
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당한다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number와 next의 값을 각각 저장한다.
n->number = 2;
n->next = NULL;
// list가 가리키는 것은 첫 번째 node이다.
//이 node의 다음 node를 n 포인터로 지정한다.
list->next = n;
// 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장한다.
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있다.
// 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의
// 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정한다.
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력한다.
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 된다.
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해준다.
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}
