[CS50] 6.3 연결 리스트: 도입

연결 리스트는 데이터 구조 중에 하나로,

고정되어있는 배열과 달리 중간중간 비어있는 메모리에 값을 저장하고

바로 옆에 그 다음 값의 메모리 주소(포인터)를 함께 가진다.

메모리를 효율적으로 사용할 수 있지만 메모리를 두 배로 가지게 된다.

배열처럼 연속적으로 저장되진 않지만 다음 값의 메모리 주소만 알면 값을 읽어들일 수 있다.

 

 

1이 저장되고 바로 옆에 2를 가리키는 주소를 함께 가진다.

2는 3의 주소를 함께 가진다.

3 다음은 없기 때문에 널 포인터를 가진다.

 

 

 

 

 

연결 리스트는 아래와 같은 구조체로 정의할 수 있다.

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

node라는 이름의 구조체는 number 와 *next  두 개의 필드를 정의한다.

number는 각 node가 가지는 값,

*next 는 다음 node를 가리키는 포인터를 의미한다.

 

여기서 typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은,

구조체 안에서 node를 사용하기 위해서다.

 

 

 

 

 

 

 

 

 

 

출처: www.boostcourse.org/cs112