List   리스트

(2019-06-07)

Linear List, 선형 리스트, Ordered List, 순서 리스트

1. 리스트 (List)

  ㅇ 자료의 목록
     - 내부적으로 순서가 있는 일련의 데이터 집합
        . 例)  리스트 = (원소1,원소2,...,원소n), Empty List = ()  ☞ 수열 참조


2. 리스트의 특징

  ㅇ 리스트 내 항목들은 순서 또는 위치를 갖음
     - 비교적 저장 데이터가 적을 때에, 
     - 순서를 갖으나, 굳이 저장 순서가 중요하지 않을 때에 유용
  ㅇ 사용과 구현이 비교적 단순
     - 작은 규모에서 자료의 삽입,삭제,찾기가 비교적 용이한 편
  ㅇ 검색은 다소 불편
     - 리스트 내 어떤 요소를 찾는데는, 중간 노드들을 차례대로 따라가야 함
  ㅇ 크기 변경이 쉬움
     - 배열 보다는 크기를 유연하게 바꿀 수 있음
  ㅇ 다양한 응용
     - 스택,,집합,더 복잡한 자료구조를 구현하는데 자주 사용됨
  ㅇ 리스트의 구현 (C 언어 例)
     - (고정 크기) => 배열에 의해 선형 리스트를 구현
     - (가변 크기) => 포인터를 이용한 연결 리스트로써 구현


3. 리스트에 필요한 주요 연산 종류

  ㅇ 일반 연산
     - 특정 크기의 리스트 생성 (즉, 생성된 리스트를 반환)
        . 例) list create(size)
     - 리스트 크기 (즉, 원소 수를 반환)
        . 例) integer size()
     - 빈 리스트 여부
        . 例) boolean isEmpty()
     - 소속 원소 전체를 반환
        . 例) iterator elements()                                    ☞ 이터레이터 참조

  ㅇ 접근 및 갱신 연산
     - 원소 접근/탐색
        . 例) element get(index)
     - 원소 대체
        . 例) element set(index,element) 또는 element replace(index,element)
     - 원소 삭제 (맨 뒤,맨 앞,특정 원소)
        . 例) element removeFirst(), element removeLast(), element remove(index)
     - 원소 삽입 (맨 뒤,맨 앞,특정 원소 앞)
        . 例) boolean addFirst(elemet), boolean addLast(elemet), boolean add(index,element)


4. 선형 리스트(Linear List), 순서 리스트(Ordered List)

  ㅇ 연속되는 장소에 저장되는 자료구조 
     - 데이터를 자연스럽게 나열한 구조

  ㅇ 선형 리스트 특징
     - 원소들 간에 순서가 유지되며 위치함 
        . 표현이 간단하고 원소 위치를 찾기가 비교적 쉬움
     - 논리적 및 물리적 순서가 같음
        . 일반적 例) 사전 (단어를 순서있게 나열한 리스트), 주소록 등
        . 컴퓨터 구현 例) 배열 등
     - 다양한 데이터형으로 구현 가능
        . 주로, 배열 이용 구현
           .. 배열로 구현하면, 인덱스를 이용하여 즉시 원하는 원소를 취할 수 있음
        . 또한, 연결 리스트로도 구현이 가능
     - 선형 리스트 내 삽입,삭제 연산 시에는 비효율적
        . 연속적으로 원소들의 추가적인 이동이 필요 함
     - 또한, 저장공간 사용이 비효율적임
        . 실행 전에 미리 크기를 결정해야 하는, 정적 메모리 할당 방식 ☞ 동적 메모리 할당 참조


5. 연결 리스트 (Linked List)

  ※ ☞ 연결 리스트 참조
     - 연결 리스트선형리스트(배열 등)의 단점을 보완한 자료구조로써,
     - 저장 데이터 및 포인터에 의해 연결된 비 연속적(비 순차적) 자료구조
6. Sorted List, Array List

  ㅇ Sorted List : 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조
     - 例) DBMS 인덱스Array List  : 저장되는 순서 그대로 유지하는 자료구조
     - 例) 단순 데이터 파일


[선형자료구조(리스트 등)] 1. 리스트 2. 연결 리스트 3. 4. 스택 5. 데크
[배열]

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