자료의 특징(추상 자료형)과 주로 사용할 연산(알고리즘)에 따라 최적의 형태로 자료를 구조화해야 하는데, 자료를 구조화하는 가장 기본적인 방법은 나열하는 것이다.[표 3-2]와 같이 동창 이름, 좋아하는 음식, 오늘의 할 일 등을 하나씩 나열할 수 있는데, 이렇게 나열한 목록을 리스트라고한다.

이때 원소들을 순서대로 나열한 리스트를 선형 리스트 또는 순서 리스트 라고 한다.

리스트를 표현하는 형식은 [그림 3-1]의 (a)와 같다. 원소가 순서대로 나열된 선형 리스트는 1에 나열된 순서가 원소들의 순서가 된다. [표 3-3]에 있는 동창 이름 선형 리스트를 리스트의 일반화 표현 형식으로 나타내면 (b)와 같다.

원소가 하나도 없는 리스트는 공백 리스트라고 하고, [ 그림 3-2]와 같이 빈 괄호로 표현한다.

선형 리스트는 메모리에 저장되는 구현 방식에 따라 순차 방식으로 구현하는 선형 순차 리스트와 연결 방식으로 구하는 선형 연결 리스트로 나뉜다. 일반적으로 선형 순차 리스트를 선형 리스트라고 하고, 선형 연결 리스트를 연결 리스트라고 한다. 3장에서는 순차 자료구조 방식으로 구현하는 선형 리스트를 살펴본다.

선형 리스트( 선형 순차 리스트 ) 는 원소들이 나열된 논리적인 순서와 메모리에 저장되는 물리적인 순서가 일치하는 순차 자료구조 방식으로 구현한다. 순차 자료구조는 원소를 논리적인 순서대로 메모리에 연속하여 저장한다. 표 [ 3-3 ] 에 있는 동창 이름 선형 리스트가 메모리에 저장되는 순서는 그림 [ 3-3 ]과 같아 논리 순서와 일치한다.

순차 자료구조는 원소들이 순서대로 연속하여 저장되기 때문에 시작 위치와 원소 크기를 알면 특정소의 위치를 쉽게 알 수 있다. 시작 위치가 a 이고, 원소 크기가 l인 선형 리스트에서 두 번째 원소의 위치는 [ 그림 3-4 ]와 같이 a + l 이고, 세 번째 원소의 위치는 a + 2l이다. 따라서 i번째 원소의 위치는 a + (i - 1) x l이 된다.