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

1. 연결 리스트 (Linked List)

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

  ㅇ 데이터 및 링크(포인터)에 의해 비 연속적(비 순차적)으로 연결된 선형 자료구조


2. 연결 리스트의 특징

  ㅇ 포인터로 연결됨
     - 원소들이 메모리 내 어느 위치에도 가능
     - 동적으로 노드의 삽입과 삭제가 용이
        . 항목의 삭제,삽입 시에 데이터 이동 필요 없음
     - 원소 끝 포인터는 비어있거나 null을 지시 함

     * 한편, 배열에 의해 연결 리스트 형식을 구현할 때에는, 
        . 요소의 추가,삭제에 비교적 많은 시간이 소요됨

  ㅇ 크기가 가변적임
     - 메모리 허용하는 만큼 커질 수 있음
     - 메모리 공간 사용이 효율적이나, 포인터를 위해 추가 메모리 필요
     
  ㅇ 원소의 순서 유지 및 순차 접근이 규칙을 따름
     - 원소의 순서는, 링크를 이용하여 유지시켜 줌
     - 원소에의 접근은, 순차적으로 줄 만 따라가면 됨 
        . 단, 이 점이 오히려 검색 시간면에서는 단점 임
        . 최악의 경우, O(n) 시간이 걸림

  ㅇ 상대적으로 구현이 어려움 (선형리스트에 비해)
     - 다만, 포인터의 저장 필요성 때문에, 저장 공간이 조금 더 많이 소요되나,
     - 빈 틈이 거의 없게 할 수 있어서, 전체적으로 보아 기억공간이 오히려 절약됨

  ㅇ 다른 자료구조(추상자료형,ADT)의 기반이 됨
     - 즉, 큐, 스택, 해시 테이블 등


3. 연결 리스트의 형태

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

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

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


4. 연결 리스트의 필요 연산 例)                                         ☞ 리스트 연산 참조
                                       
  ㅇ 삽입,삭제
     - prepend(element) : 처음 노드에 추가
     - append(element) : 끝 노드에 추가
     - delete(element) : 노드 삭제
     - deleteTail() : 끝 노드 삭제
     - deleteHead() : 처음 노드 삭제
  ㅇ 검색, 개수 세기 등
     - find()
     - size()


5. 연결 리스트의 구분

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

     - 구현 例) struct LinkedListNode { int data; struct LinkedListNode *next; }; 
        [참고] ☞ 연결리스트 C 구현 참조

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

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