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

(2016-12-12)

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. Sorted List, Array List

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


[선형자료구조(리스트 등)] 1. 리스트 2. 배열 3. 스택 4. 5. 선입선처리 6. 선입후출처리 7. 데크

 
        최근수정     모바일웹     참고문헌