[자료구조] 240611~240629 - ch3. 배열 기반 리스트(Array List)

두 달 전, 몇 주동안 작성했던 글이 덮어쓰기 도중에 날라가버려서 매우 상심했었는데 개강한 지금, 자료구조 공부의 시급함을 느끼고 이를 정리하려고 한다.

 

챕터 3의 진짜 이름은 "연결리스트(Linked List) 1"이지만 해당 챕터가 배열 기반 리스트를 다루고 있다고 판단하여 이번 포스트를 "배열 기반 리스트"로 명명하게 되었다.

윤성우의 열혈 자료구조 - 예스24

 

 

(아래의 레포에 실습 코드들을 정리해놓았다.)

https://github.com/Learning-N-Running/data-structure

---

1. ADT(추상자료형)

- 구체적인 기능의 완성과정을 언급하지 않고 순수하게 기능이 무엇인지 나열한 것.

- '자료형'과 '추상 자료형' 모두 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있다.

 

모든 자료구조는 그 내부 구현을 알지 못해도 활용할 수 있도록 구현해야 함. => 그러기 위해서는 ADT 정의가 필수!

2. 배열을 이용한 리스트의 구현(추상자료형)

2-1. 리스트의 이해

List ≠ Linked List

 

리스트라는 자료구조는 구현 방법에 따라 크게 두 가지로 나뉜다.

- 순차 리스트: 배열을 기반으로 구현된 리스트

- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트

 

각종 자료구조들의 ADT는 필요에 따라서 차이가 난다. 즉, 표준이 아니다.

 

하지만 해당 자료구조의 가장 기본 특성을 따르는 형태로 ADT가 정의되는데,
리스트 자료구조의 가장 기본적이고 중요한 특성은

리스트 자료구조는 데이터를 나란히 저장한다.
그리고 중복된 데이터의 저장을 허용한다.

2-2. 리스트의 ADT

ADT를 정의할 때에는 그 자료구조의 기본적인 특성을 바탕으로 제공해야할 기능들을 나열해야한다.

 

따라서 리스트의 ADT를 정의할 때의 접근 방식은

❌ 일단 데이터를 나란히 저장해야 하니까 어떻게 짜야할까?
✅ 데이터를 나란히 저장하니까 어떤 기능을 제공해야할까?

 

 

[리스트 자료구조의 ADT]
✏️ Operations

 

void ListInit(List *plist)

- 초기화할 리스트의 주소값을 인자로 전달한다.
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

 

void LInsert(List *plist, LData data)

- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

 

int LFirst(List *plist, LData *pdata)

- 첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.
- 데이터 참조를 위한 초기화가 진행된다.
- 참조 성공시 TRUE(1), 실패 시 FALSE(0)을 반환

§ pdata: 참조한 데이터를 저장하는 변수

 

int LNext(List *plist, LData *pdata)

- 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
- 순차적인 참조를 위해서 반복 호출이 가능하다.
- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
- 참조 성공시 TRUE(1), 실패 시 FALSE(0)을 반환

 

LData LRemove(List *plist)

- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.(현재 참조 위치의 데이터 삭제)
- 삭제된 데이터는 반환된다.
- 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

 

int LCount(List *plist)

- 리스트에 저장되어 있는 데이터의 수를 반환한다.

 

2-3. 리스트의 ADT를 기반으로 정의된 main 함수

ArrayListMain.c

#include <stdio.h>
#include "ArrayList.h"

int main(void)
{

  // ArrayList의 생성 및 초기화
  int data;
  List list;
  ListInit(&list);

  // 5개 데이터 저장
  LInsert(&list, 11);
  LInsert(&list, 11);
  LInsert(&list, 22);
  LInsert(&list, 22);
  LInsert(&list, 33);

  // 저장된 데이터의 전체 출력
  printf("현재 데이터의 수 : %d\n", LCount(&list));
  if (LFirst(&list, &data)) // 첫 번째 데이터 조회
  {
    printf("%d ", data);

    while (LNext(&list, &data)) // 두 번째 이후의 데이터 조회
    {
      printf("%d ", data);
    }
  }
  printf("\n\n");

  // 숫자 22를 탐색하여 모두 삭제
  if (LFirst(&list, &data))
  {
    if (data == 22)
      LRemove(&list);

    while (LNext(&list, &data))
    {
      if (data == 22)
        LRemove(&list);
    }
  }

  // 삭제 후 남은 데이터 전체 출력
  printf("현재 데이터의 수 : %d\n", LCount(&list));
  if (LFirst(&list, &data))
  {
    printf("%d ", data);

    while (LNext(&list, &data))
    {
      printf("%d ", data);
    }
  }
  printf("\n\n");

  return 0;
}

 

