5강. 연결 리스트

by

학습개요

리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조입니다. 원소들 간의 순서가 논리적으로(추상적으로) 지켜져야 하며, 각각의 원소가 저장되는 물리적인 위치가 연속적이든 불연속적이든 상관하지 않습니다.

배열을 이용하여 리스트를 구현하면, 원소의 논리적인 순서를 지키기 위해 원소의 이동이 많아집니다. 따라서 리스트를 구현하기 위해서는 일반적으로 포인터 변수를 이용한 연결 리스트를 이용합니다. 포인터 변수의 사용과 동적인 메모리 할당 방법을 이용하면 리스트 구현 프로그램의 실행에 필요한 메모리의 낭비를 막을 수 있습니다. 연결 리스트의 노드 삭제 연산과 삽입 연산은 포인터 변수를 활용하여 설명하였습니다. 포인터와 연결 리스트의 특징을 잘 이해하시기 바랍니다.

학습목표

  1. 리스트와 배열의 차이점을 이해할 수 있다.
  2. 연결 리스트의 구현을 위한 포인터 개념을 이해할 수 있다.
  3. 연결 리스트의 노드 삭제를 위한 포인터 변수의 운영을 이해할 수 있다.

연습문제

  1. 다음 중 포인터로 구현된 리스트에 대한 설명으로 틀린 것은?
    1.  ‘일정한 순서’의 나열
    2. 어떤 정의에 의해서 결정된 ‘논리적인 순서’의 나열
    3. 리스트를 포인터로 구현할 경우에는 배열에 비해서 추가적인 메모리 공간이 필요하다.
    4. 메모리 공간(주기억 장치, DDR)에서의 물리적인 위치가 논리적 위치와 일치한다.
      –
  2.  

     

     

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

    typedef struct ListNode {   // 단순 연결 리스트의 노드 구조 정의
    int data;
    [가]
    } listNode;
    typedef struct {       // 리스트의 헤드(first) 노드 구조 정의
    listNode* head;
    } linkedList_h;
     linkedList_h* createLinkedList_h(void) { // 연결 리스트 생성
          linkedList_h* H;
    [나]
    H → head = NULL;
    return H;
    }

    지문 프로그램의 (가) 에 적합한 것은?
    1.ListNode* link;
    2.struct ListNode* link;
    3.struct LinkNode* link;
    4.LinkNode* link;
    –

  3. 지문 프로그램의 (나) 에 적합한 것은?
    1. H = (list_pointer) list_node;
    2. H = (linkedList_h*)malloc(sizeof(linkedList_h));
    3. H = struct list_node;
    4. H = list_node → data;

정리하기

  1. 리스트의 ‘순서’는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’를 의미합니다.
  2. 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있습니다. 자료의 삽입과 삭제가 빈번히 발생하는 상황에서, 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발합니다.
  3. 포인터를 이용하는 방법은 원소의 자리에는 원소값을 저장하고, 다음 원소를 가리키는 정보의 자리에는 다음 원소가 저장될 위치의 주소값을 저장합니다. 조금 더 ‘프로그램’스럽게 설명하자면, 리스트의 원소 자리와 다음 원소를 가리키는 정보의 자리를 합쳐서 노드(node)라고 합시다. 노드에는 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가진다고 생각하면 됩니다. 이 포인터는 링크(link)라고도 부릅니다.
  4. 포인터의 ‘메모리 주소값’이라는 것은 메모리에 저장되는 값의 위치라고 생각하면 됩니다. 메모리에 저장되는 값(데이터)은 저장 위치에 대한 주소를 가지며, 이 저장 위치를 이용해서 리스트의 원소값을 찾아갈 수 있습니다.
  5. 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법이 구조체(struct)입니다.

Leave a Comment