연결 리스트: 도입

데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다.

일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다.

이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다.

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다.

하지만 꼭 그럴 필요가 있을까요? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있습니다.

이를 ‘연결 리스트’라고 합니다. 아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장합니다.

연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있습니다.

3은 다음 값이 없기 때문에 NULL (\0, 즉 0으로 채워진 값을 의미합니다)을 다음 값의 주소로 저장합니다.

연결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있습니다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

node 라는 이름의 구조체는 number 와 *next 두 개의 필드가 함께 정의되어 있습니다.

number는 각 node가 가지는 값, *next 는 다음 node를 가리키는 포인터가 됩니다.

여기서 typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함입니다.