Linear List   선형 리스트

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 인덱스