<실행 결과>

현재 데이터의 수 : 5
11 11 22 22 33 

현재 데이터의 수 : 3
11 11 33

 

이 파일의 실행결과를 보기 위해서는 ArrayList.h(리스트 자료구조의 헤더파일), ArrayList.c(리스트 자료구조의 소스파일)가 필요하다. 하지만 이 단계에서의 의도는 리스트 자료구조의 내부 구현은 모르는 상태로, ADT만 가지고 main함수를 작성하는 것이기때문에 위의 두 파일들은 자료실에서 다운받아 실습을 진행했다.

 

코드를 쪼개서 살펴보자.

 

◆◆

ListInit

int main(void)
{
  List list;
  ....
  ListInit(&list);
  ....
}

모든 자료구조는 내부적으로 다양한 정보를 담게 된다. 그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다. 따라서 이와 관련된 변수들을 초기화해야하며, 이를 담당하는 함수가 ListInit이다.

 

◆◆

  LInsert(&list, 11);

<   &연산자를 활용해서 list의 주소값을 전달하는 이유   >

포인터는 변수나 객체의 메모리 주소를 저장하는 데 사용된다.

변수의 주소를 포인터에 저장하려면, 변수 앞에 & 연산자 (주소 연산자)를 사용해야 한다. 이 연산자는 해당 변수의 메모리 주소를 반환한다. 여기서 LInsert 함수를 포함한 다른 함수들이 포인터를 사용하여 변수(여기서는 리스트)의 주소를 전달한 이유는 원본 변수에 직접 접근하여 값을 수정하기 위함이다.

 

§ 참조하다(컴퓨터 과학에서의 의미): 데이터, 객체, 변수등의 실제 인스턴스나 값이 아닌 그것의 주소, 위치 혹은 식별자를 사용하여 간접적으로 접근하는 행위를 하는 것.

 

◆◆

데이터의 참조방식

  if (LFirst(&list, &data))
  {
    printf("%d ", data);

    while (LNext(&list, &data))
    {
      printf("%d ", data);
    }
  }

- LFirst를 호출해서 첫번째 데이터를 얻어라. 그리고 두번째 데이터부터는 LNext를 호출해서 얻으면 된다.

- LFirst함수와 LNext 함수는 더이상 참조할 데이터가 없으면 FALSE를 반환한다.

 

여기서 LFirst함수를 호출하도록 ADT를 설계한 이유는 뭘까.

리스트 내에서는 '데이터의 참조위치'를 기록하기 때문이다. 따라서 처음부터 참조를 새롭게 시작하기 위해서는 바로 이 정보를 초기화해야한다.

 

◆◆

데이터의 삭제

 if (LFirst(&list, &data))
  {
    if (data == 22)
      LRemove(&list);

    while (LNext(&list, &data))
    {
      if (data == 22)
        LRemove(&list);
    }
  }

삭제를 위해서는 탐색이 선행되어야 하기에,
LRemove 함수가 호출되는 시점은 
- LFirst 함수가 호출된 이후

- LNext 함수가 호출된 이후

이다.

* 문제 3-1 리스트 라이브러리의 활용

#include <stdio.h>
#include "ArrayList.h"

int main(void)
{

    // 1. 리스트를 생성 및 초기화 한 다음, 정수 1부터 9까지 리스트에 저장한다.
    List list;
    int data;
    ListInit(&list);

    for (int i = 1; i < 10; i++)
    {
        LInsert(&list, i);
    }

    // 2. 리스트에 저장된 값 순차적으로 참조하여 그 합을 게산하여 출력한다.
    int sum = 0;
    if (LFirst(&list, &data))
    {
        sum += data;
        while (LNext(&list, &data))
        {
            sum += data;
        }
    }
    printf("sum= %d \n", sum);

    // 3. 리스트에 저장된 값들 중 2의 배수와 3의 배수에 해당하는 값을 모두 삭제한다.
    if (LFirst(&list, &data))
    {
        if (data % 2 == 0 || data % 3 == 0)
        {
            LRemove(&list);
        }

        while (LNext(&list, &data))
        {
            if (data % 2 == 0 || data % 3 == 0)
            {
                LRemove(&list);
            }
        }
    }

    // 4. 마지막으로 리스트에 저장된 데이터를 순서대로 출력한다.
    if (LFirst(&list, &data))
    {
        printf("%d ", data);

        while (LNext(&list, &data))
        {
            printf("%d ", data);
        }
    }
    printf("\n");

    return 0;
}

