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

(2019-12-27)
1. 연결 리스트 (Linked List)

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


2. 연결 리스트의 특징

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

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

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

  ㅇ 연결 리스트의 처음과 끝을 나타내는 용어
     - 리스트의 처음 노드 : 헤드(Head)
     - 리스트의 끝 노드 : 테일(Tail)


3. 연결 리스트노드 저장 형태

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

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


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. 데크
[배열]

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