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. 데크
[배열]
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
          2. 프로그래밍 기법
      1.   프로그래밍 언어론
      2.   구조적 프로그래밍
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
        1.   선형자료구조(리스트 등)
              1. 리스트
              2. 연결 리스트
              3.
              4. 스택
              5. 데크
          1.   배열
        2.   비선형자료구조(트리,그래프)
        3.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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