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

(2019-06-07)
1. 연결 리스트 (Linked List)

  ㅇ 연결 리스트는, 고정 크기의 배열 등에 의해 구현된 선형리스트의 단점을 보완한 자료구조 임

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

  ㅇ 노느 저장 단위
     - { 노드 : (데이터값,링크) } 가 하나의 단위로써 저장됨
         
        . 여기서, 포인터 변수는, 
           .. 연결 리스트의 첫번째 원소를 가리키지만, 연결 리스트 전체를 가리키기도 함
           .. 연결 리스트 전체를 가리키는 경우에, 관례적으로 대문자로 시작하는 변수명을 씀

  ㅇ 연결 리스트의 처음과 끝
     - 리스트의 처음 노드 : 헤드(Head)
     - 리스트의 끝 노드 : 테일(Tail)

  ㅇ 연결 리스트 구분
     - 단순 연결 리스트 (Singly Linked Linear List)
        . 각 원소에 단방향 단일 링크 필드 필요
     - 원형 연결 리스트 (Circularly Linked Linear List) 
        . 마지막 노드링크리스트의 처음 노드를 가리킴
     - 이중 연결 리스트 (Doubly Linked Linear List)
        . 후행 노드 및 선행 노드 모두를 가리키는 포인터를 갖음으로 양방향 가능


[선형자료구조(리스트 등)] 1. 리스트 2. 연결 리스트 3. 4. 스택 5. 데크
[배열]

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