자료 구조 | 연결 리스트(1) 도입

이제껏 여러 자료형의 데이터를 메모리 상에 저장하고 삭제하는 방법을 배웠다. 이번 강의부터는 메모리를 좀 더 효율적으로 관리하고 사용하는 법을 배운다. 데이터 구조의 개념과 연결 리스트에 대해 알아보자.

 

학습 목표

연결 리스트의 정의를 설명할 수 있다. 

 

데이터 구조와 연결 리스트

데이터 구조는 메모리를 좀 더 효율적으로 관리하기 위해 새로 정의하는 구조체다. 연결 리스트(linked list)는 데이터 구조 중 하나이다.

 

• 배열에서는 각 인덱스의 값이 메모리 상에 연이어 저장되었다.
• 하지만 메모리 상의 어디에 있든 주소만 알고 있다면 연이어 값을 읽을 수 있다.
• 이러한 개념을 사용한 것이 연결 리스트이다.
• 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 다음 값의 주소(포인터)를 저장한다.

 

사진 출처 cs50

 

연결 리스트를 그림으로 이해해보자. 위 사진은 각 인덱스가 연결되어 있지 않지만, 인덱스가 자신의 값과 다음 값의 주소를 함께 저장하고 있다. 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를 사용할 수 있다.

 

생각해보기

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

연결 리스트는 메모리 상에 데이터가 연이어 저장되어 있지 않아도 돼 좀 더 효율적이다. 메모리의 크기를 조절할 때도 realloc과 같은 함수를 사용할 필요가 없다.

 

데이터를 검색할 때 시작점부터 읽어가야 한다. 때문에 배열처럼 인덱스를 이용해 원하는 데이터에 바로 접근할 수 없다는 단점이 있다.

 

---

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)