Chapter03. 배열을 이용한 리스트 구현

리스트는 크게 두가지로 구분되어 있다.

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

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

이는 구현 방법을 기준으로 한 구분이다. 따라서 이 두 리스트의 ADT가 동일하다고 해서 문제가 되지는 않는다.

 

리스트의 특징

º 저장 형태 : 데이터를 나란히(하나의 열로) 저장한다.

º 저장 특성 : 중복이 되는 데이터의 저장을 허용한다.

 

이것이 리스트의 ADT를 정의하는데 있어서 고려해야 할 유일한 내용이다.

이러한 특성을 유지하려고 하다보니 순차, 연결로 나뉘는 것이다.

 

모든 자료구조는 내부적으로 다양한 정보를 담게 된다. 그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다.

 

배열기반의 리스트 ADT (순차 리스트)

 

 

배열을 기반으로 한 동적할당

배열기반 ArrayList.h

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE 1
#define FALSE 0

/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData;

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


/*** 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

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE 1
#define FALSE 0

/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData;

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


/*** 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

ArrayList.c

#include 
#include "ArrayList.h"

void ListInit(List* plist)
{

    plist->numOfData = 0;
    plist->curPosition = -1;
}

void LInsert(List* plist, LData data)
{
    if (plist->numOfData > LIST_LEN)
    {
        puts("저장이 불가능합니다. \n");
        return;
    }

    plist->arr[plist->numOfData] = data;
    (plist->numOfData)++;
}

int LFirst(List* plist, LData* pdata)
{
    if (plist->numOfData == 0)
   		return FALSE;

    (plist->curPosition) = 0;
    *pdata = plist->arr[0];
    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;
}

LData LRemove(List* plist)
{
    int rpos = plist->curPosition;
    int num = plist->numOfData;
    int i;
    LData rdata = plist->arr[num];

    for (i = rpos; i < num-1; i++)
    	plist->arr[i] = plist->arr[i + 1];

    (plist->curPosition)--;
    (plist->numOfData)--;

	return rdata;
}

int LCount(List* plist)
{
	return plist->numOfData;
}

#include 
#include "ArrayList.h"

void ListInit(List* plist)
{

plist->numOfData = 0;
plist->curPosition = -1;
}

void LInsert(List* plist, LData data)
{
if (plist->numOfData > LIST_LEN)
{
puts("저장이 불가능합니다. \n");
return;
}

plist->arr[plist->numOfData] = data;
(plist->numOfData)++;
}

int LFirst(List* plist, LData* pdata)
{
if (plist->numOfData == 0)
return FALSE;

(plist->curPosition) = 0;
*pdata = plist->arr[0];
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;
}

LData LRemove(List* plist)
{
int rpos = plist->curPosition;
int num = plist->numOfData;
int i;
LData rdata = plist->arr[num];

for (i = rpos; i < num-1; i++)
plist->arr[i] = plist->arr[i + 1];

(plist->curPosition)--;
(plist->numOfData)--;

return rdata;
}

int LCount(List* plist)
{
return plist->numOfData;
}

main.c

#include 
#include "ArrayList.h"

int main(void)
{
    List list;
    ListInit(&list);
    LData data;
    int hap = 0;

    LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5);
    LInsert(&list, 6); LInsert(&list, 7); LInsert(&list, 8); LInsert(&list, 9);

// 합 구하기 //
    if (LFirst(&list, &data))
    {
        hap += data;
        while (LNext(&list, &data))
        hap += data;
    }
    printf("합은: %d \n\n", hap);

    // 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);
        }
    }

    // 저장된 데이터 출력
    if (LFirst(&list, &data))
    {
        printf("%d ", data);
        while (LNext(&list, &data))
        printf("%d ", data);
    }
    printf("\n\n");
    return 0;
}

#include 
#include "ArrayList.h"

int main(void)
{
List list;
ListInit(&list);
LData data;
int hap = 0;

LInsert(&list, 1); LInsert(&list, 2); LInsert(&list, 3); LInsert(&list, 4); LInsert(&list, 5);
LInsert(&list, 6); LInsert(&list, 7); LInsert(&list, 8); LInsert(&list, 9);

// 합 구하기 //
if (LFirst(&list, &data))
{
hap += data;
while (LNext(&list, &data))
hap += data;
}
printf("합은: %d \n\n", hap);

// 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);
}
}

// 저장된 데이터 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
while (LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
return 0;

}

 

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

연결 리스트

Point.c

#include 
#include "Point.h"

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

void ShowPointPos(Point* ppos)
{
	printf("[%d, %d] \n", 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;
}

#include 
#include "Point.h"

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

void ShowPointPos(Point* ppos)
{
printf("[%d, %d] \n", 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;
}

 

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));
    SetPointPos(ppos, 2, 2);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    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 || PointComp(&compPos, ppos) == 0)
    	{
            ppos = LRemove(&list);
            free(ppos);
    	}

        while (LNext(&list, &ppos))
        {
            if (PointComp(ppos, &compPos) == 1 || PointComp(&compPos, ppos) == 0)
            {
                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;
}

#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));
SetPointPos(ppos, 2, 2);
LInsert(&list, ppos);

ppos = (Point*)malloc(sizeof(Point));
SetPointPos(ppos, 3, 1);
LInsert(&list, ppos);

ppos = (Point*)malloc(sizeof(Point));
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 || PointComp(&compPos, ppos) == 0)
{
ppos = LRemove(&list);
free(ppos);
}

while (LNext(&list, &ppos))
{
if (PointComp(ppos, &compPos) == 1 || PointComp(&compPos, ppos) == 0)
{
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;
}

 

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

#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

 

 

위 순차리스트에서 아래의 것들을 추가하면 연결리스트로 구현이 가능하지만 변경해야 할 내용이 있다.

그리고 순차리스트의 ArrayList.h 의 LData 형을 Point * 로 바꿔주면 된다.

왜냐하면 리스트의 단위가 int형 데이터가 아닌 Point형 구조체로 이뤄졌기 때문이다.

 

그리고 여기를 보면 LRemove함수에서 return 값을 왜 주는지 이해가 가능하다.

동적할당을 통해 이뤄진 리스트 이므로 free 함수를 통하여 할당된 주소값을 해제시켜 주기 위함이다.

메모리 해제까지 리스트가 책임을 지려면 무리가 있기 떄문에 할당된 메모리 소멸의 책임을 전가한다.

 

 

배열 기반 리스트의 단점

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

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

 

배열 기반 리스트이 장점

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

 

이 장단점은 "연결 기반 리스트" 를 대상으로 비교한 결과이다.