2-4. 리스트! 배열을 기반으로 구현하기: 헤더파일의 정의

어떤 자료구조이건 간에 '자료구조의 구현'과 '구현된 자료구조의 활용'은 완전히 구분되도록 ADT를 정의해야한다.

 

아래는 배열 기반의 리스트 구현을 위해 정의된 헤더파일이다.

ArrayList.h

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE 1
#define FALSE 0

#define LIST_LEN 100
typedef int LData; // 리스트에 int형 데이터의 저장을 위한 선언

typedef struct __ArrayList
{
  LData arr[LIST_LEN]; // 리스트의 저장소인 배열
  int numOfData;       // 저장된 데이터의 수
  int curPosition;     // 데이터의 참조위치를 기록
} ArrayList;

typedef ArrayList List; // List는 배열 기반 리스트

void ListInit(List *plist);            // 초기화
void LInsert(List *plist, LData data); // 데이터 저장

int LFirst(List *plist, LData *pdata); // 첫 데이터 참조
int LNext(List *plist, LData *pdata);  // 두 번재 이후 데이터 참조

LData LRemove(List *plist); // 참조한 데이터 삭제
int LCount(List *plist);    // 저장된 데이터의 수 반환

#endif

 

헤더 파일에서는 변수, 구조체, 함수의 선언등이 이루어진다고 보면 된다.

2-5. 리스트! 배열을 기반으로 구현하기: 삽입과 조회

이제 헤더파일에 선언된 함수들을 정의하자.

 

◆◆

ListInit

void ListInit(List *plist)
{
    (plist->numOfData) = 0; //리스트에 저장된 데이터의 수는 0!
    (plist->curPosition) = -1; // 현재 아무 위치도 가리키지 않음!
}

§ -> 연산자: 

*plist가 List 구조체의 주소를 가리킬 때, plist→ numofData는 그 구조체(List)의 멤버인 numOfData 필드에 접근하여 값을 얻거나 설정한다.

 

curPosition에는 배열의 index값이 저장된다. 그리고 이 변수에 저장된 값을 통해 LFirst 함수와 LNext 함수가 참조해야 할 배열의 위치를 알게 한다.

 

◆◆

LInsert

void LInsert(List *plist, LData data)
{
    if (plist->numOfData >= LIST_LEN) // 더 이상 저장할 공간이 없다면
    {
        puts("저장이 불가능합니다.");
        return;
    }
    plist->arr[plist->numOfData] = data; // 데이터 저장
    (plist->numOfData)++; // 저장된 데이터의 수 증가
}

§ puts: 문자열 출력, 자동 줄바꿈

 

◆◆

LFirst와 LNext

int LFirst(List *plist, LData *pdata)
{
    if (plist->numOfData == 0) // 저장된 데이터가 하나도 없다면
    {
        return FALSE;
    }
    (plist->curPosition) = 0; // 참조 위치 초기화! 첫 번째 데이터의 참조를 의미!
    *pdata = plist->arr[0]; //pdata가 가리키는 공간에 데이터 저장
    return TRUE;
}

 

int LNext(List *plist, LData *pdata)
{
    if (plist->curPosition >= plist->numOfData - 1) // 더 이상 참조할 데이터가 없다면
    {
        return FALSE;
    }
    plist->curPosition++;
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}

 

위 두 함수의 차이점은 plist->curPosition을 어떻게 세팅하느냐에 달려있다.

LFirst 함수는 curPosition에 저장된 값을 0으로 재설정함으로써 데이터의 참조가 앞에서부터 다시 진행되도록 하는 역할을 한다.

(plist->curPosition) = 0;

 

반면에, LNext는 이 값을 증가시켜서 순서대로 데이터를 참조할 수 있도록 한다.

plist->curPosition++;

 

 

이 코드는 저자의 취향과는 관련이 없다.

어떤 라이브러리를 사용하건, 저장된 데이터의 조회를 위해 LFirst 함수의 호출과 같은 별도의 과정을 거친다.

