배열 기반 리스트

리스트 자료구조는 크게 두가지로 나뉨

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

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

리스트 자료 구조의 특성

: 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.

아래 예제 파일을 열어 ArrayList.c는 가급적 열지 않고 직접 구현해보도록

* 자료 구조의 내부 구현을 모르고도 해당 자료구조의 활용이

가능하도록 ADT를 정의하는 것이 맞다.

리스트의 데이터 참조 과정

순서대로 참조하려면 먼저 LFirst를 호출해 첫번째 데이터를 얻는다.

두 번째 이후의 데이터는 LNext를 호출해서 얻는다.

LFirst 함수와 LNext 함수는 더 이상 참조할 데이터가 없으면 

FALSE를 반환한다.

리스트내에서 '데이터 참조위치'를 기록하기 때문에,

참조를 새롭게 시작하기 위해선 LFirst함수를 호출해 정보를 초기화한다.

ListMain.c

#include <stdio.h> #include "ArrayList.h" int main(void) { /*** ArrayList의 생성 및 초기화 ***/ List list; int data; int i; int sum = 0; ListInit(&list); /*** 정수 1부터 9까지 데이터 저장 ***/ for (i = 1; i < 10; i++) LInsert(&list, i); /*** 저장된 데이터의 합 출력 ***/ if (LFirst(&list, &data)) { sum = sum + data; while (LNext(&list, &data)) sum = sum + data; } /*** 저장된 데이터의 전체 출력 ***/ printf("현재 데이터 수 : %d\n", LCount(&list)); if (LFirst(&list, &data)) { printf("%d ", data); while (LNext(&list, &data)) printf("%d ", data); } printf("\n합 : %d \n\n", sum); /*** 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); } } /*** 저장된 데이터의 전체 출력 ***/ printf("현재 데이터 수 : %d\n", LCount(&list)); if (LFirst(&list, &data)) { printf("%d ", data); while (LNext(&list, &data)) printf("%d ", data); } printf("\n"); return 0; }

Output :

현재 데이터 수 : 9

1 2 3 4 5 6 7 8 9

합 : 45

현재 데이터 수 : 3

1 5 7

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

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

typedef LinkedList List; // List는 연결 기반 리스트

List에 다른 이름을 부여하는 것만으로 사용하는 리스트의 종류를 바꿀 수 있다.

typedef int LData; 도 마찬가지로 다른 이름을 부여해 활용할 수 있다.

ArrayList.c    // 가급적 스스로 구현을 연습해보는 것이 좋다.

#include <stdio.h> #include "ArrayList.h" void ListInit(List * plist) // 리스트 초기화 { (plist->numOfData) = 0; (plist->curPosition) = 0; // -1에서 0으로 참조 위치 초기화, 첫번째 데이터 참조 } void LInsert(List * plist, LData data) { if (plist->numOfData >= LIST_LEN) // 데이터 개수가 배열 총 길이보다 많거나 같으면 저장불가 { puts("데이터 저장불가"); return; } plist->arr[plist->numOfData] = data; // 데이터 저장, numOfData를 index값으로 활용 (plist->numOfData)++; } int LFirst(List * plist, LData * pdata) // 첫번째 데이터가 pdata가 가리키는 메모리에 저장 { if (plist->numOfData == 0) // 저장된 데이터가 없으면 return FALSE;// FALSE 반환 (plist->curPosition) = 0; // 현재 참조위치가 초기화 *pdata = plist->arr[0]; // plist->arr[plist->curPosition]와 같은 의미지만 강조를 위한 것 return TRUE; } int LNext(List * plist, LData * pdata) { if (plist->curPosition >= (plist->numOfData) - 1) // 더 이상 참조할 데이터가 없을 때(현재 참조위치와 데이터 수 비교) return FALSE; // FALSE 반환 (plist->curPosition)++; *pdata = plist->arr[plist->curPosition]; return TRUE; } LData LRemove(List * plist) { int rmPos = plist->curPosition; // 현재 위치가 삭제할 위치가 된다. LData rmData = plist->arr[rmPos]; // 삭제할 인덱스의 데이터를 rmData에 저장 // 해당 인덱스 삭제후, 한칸씩 왼쪽 이동해 그 빈칸을 메움 int i; for (i = rmPos; i < (plist->numOfData) - 1; i++) plist->arr[i] = plist->arr[i + 1]; // 오른쪽의 인덱스가 왼쪽으로 이동 (plist->numOfData)--; (plist->curPosition)--; // curPosition이 참조가 이뤄지지않은, 이동한 데이터를 가리키므로 참조위치를 왼쪽으로 옮겨야 함 return rmData; // 삭제된 데이터는 반환해야 한다. (이것은 메모리의 공간 해제를 위한 것) } int LCount(List * plist) // 리스트에 저장된 데이터 수(numOfData) 반환 { return plist->numOfData; }

배열 기반 리스트의 장 단점

장점

인덱스 값을 기준으로 쉽게 참조가 가능하다.

단점

배열 길이가 초기에 결정되며 변경 불가능하다.

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