List   리스트

(2020-05-20)

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

1. 리스트 (List)

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


2. 리스트의 특징

  ㅇ 리스트 내 항목들은 순서 또는 위치를 갖음
     - 비록, 순서를 갖으나,
     - 굳이, 저장 순서가 중요하지 않을 때에 유용
     - 한편, 배열은 연속된 메모리 위치에 저장
  ㅇ 데이터의 중복 허용 함
     - 데이터 중복을 허용 않는 것은, ☞ 집합 참조
  ㅇ 사용과 구현이 단순
     - 비교적 저장 데이터가 적을 때에 유용
     - 작은 규모에서 자료의 삽입,삭제,찾기가 용이한 편
  ㅇ 다양한 데이터형으로 구현 가능하나, 주로, 배열 이용 구현
     - 배열로 구현하면, 인덱스를 이용하여 즉시 원하는 원소를 취할 수 있음
  ㅇ 검색은 다소 불편
     - 리스트 내 어떤 요소를 찾는데는, 중간 노드들을 차례대로 따라가야 함
  ㅇ 정렬은 비효율적
     - 정렬이 필요한 응용에는 잘 사용하지 않는 자료구조 임
  ㅇ 매우 유연한 구조 
     - 내용 변경, 크기 변경(늘임,줄임)이 쉬움
     - 특히, 고정적인 배열 구조 보다는 훨씬 유연함
  ㅇ 중간 삽입,삭제에 유리
     - 배열에 비해, 중간 삽입,삭제에 효율적
  ㅇ 다양한 응용
     - 스택,,집합,더 복잡한 자료구조를 구현하는데, 리스트를 기반으로 구현하곤 함


3. 리스트의 구분 

  ㅇ (고정 크기) => 선형 리스트
     - 적용 : 데이터 갯수가 제한된(고정된) 크기의 데이터를 자연스럽게 나열한 구조에 적합
     - 구현 : 주로, 고정 크기의 배열에 의해 선형 리스트를 구현

  ㅇ (가변 크기) => 연결 리스트 (단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트)
     - 적용 : 동적으로 크기가 변할 수 있고, 삭제,삽입 등에 데이터 이동의 필요가 없는 용도에 적합
     - 구현 : 주로, 포인터를 이용한 가변 크기의 연결 리스트로써 구현

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


4. 선형 리스트(Linear List), 순서 리스트(Ordered List)데이터를 자연스럽게 나열한 구조
     - 연속되는 장소에 저장되는 연속적(순차적) 자료구조 임
     - 주로, 배열 이용 구현

  ㅇ 선형 리스트 특징
     - 원소들 간에 순서가 유지되며 위치함 
        . 표현이 간단하고 원소 위치를 찾기가 비교적 쉬움
     - 논리적 및 물리적 순서가 같음
        . 例) 사전 (단어를 순서있게 나열한 리스트), 전화번호부, 주소록 등
     - 선형 리스트 내 삽입,삭제 연산 시에는 비효율적
        . 원소들의 추가적인 이동이 필요 함
     - 고정 크기 이므로, 저장공간 사용이 비효율적임
        . 실행 전에 미리 크기를 결정해야 하는, 정적 메모리 할당 방식 ☞ 동적 메모리 할당 참조

  ㅇ 선형 리스트 구현 例)  전화번호부
     - typedef struct { char *name; char *phone; } Person;


5. 연결 리스트 (Linked List)

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

  ※ ☞ 리스트 연산 참조
     - 빈 리스트의 생성, 노드의 추가,삭제 등


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

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