Linear List   선형 리스트

(2020-10-13)

Sorted List, Ordered 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 인덱스


[리스트] 1. 리스트 2. 리스트 연산 3. 선형 리스트 4. 연결 리스트

 
        최근수정     요약목록     참고문헌