Page 337 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

09-1 선형 리스트

리스트는 데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조입니다. 여기서는 가장 간단한
리스트 구조를 가지고 있는 선형 리스트에 대해 살펴보겠습니다.

선형 리스트란?
이번에 살펴볼 내용은 선형 리스트입니다. 우선 리스트가 어떤 것인지 간단한 그림을 통해 알

아보겠습니다. 그림 9-1에 리스트 구조를 간단히 나타냈습니다. 이와 같이 리스트는 데이터
를 순서대로 나열해 놓은 자료구조를 말합니다. 04장에서 공부한 스택과 큐도 리스트 구조
로 되어 있습니다.

리스트는 순서가 있는 데이터를 나열한 구조로 되어 있습니다.
…
처음 끝
[그림 9-1] 리스트

가장 단순한 구조를 가진 리스트를 선형 리스트(linear list) 또는 연결 리스트(linked list)라고

합니다. 그림 9-2는 연결 리스트의 한 예입니다. 그림을 보면 A부터 F까지 데이터가 순서대
로 나열되어 있고 각각의 데이터가 화살표로 연결되어 있음을 알 수 있습니다. 이때 각 데이
터의 연결 관계를 ‘이야기 전달하기 게임’에 비유할 수 있습니다. A가 B에게 이야기를 전달하

고 B가 C에게 이야기를 전달하는 방식으로 F에게 이야기를 전달합니다. 즉, 한 사람을 건너
뛰어 이야기를 전달할 수 없습니다.

데이터를 사슬 모양으로 연결한 형태로 되어 있습니다.
머리 노드 꼬리 노드
Ａ Ｂ Ｃ Ｄ Ｅ Ｆ

다음 노드를 가리키는 포인터를 의미합니다.

[그림 9-2] 연결 리스트

이때 리스트의 데이터는 노드(node) 또는 요소(element)라고 합니다. 각각의 노드는 데이터와
다음 노드를 가리키는 포인터를 가지고 있습니다. 처음과 끝에 있는 노드는 특별히 각각 머리

09•리스트 337