알고리즘 자료구조 - 10

9장


1)
리스트: 데이터를 순서대로 나열한 자료구조

선형 리스트(linear list)
 - 배열과 같이 연속되는 기억장소에 저장되는 리스트 

연결 리스트(linked list)
 - 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라 노드의 포인터 부분을 이용하여 연결시킨 자료 구조
 - 리스트의 각 데이터를 노드(node) 혹은 요소(element)라고 하며, 각 노드는 데이터와 다음노드를 가리키는 포인터를 가지고 있다
 - 리스트에서 노드의 처음은 head node, 끝은 tail node라고 함
 - 현재 노드의 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤의 노드를 다음 노드(successor node)라고 한다

배열로 선형리스트 구성
 - 데이터를 저장하는 구조체 생성
 - 해당 구조체를 자료형으로하는 배열 생성
 - 데이터 삽입/삭제시 일일히 데이터를 옮겨야 하는 단점이 있다


2)
포인터로 연결 리스트 구성
 - 데이터와 자기자신과 같은 자료형을 가리키는 포인터로 구성된 구조체 선언
   ** 자기 참조형(self-referential)
       : 연결 리스트와 같이 "'자기 자신과 같은 자료형'을 가진 객체를 가리키는 데이터"를 가지고 있는 자료구조

 - 연결리스트 구성시 tail node의 포인터는 NULL 값을 가진다
 - 연결 리스트를 위한 구조체를 선언하며, 머리노드를 가리키는 포인터와, 현재 선택한 노드를 가리키는 포인터 맴버를 가진다
   (꼬리 노드는 NULL값으로 알 수 있으며, 이 구조체를 시작으로 노드를 연결해나간다)

 - 함수
    : initialize(초기화), search(검색), inserthead(머리에 노드삽입), inserttail(꼬리에 노드삽입), removehead(머리노드 삭제), removetail(꼬리노드 삭제), removeselet(현재 선택한 노드 삭제), terminate(모든 노드 삭제)
    : 그밖에 allocatenode(노드 생성), setnode(노드 맴버값 설정) 함수가 있으면 좋다
    : 검색시 사용하는 알고리즘은 선형검색, head부터 검색시작


3)
커서로 연결리스트 구성
 - 프로그램이 동작할 때 데이터 개수가 크게 변하지 않고 데이터 개수의 최대값이 정해져있을때 사용하는 연결리스트
 - 배열을 사용하여 리스트를 구성한다. 정확히는 구조체 배열을 사용하여 만든다
 - 구조체에는 데이터와 다음 노드를 가리키는 배열의 요소가 들어있는 인덱스(커서, cursor)로 구성하여 배열을 생성
 - 또한 해당 배열을 관리하기 위한 구조체를 생성한다
    : 배열을 가리키는 포인터, head노드 주소(요소값), 현재 선택한 노드 주소
 - 꼬리노드의 인덱스는 배열에서 있을수 없는 값(ex: -1)을 사용하여 끝임을 알려준다


프리 리스트(free list)
 - 배열로 연결리스트를 구성 시, 노드의 삽입, 삭제로 인해 단편화가 일어난다. 이를 관리하기 위해 사용하는 자료구조를 프리 리스트라 한다
 - 프리리스트는 비어있는 노드의 정보를 가지고 있는 연결 리스트이며, 스택과 같은 LIFO 구조를 가진다
 - 배열 구조체에 프리 리스트를 가리키는 커서를 추가하고, 배열 관리 구조체에는 프리 리스트의 head노드를 가리키는 커서, 배열의 가장 꼬리에 있는 노드의 주소값을 가지는 변수를 추가한다


4)
원형 리스트(circular list)
 - 선형 리스트의 꼬리노드가 머리노드를 가리키는 구조
   (즉, 선형 리스트에서 꼬리의 다음노드를 가리키는 포인터는 NULL값을 가지지만, 원형 리스트에서 꼬리의 다음노드를 가리키는 포인터는 머리노드를 가리킨다)
 - 원형 리스트는 고리모양으로 나열된 데이터를 저장할 때 알맞은 자료구조
 - 원형 리스트가 빈 원형리스트일 때, 리스트의 head값이 NULL값을 가진다
 - 원형 리스트가 1개의 노드만을 가지는 원형리스트일 때, 리스트의 head의 다음 노드 값이 head를 가리킨다
 - 원형 리스트에서 현재 선택한 노드가 머리노드와 꼬리노드 판단은 다음과 같다
     머리노드 판단: 현재 노드가 리스트의 head와 같은지 판단
     꼬리노드 판단: 현재 노드의 다음 노드값이 head와 같은지 판단


이중 연결 리스트(doubly linked list)
 - 선형 리스트의 단점인 '이전 노드로 접근'방식을 해결하고자 노드를 가리키는 방향을 역방향으로 추가한 자료구조
 - 노드를 구성하는 구조체에 기존의 데이터와 다음 노드를 가리키는 포인터 외에, 이전 노드를 가리키는 포인터가 추가된다


원형 이중 연결 리스트(circular doubly linked list)
 - 원형 리스트와 이중 연결 리스트를 합친 구조
 - 노드를 구성하는 구조체는 데이터와 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터로 구성된다
 - 리스트를 관리하는 구조체는 머리노드를 가리키는 포인터와 현재 선택한 노드에 대한 포인터로 구성된다
 - 함수
     : Initialize, search, next(다음노드로 이동), prev(이전노드로 진행), insertafter(현재노드기준 다음노드에 노드 삽입), insertdatahead, insertdatattail, remove(특정 노드 삭제), removedatahead, removedatattail, removecurrent(현재선택한 노드 삭제), nodeclear, terminate
     : 이와 같은 구성에서 선택한 데이터 추출 등의 과정이 이루어진다

   * 초기화 시, 더미노드를 생성하여, 헤드가 더미노드를 가리키게 구성한다
    - 더미노드 생성 시, 두 포인터 둘다 자기자신을 가리키게 셋팅한다
   * 리스트 종료에서는 더미노드외의 실제 데이터를 삭제하는 부분(nodeclear)과 더미노드를 삭제하는 부분으로 나뉜다
   * 리스트 검색시에는 헤드가 아닌 헤드 다음 노드부터 검색을 시작한다(종료는 헤드 노드를 만나면 종료)
    - 리스트를 구성한 이후, 더미노드는 머리노드가 가리키고 있지만(list->head), 실제 데이터기준 머리노드는 더미노드의 다음노드(list->head->next)이다
   * insertdatahead, inserdatattail, removedatahead, removedatattail의 경우, 더미노드가 아닌 데이터의 머리노드를 의미한다

** 더미노드
 - 데이터가 텅 비어 있는 상태의 노드.
 - 노드의 삽입, 삭제를 위한 논리구성을 단순화 하기 위해 사용한다
 - 책에는 head만 더미노드를 사용하는데, 이중 연결 리스트, 선형 연결 리스트의 경우 head와 tail 둘다 더미노드를 생성하기도 한다
  * 참조: https://ehpub.co.kr/c%EC%96%B8%EC%96%B4-%EC%86%8C%EC%8A%A4-%EB%8D%94%EB%AF%B8-%EB%85%B8%EB%93%9C%EC%9E%88%EB%8A%94-%EC%9D%B4%EC%A4%91-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8/

** 더미노드를 생성하여 리스트를 구성하는 이유
 - '비어 있는 리스트에 노드를 삽입하는 경우', '리스트 head에 노드를 삽입하는 경우'를 따로 처리할 필요 없이 '현재 선택한 노드 다음의 노드에 삽입'함수를 사용하는 것으로 통일시킬 수 있다