1. 선형 리스트 (Linear List)
ㅇ 고정 크기의 데이터들을 자연스럽게 나열한 구조
- 연속되는 장소에 연속적(순차적)으로 저장되는 자료구조 임
- 주로, 배열 이용 구현
2. 선형 리스트의 특징
ㅇ 논리적 및 물리적 순서가 같음
- 저장되는 순서가 논리적인 순서와 같음
ㅇ 대부분, 원소들 간에 순서가 유지되며 위치함
- 원소 위치를 찾기가 비교적 쉬움
. 例) 사전 (단어를 순서있게 나열한 리스트), 전화번호부, 주소록 등
- (다른 명칭) (Dense List : 연접 리스트) 또는, (Sorted List,Ordered List : 순서 리스트)
ㅇ 선형 리스트 내 삽입,삭제 연산 시에는 비효율적
- 원소들의 추가적인 이동이 필요 함
. 더욱이, 순서 유지할 경우 정렬 작업까지 추가적으로 필요
ㅇ 고정 크기 이므로, 저장공간 사용이 비효율적임
- 실행 전에 미리 크기를 결정해야 하는, 정적 메모리 할당 방식 ☞ 동적 메모리 할당 참조
ㅇ 선형 리스트 구현 例) 전화번호부
- typedef struct { char *name; char *phone; } Person;
3. 선형 리스트의 구분 : (정렬 여부)
ㅇ Array List (배열 리스트)
- 저장되는 순서 그대로 유지하는 자료구조
. 例) 단순 데이터 파일
ㅇ Sorted List (Ordered List, 순서 리스트)
- 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조
. 例) DBMS 인덱스