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

(2020-05-20)
1. 연결 리스트 (Linked List)

  ㅇ 고정 크기의 배열 등에 의해 구현된 선형 리스트의 단점을 보완한 자료구조 임
     - 즉, 연결 리스트는, 동적으로 크기가 변할 수 있고, 삭제,삽입 등에 데이터 이동의 필요가 없음


2. 연결 리스트의 특징

  ㅇ 저장 데이터 및 포인터에 의해 연결된 비연속적(비순차적) 자료구조
     - 원소들이 기억 장소 내 어느 곳에서나 위치 가능
     - 노드의 삽입과 삭제가 용이하며, 기억공간이 절약됨
        . 항목의 삭제,삽입 시에 데이터 이동 필요 없음
     - 한편, 배열에 의한 연결 리스트의 구현시에는, 요소의 추가,삭제에 비교적 많은 시간이 소요
     - 또한, 상대적으로 구현이 어렵고, 포인터의 저장 필요에 저장공간이 많이 소요됨

  ㅇ 원소의 순서는, 링크를 이용하여 유지시켜 줌

  ㅇ 원소에의 접근은, 순차적으로 줄 만 따라가면 됨


3. 연결 리스트의 형태

  ㅇ { 노드 : (데이터값, 링크) } 가 하나의 단위로써 저장됨
       

     - 여기서, 포인터 변수는, 
        . 연결 리스트의 첫번째 원소를 가리키지만, 연결 리스트 전체를 가리키기도 함
        . 이렇게 전체를 가리키는 경우에는, 관례적으로 대문자로 시작하는 변수명을 씀

  ㅇ 연결 리스트의 처음과 끝
     - 리스트의 처음 노드 : 헤드(Head) 노드
     - 리스트의 끝 노드 : 테일(Tail) 노드, 엔드(End) 노드
     * 통상 묵시적으로, 데이터 없이 시작,끝 만을 알림


4. 연결 리스트의 구분

  ㅇ 단순 연결 리스트 (Singly Linked Linear List)
     - 노드들을 한 줄로 연결시킨 자료구조
        . 단방향 연결됨 : 각 원소(노드)에 단방향 단일 링크 필드 필요
        . 노드 포인터는, 다음 노드를 가리킴
        . 마지막 노드링크는, NULL 값을 갖음

     - 구현 例) struct LinkedListNode { int data; struct LinkedListNode *next; }; 

  ㅇ 이중 연결 리스트 (Doubly Linked Linear List)
     - 후행 노드 및 선행 노드 모두를 가리킬 수 있게, 2개의 포인터를 갖음으로, 양방향 가능
     - 즉, 순방향,양방향 탐색 모두 가능

  ㅇ 원형 연결 리스트 (Circularly Linked Linear List) 
     - 마지막 노드링크리스트의 처음 노드를 가리킴
     - 즉, 단순 연결 리스트의 처음과 끝을 연결하면 원형 연결 리스트가 됨


[선형 자료구조 (리스트 등)] 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.   기술경영

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