2-6. 리스트! 배열을 기반으로 구현하기: 삭제

◆◆

LRemove

LFirst 함수나 LNext 함수의 호출을 통해서 바로 직전에 참조가 이뤄진 데이터를 LRemove가 삭제하는 형태로 진행된다.

=> LRemove 함수가 호출되면 리스트의 멤버인 curPostion을 확인해서, 조회가 이뤄진 데이터의 위치를 확인한 후, 그 데이터를 삭제한다.

[+] 앞에서부터 데이터를 채우는 것이 원칙이니 중간에 데이터가 삭제되면, 뒤에 저장된 데이터들을 한 칸씩 앞으로 이동시켜서 그 빈 공간을 메워야 한다.

LData LRemove(List *plist)
{
    int rpos = plist->curPosition; // 삭제할 데이터의 인덱스 값 참조
    int num = plist->numOfData;
    LData rdata = plist->arr[rpos]; // 삭제할 데이터를 임시로 저장(반환을 위해)

	// 삭제를 위한 데이터의 이동을 진행하는 반복문
    for (int i = rpos; i < num - 1; i++)
    {
        plist->arr[i] = plist->arr[i + 1];
    }
    (plist->numOfData)--; // 데이터의 수 감소
    (plist->curPosition)--; // 참조위치를 하나 앞으로(배열 기준 왼쪽으로) 옮긴다.

    return rdata; // 삭제될 데이터의 반환
}

 

* 그림으로 이해하기

2-7. 배열 기반의 리스트 구현 하나로 묶기

ArrayList.c

#include <stdio.h>
#include "ArrayList.h"

/**
 * 초기화할 리스트의 주소값을 인자로 전달한다.
 * 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
 */
void ListInit(List *plist)
{
    (plist->numOfData) = 0;
    (plist->curPosition) = -1;
}

/**
 * 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
 */
void LInsert(List *plist, LData data)
{
    if (plist->numOfData >= LIST_LEN)
    {
        puts("저장이 불가능합니다.");
        return;
    }
    plist->arr[plist->numOfData] = data;
    (plist->numOfData)++;
}
/**
 * 첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.
 * 데이터 참조를 위한 초기화가 진행된다.
 * 참조 성공시 TRUE(1), 실패 시 FALSE(0)을 반환
 */
int LFirst(List *plist, LData *pdata)
{
    if (plist->numOfData == 0)
    {
        return FALSE;
    }
    (plist->curPosition) = 0;
    *pdata = plist->arr[0];
    return TRUE;
}
/**
 * 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
 * 순차적인 참조를 위해서 반복 호출이 가능하다.
 * 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
 * 참조 성공시 TRUE(1), 실패 시 FALSE(0)을 반환
 */
int LNext(List *plist, LData *pdata)
{
    if (plist->curPosition >= plist->numOfData - 1)
    {
        return FALSE;
    }
    plist->curPosition++;
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}
/**
 * LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
 * 삭제된 데이터는 반환된다.
 * 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
 */
LData LRemove(List *plist)
{
    int rpos = plist->curPosition;
    int num = plist->numOfData;
    LData rdata = plist->arr[rpos];

    for (int i = rpos; i < num - 1; i++)
    {
        plist->arr[i] = plist->arr[i + 1];
    }
    (plist->numOfData)--;
    (plist->curPosition)--;

    return rdata;
}
/**
 * 리스트에 저장되어 있는 데이터의 수를 반환한다.
 */
int LCount(List *plist)
{
    return plist->numOfData;
}

2-8. 리스트에 구조체 변수 저장하기_1: 구조체 Point와 관련 함수들의 정의

Point.h

#ifndef __POINT_H__
#define __POINT_H__

typedef struct _point
{
    int xpos;
    int ypos;
} Point;

// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point *ppos, int xpos, int ypos);

// Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point *ppos);

// 두 Point 변수의 비교
int PointComp(Point *pos1, Point *pos2);

#endif

 

§ include gruard:

#ifndef, #define

실수로 인해 header 파일이 한 번 이상 include되는 걸 막는 방법

 

Point.c

#include <stdio.h>
#include "Point.h"

void SetPointPos(Point *ppos, int xpos, int ypos)
{
    ppos->xpos = xpos;
    ppos->ypos = ypos;
}

