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

(2020-10-27)
1. 연결 리스트 (Linked List)

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

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

2. 연결 리스트의 특징

  ㅇ 포인터로 연결
     - 원소들이 메모리 내 어느 위치에도 가능
     - 노드의 삽입과 삭제가 용이
        . 항목의 삭제,삽입 시에 데이터 이동 필요 없음
     - 원소 끝 포인터는 null을 지시 함
     - 한편, 배열에 의한 연결 리스트의 구현시에는, 
        . 요소의 추가,삭제에 비교적 많은 시간이 소요

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

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

  ㅇ 다른 자료구조의 기반이 됨
     - 즉, , 스택, 해시 테이블3. 연결 리스트의 형태

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

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

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


4. 연결 리스트의 필요 연산 例)                                         ☞ 리스트 연산 참조
                                       
  ㅇ 삽입,삭제
     - prepend(), append(), delete(), deleteTail(), deleteHead()
  ㅇ 검색, 개수 세기 등
     - find(), size() 등      


5. 연결 리스트의 구분

  ㅇ 단순 연결 리스트 (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. 연결 리스트

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