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

(2017-12-01)

Linked List, 연결 리스트, 링크드 리스트

1. 리스트 (List)

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


2. 리스트의 특징

  ㅇ 비교적 저장 데이터가 적고, 굳이 저장 순서가 중요하지 않을 때에 유용
     - 작은 규모에서 자료의 삽입,삭제,찾기가 비교적 용이한 편
  ㅇ 리스트 내의 어떤 요소를 찾는데는, 
     - 중간 노드들을 차례대로 따라가야 함
  ㅇ 배열 보다는 크기를 유연하게 바꿀 수 있음


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

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

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


4. 연결 리스트 (Linked List)

  ㅇ 저장 데이터 및 포인터에 의해 연결된 비연속적(비순차적) 자료구조

  ㅇ 연결 리스트 특징
     - 연결 리스트는 선형리스트(배열 등)의 단점을 보완한 자료구조임
        . 원소들이 기억 장소 내 어느 곳에서나 위치 가능
        . 노드의 삽입과 삭제가 용이하며, 기억공간이 절약됨
           .. 한편, 배열은 새로운 요소의 추가,기존 요소의 삭제에 비교적 많은 시간이 소요
        . 링크를 이용하여 원소의 순서를 유지시켜 줌

  ㅇ 노느 저장 단위
     - { 노드 : (데이터값,링크) } 가 하나의 단위로써 저장됨
       
        . 여기서, 포인터 변수는, 
           .. 연결 리스트의 첫번째 원소를 가리키지만, 연결 리스트 전체를 가리키기도 함
           .. 연결 리스트 전체를 가리키는 경우에, 관례적으로 대문자로 시작하는 변수명을 씀

  ㅇ 연결 리스트의 처음과 끝
     - 리스트의 처음 노드 : 헤드(Head)
     - 리스트의 끝 노드 : 테일(Tail)

  ㅇ 연결 리스트 구분
     - 단순 연결 리스트 (Singly Linked Linear List)
        . 각 원소에 단방향 단일 링크 필드 필요
     - 원형 연결 리스트 (Circularly Linked Linear List) 
        . 마지막 노드링크가 리스트의 처음 노드를 가리킴
     - 이중 연결 리스트 (Doubly Linked Linear List)
        . 후행 노드 및 선행 노드 모두를 가리키는 포인터를 갖음으로 양방향 가능


5. 리스트 연산 종류노드 생성/소멸
  ㅇ 노드 추가
  ㅇ 노드 탐색
  ㅇ 노드 삭제
  ㅇ 노드 삽입 등


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. 프로그램,프로그래밍
      1.   프로그래밍 언어론
      2.   객체지향
      3.   자료구조
            1. 자료구조
        1.   선형자료구조(리스트 등)
          1.   1. 리스트
              2. 배열
              3. 스택
              4.
              5. 데크
        2.   비선형자료구조(트리,그래프)
        3.   자료구조 기타일반
      4.   알고리즘
      5.   자료표현(알파벳/코드)
      6.   시스템 소프트웨어
      7.   프로그래밍언어 종류
      8.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록(시험중)     참고문헌