void ShowPointPos(Point *ppos)
{
    printf("[%d,%d]", ppos->xpos, ppos->ypos);
}

int PointComp(Point *pos1, Point *pos2)
{
    if (pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
        return 0;
    else if (pos1->xpos == pos2->xpos)
        return 1;
    else if (pos1->ypos == pos2->ypos)
        return 2;
    else
        return -1;
}

2-9. 리스트에 구조체 변수 저장하기_2: 구조체 Point와 관련 함수들의 정의

Point 구조체 변수의 주소값을 리스트에 저장할 수 있도록 해보자.

이때, 전에 배열로 리스트를 구현한 ArrayList.c, ArrayList.h 파일을 조금 수정해서 사용할 것이다.

헤더 파일은 일부 변경해야하지만, 소스 파일은 변경하지 않는다.

 

헤더파일인 ArrayList.h는 typedef 선언만 변경하면 된다.

 

ArrayList.h

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#include "Point.h"

#define TRUE 1
#define FALSE 0

#define LIST_LEN 100
typedef Point *LData; // 변경 부분

typedef struct __ArrayList
{
  LData arr[LIST_LEN];
  int numOfData;
  int curPosition;
} ArrayList;

typedef ArrayList List;

void ListInit(List *plist);
void LInsert(List *plist, LData data);

int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);

LData LRemove(List *plist);
int LCount(List *plist);

#endif

 

§ 왜 Ldata는 Point 구조체의 "포인터 타입"인가?:

두 달만에 복습하면서 든 질문이다. 책에 적어놓지 않은 것으로 보아 두 달 전에는 이게 안 궁금했던 것 같은데.. 그래서 찾아봤다.

이유는 크게 세 가지이다.

 

(1) 메모리 효율성

Point 구조체 자체를 ArrayList에 직접 저장하는 것보다 Point 구조체의 포인터를 저장하는 것이 메모리 사용 측면에서 더 효율적이다. 구조체가 크거나 ArrayList가 많은 데이터를 저장할 경우, 구조체의 복사본을 여러 번 만들게 되면 메모리의 사용량이 많아질 수 있다. 포인터를 사용하면 각 요소마다 실제 데이터의 주소만 저장하면 되므로 메모리 사용량을 줄일 수 있다.

 

(2) 데이터 조작의 유연성

ArrayList에 저장된 Point의 데이터(ex. 멤버)를 수정할 때, 포인터를 통해 직접 해당 데이터에 접근하여 수정할 수 있다. 이는 구조체를 직접 저장했을 때보다 간편하고 빠르게 데이터를 변경할 수 있게 해준다.

 

(3) 동적 메모리 관리의 용이성

Point 구조체의 포인터를 사용하면, ArrayList 내의 각 요소를 동적으로 할당하고 해제하는 것이 가능해진다. 이는 프로그램 실행 중 데이터의 구조의 크기가 변경되어야 할 때 유용하게 사용될 수 있다. 동적 메모리 할당을 통해 필요할 때만 메모리를 할당받고, 더 이상 필요하지 않을 때 해제함으로써 메모리 사용의 효율성을 극대화할 수 있다.

 

이해하고 나서야 애초에 목표 자체가 "리스트에 Point 구조체 변수의 주소 값을 저장해보자" 였다는 것을 알게되었다...(2-9의 첫문장 참고) 그러나 저자의 의도를 알게 되는 것도 좋은 공부인 것 같다! 

 

PointListMain.c

#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"

int main(void)
{
    List list;
    Point compPos;
    Point *ppos;

    ListInit(&list);

    // 4개의 데이터 저장 //
    ppos = (Point *)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&list, ppos);

    ppos = (Point *)malloc(sizeof(Point)); // ppos가 가리키는 메모리 주소 변경
    SetPointPos(ppos, 2, 2);
    LInsert(&list, ppos);

    ppos = (Point *)malloc(sizeof(Point)); // ppos가 가리키는 메모리 주소 변경
    SetPointPos(ppos, 3, 1);
    LInsert(&list, ppos);

    ppos = (Point *)malloc(sizeof(Point)); // ppos가 가리키는 메모리 주소 변경
    SetPointPos(ppos, 3, 2);
    LInsert(&list, ppos);

    // 저장된 데이터 출력 //
    printf("현재 데이터의 수: %d \n", LCount(&list));
    if (LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while (LNext(&list, &ppos))
        {
            ShowPointPos(ppos);
        }
    }
    printf("\n");

    // xpos가 2인 모든 데이터 삭제 /
    compPos.xpos = 2;
    compPos.ypos = 0;

    if (LFirst(&list, &ppos))
    {
        if (PointComp(ppos, &compPos) == 1)
        {
            ppos = LRemove(&list);
            free(ppos);
        }

        while (LNext(&list, &ppos))
        {
            if (PointComp(ppos, &compPos) == 1)
            {
                ppos = LRemove(&list);
                free(ppos);
            }
        }
    }

    // 삭제 후 남은 데이터 전체 출력 //
    printf("현재 데이터의 수: %d \n", LCount(&list));

    if (LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while (LNext(&list, &ppos))
        {
            ShowPointPos(ppos);
        }
    }
    printf("\n");

    return 0;
}

