3) 연결 리스트: 도입

연결 리스트란

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

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다. 연결 리스트는 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하여 값을 연이어서 읽어들일 수 있습니다.

자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장합니다.

구현 코드

typedef struct node

{

int number;

struct node *next;

}

node;

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

생각해보기

연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?

포인터를 넣을 공간 하나를 더 차지하지만, 배열과는 달리 연결 리스트는 메모리 어디에 있어도 상관 없다.

note

written by CaesiumY