6강. 연결 리스트의 응용

by

학습개요

단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조입니다. 따라서 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 합니다. 이러한 단점을 보완하기 위해, 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 갖는 이중 연결 리스트가 제안되었습니다.

단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안되었다. 단순 연결 리스트의 마지막 노드의 링크가 처음 노드를 가리키게 하여 원형 연결 리스트를 만듭니다. 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있습니다.

학습목표

  1. 단순 연결 리스트와 이중 연결 리스트의 장단점을 이해할 수 있다.
  2. 원형 연결 리스트의 장점을 이해할 수 있다.
  3. 이중 연결 리스트의 노드 삭제 연산과 노드 삽입 연산을 이해할 수 있다.
  4. 원형 연결 리스트의 노드 삭제 연산과 노드 삽입 연산을 이해할 수 있다.

연습문제

  1. 원형 연결 리스트에 대한 설명으로 틀린 것은?
    1. 단순 연결 리스트의 마지막 노드의 링크 필드가 단순 연결 리스트의 처음 노드를 가리키도록 하는 구조이다.
    2. 단순 연결 리스트에 비해 추가적인 메모리 공간이 필요하다. 
    3. 한 노드에서 다른 어떤 노드로도 접근할 수 있다.
    4. 한 노드의 후행 노드를 직접 접근하면서도, 선행 노드도 접근할 수 있다.
      –
  2.  

     

     

    ※ (2 ~ 3) 다음 프로그램은 2개의 노드로 구성된 연결리스트의 노드 생성과 연결에 관한 프로그램이다. 문제를 읽고 빈칸을 알맞은 답을 구하시오.

    ① void addNode(linkedList_h* H, int x) {
    ②      listNode* LastNode;
    ③      listNode* NewNode;
    ④      NewNode = (가)
    ⑤      NewNode → data = x;
    ⑥      NewNode → link = NULL;
    ⑦      if ( H → head == NULL) {
    ⑧           (나)
    ⑨           return;
    ⑩      }
    ⑪      LastNode = H → head;
    ⑫      while(LastNode → link != NULL)
    ⑬            LastNode = LastNode → link;
    ⑭      LastNode → link = NewNode;
    ⑮ }

    지문 프로그램의 (가) 에 적합한 것은?
    1. (listNode*)malloc(sizeof(listNode));
    2. listNode;
    3. (LastNode*)malloc(sizeof(listNode));
    4. listNode → link;
    –

  3. 지문 프로그램의 (나) 에 적합한 것은?
    1. H → head = listNode → link;
    2. H → head = LastNode;
    3. H → head = listNode;
    4. H → head = NewNode;

정리하기

  1. 단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조이며, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 단점을 가집니다.
  2. 이중 연결 리스트는 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 가집니다.
  3. 단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 제안된 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있습니다.

Leave a Comment