<실행 결과>

현재 데이터의 수: 4 
[2,1][2,2][3,1][3,2]
현재 데이터의 수: 2 
[3,1][3,2]

 

위 main 함수를 통해 LRemove 함수가 삭제된 데이터를 반환하도록 디자인한 이유를 알 수 있다.

위의 코드에서 리스트에 저장한 데이터는 Point 구조체 변수의 주소 값이다. 이 주소값은 Point 구조체를 동적으로 할당한 결과이기 때문에, 반드시 free 함수를 통한 메모리의 해제과정을 거쳐야 한다.

하지만 일반적인 리스트는 메모리의 해제까지 책임지지 않는다. 그리고 그렇게 구현하는 것은 무리가 있다.

 

때문에 LRemove함수처럼 데이터를 소멸하는 함수는 소멸된 데이터를 반환하도록 정의해야 한다. 그래서 메모리 소멸의 기회를 줄 수 있어야 한다. 할당된 메모리 소멸의 책임을 전가해 그 사용 단에서는 메모리 소멸을 할 수 있도록 해야한다.

 

 

 

§ 왜 4개의 데이터 저장 부분에서 4번 다 독립적으로 메모리 할당을 해줄까?

맨 처음에 한 번만 메모리할당을 해주면 안되나? :

ppos = (Point *)malloc(sizeof(Point));

 

A:: 이 코드를 맨 처음에 한 번만 해주지 않는 이유는 처음 한번만 해주면 ppos는 항상 같은 메모리 주소를 가리키게 되어 리스트의 모든 요소가 마지막에 설정된 3,2의 값을 가지게 된다. 각 데이터의 독립성을 보장하기 위해 네 번 다 독립적으로 메모리 할당을 해주어야 한다.

 

 

§ 

   if (LFirst(&list, &ppos))
    {
        ShowPointPos(ppos);

        while (LNext(&list, &ppos))
        {
            ShowPointPos(ppos);
        }
    }

왜 이 코드 전에는 메모리 ppos에 대한 메모리 할당을 안 해줄까? : 

 

A:: 이미 생성되고 메모리에 할당된 Point 인스턴스들을 단지 접근하고 사용하기 때문이다. 여기서 수행하는 작업은 이미 리스트에 저장된 Point 객체들의 데이터를 읽고 출력하는 것이기 때문에, 새로운 메모리를 할당받을 필요가 없다.

 

그림을 통해 이해를 도울 수 있었다.

 

- 리스트 => 책장

- 메모리 할당 => 책을 만드는 것.

- set Point 하는 것 => 책에 저자와 출판사 정보를 적는 것

으로 비유하여 이해하였다.

 

ppos를 뭘로 비유하면 좋을까 고민했는데 사실 마땅한 비유를 찾기가 힘들었다. 그냥 이런 일을 하는 관념적인 대상정도로 생각하면 적절할 것 같다.

* 문제 3-2. 리스트의 활용

NameCard.h

(이 헤더파일에 정의된 구조체를 기반으로 리스트를 활용하는 문제)

#ifndef __NameCard_H__
#define __NameCard_H__
#define NAME_LEN 30
#define PHONE_LEN 30

typedef struct __namecard
{
    char name[NAME_LEN];
    char phone[PHONE_LEN];
} NameCard;

// NameCard 구조체 변수의 동적 할당 및 초기화 후 주소 값 반환
NameCard *MakeNameCard(char *name, char *phone);

// NameCard 구조체 변수의 정보 출력
void ShowNameCardInfo(NameCard *pcard);

// 이름이 같으면 0, 다르면 0 아닌 값 반환
int NameCompare(NameCard *pcard, char *name);

// 전화번호 정보를 변경
void ChangePhoneNum(NameCard *pcard, char *phone);
#endif

 

 

 

NameCard.c

#include "NameCard.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

NameCard *MakeNameCard(char *name, char *phone)
{
    NameCard *pcard = (NameCard *)malloc(sizeof(NameCard));
    strcpy(pcard->name, name);
    strcpy(pcard->phone, phone);

    return pcard;
}

void ShowNameCardInfo(NameCard *pcard)
{
    printf("Name: %s\n", pcard->name);
    printf("Phone: %s\n", pcard->phone);
}

int NameCompare(NameCard *pcard, char *name)
{
    return strcmp(pcard->name, name);
}

void ChangePhoneNum(NameCard *pcard, char *phone)
{
    strcpy(pcard->phone, phone);
}

 

 

NameCardListMain.c

#include "ArrayList.h"
#include "NameCard.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    NameCard *pcard;
    List list;
    char *compname = "Bob";
    char *newphonenum = "55555";

    ListInit(&list);

    // 총 3명의 전화번호 정보를 앞서 우리가 구현한 리스트에 저장한다. //
    pcard = MakeNameCard("Annie", "11111");
    LInsert(&list, pcard);
    pcard = MakeNameCard("Bob", "22222");
    LInsert(&list, pcard);
    pcard = MakeNameCard("Crong", "33333");
    LInsert(&list, pcard);

    // 특정 이름을 대상으로 탐색을 진행하여, 그 사람의 정보를 출력한다. //
    if (LFirst(&list, &pcard))
    {
        if (NameCompare(pcard, compname) == 0)
        {
            ShowNameCardInfo(pcard);
        }
        else
        {
            while (LNext(&list, &pcard))
            {
                if (NameCompare(pcard, compname) == 0)
                {
                    ShowNameCardInfo(pcard);
                    break;
                }
            }
        }
    }
    printf("\n");

    // 특정 이름을 대상으로 탐색을 진행하여, 그 사람의 전화번호 정보를 변경한다. //
    if (LFirst(&list, &pcard))
    {
        if (NameCompare(pcard, compname) == 0)
        {
            ChangePhoneNum(pcard, newphonenum);
        }
        else
        {
            while (LNext(&list, &pcard))
            {
                if (NameCompare(pcard, compname) == 0)
                {
                    ChangePhoneNum(pcard, newphonenum);
                    break;
                }
            }
        }
    }
    // 확인을 위한 전체 출력
    if (LFirst(&list, &pcard))
    {
        ShowNameCardInfo(pcard);
        while (LNext(&list, &pcard))
            ShowNameCardInfo(pcard);
    }
    printf("\n");

    // 특정 이름을 대상으로 탐색을 진행하여 그 사람의 정보를 삭제한다. //
    if (LFirst(&list, &pcard))
    {
        if (NameCompare(pcard, compname) == 0)
        {
            pcard = LRemove(&list);
            free(pcard);
        }
        else
        {
            while (LNext(&list, &pcard))
            {
                if (NameCompare(pcard, compname) == 0)
                {
                    pcard = LRemove(&list); // 사실 그냥 LRemove(&list)만 해도 문제는 없음;
                    free(pcard);
                    break;
                }
            }
        }
    }
    // 끝으로 남아있는 모든 사람의 전화번호 정보를 출력한다. //
    if (LFirst(&list, &pcard))
    {
        ShowNameCardInfo(pcard);
        while (LNext(&list, &pcard))
            ShowNameCardInfo(pcard);
    }
}

2-10. "배열 기반 리스트"의 장점과 단점

✔️ 배열 기반 리스트의 단점😠

- 배열의 길이가 초기에 결정되어야 하고 이는 변경 불가능하다.

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

 

✔️ 배열 기반 리스트의 장점😃

- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

 

 

배열도 각종 자료구조의 구현에 중요한 도구이고, 그 자체로도 훌륭한 자료구조이다.

 

 

연결 기반 리스트에는 없는 배열 기반 리스트만의 장점도 분명히 존재한다.

 

 

배열 기반 리스트가 실무에서 사용되지 않는다는 것은 잘못된 사실이다.

실무 기반 각종 라이브러리에도 배열을 기반으로 하는 자료구조가 존재한다.