[Data Structure] 배열 리스트 (ArrayList)

리스트

- 순서를 가진 데이터들의 모임

- ex) 오늘 해야 할 일 : (청소, 쇼핑, 영화 관람), 요일들 : (일, 월, 화,... 토)

 

리스트 ADT

- n개의 element형으로 구성된 순서가 있는 모임

void init_list(ArrayList *L)

• 리스트 초기화

int is_empty(ArrayList *L) 

• 공백 상태 검출 함수

int is_full(ArrayList *L) 

• 포화 상태 검출 함수

void insert(ArrayList *L, int pos, element item) 

• 리스트의 pos위치에 item 삽입

void insert_last(ArrayList *L, element item) 

• 리스트의 last에 item 삽입

void insert_first(ArrayList *L, element item) 

• 리스트의 first에 item 삽입

element delete(ArrayList *L, int pos) 

• 리스트의 pos위치에 있는 item 리턴 후 리스트에서 제거

element get_entry(ArrayList *L, int pos) 

• 리스트의 pos위치에 있는 item 리턴

int get_length(ArrayList *L) 

• 리스트가 보유하고 있는 item 개수(size) 리턴

void print_list(ArrayList *L) 

• 리스트의 모든 item print

void clear(ArrayList *L) 

• 리스트의 모든 item 제거

void replace(ArrayList *L, int pos, element item) 

• 리스트의 pos위치에 있는 요소를 item으로 변경

 

 

리스트 구현 방법

≫ 배열(Array) 

- 구현이 간단

- 데이터 삽입/삭제 시 많은 노력이 필요

- 데이터 개수 제한

 

≫ 연결 리스트(Linked-List)

- 구현이 복잡

- 데이터 삽입/삭제가 효율적

- 데이터 개수 제한 X

---

배열(Array)로 구현된 리스트

- 1차원 배열에 데이터들을 순서대로 저장

- 삽입연산 : 삽입 위치 다음에 있는 데이터들을 1칸씩 뒤로 이동

- 삭제연산 : 삭제 위치 다음에 있는 데이터들을 1칸씩 앞으로 이동

 

1. insert (삽입연산 - insert / insert_last / insert_first)

void insert(ArrayList* L, int pos, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	if (!is_full(L) && pos >= 0 && pos <= L->size) {
		for (int i = (L->size - 1); i >= pos; i--) 
			// insert할 pos ~ 마지막 item 인덱스까지 1칸씩 뒤로 옮기기
			L->list[i + 1] = L->list[i];
		L->list[pos] = item;
		L->size++; 
		// item을 하나 추가했으니까 size (현재 리스트에 있는 item 개수) 1 증가
	}
}

void insert_last(ArrayList* L, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	else
		L->list[L->size++] = item;
	    /*
		L->size == 현재 item의 마지막 인덱스 다음 인덱스 = 빈공간에다가 item 삽입
		그리고 L->size 1 증가
		*/
}

void insert_first(ArrayList* L, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	else {
		for (int i = (L->size - 1); i >= 0; i--) 
			L->list[i + 1] = L->list[i]; // 리스트의 모든 item을 1칸씩 뒤로 옮기기
		L->list[0] = item; // 리스트의 처음에 item insert
		L->size++;
	}
}

 

 

2. delete (삭제연산)

element delete(ArrayList* L, int pos) {
	// pos에 있는 item을 리턴 후 리스트에서 삭제
	if (is_empty(L)) { // 비어있으면 delete 불가
		fprintf(stderr, "Error : ArrayList is empty\n");
		return;
	}
	if (pos <= 0 || pos >= L->size) { // 위치가 알맞지 않으면 delete 불가
		fprintf(stderr, "Error : Can't access that pos\n");
	}
	else {
		element item = L->list[pos]; // pos에서 꺼낸 item 저장
		for (int i = pos; i < (L->size-1); i++)
			// pos ~ 마지막 item 인덱스까지 1칸씩 앞으로 당기기
			L->list[i] = L->list[i + 1];
		L->size--; // 하나의 item을 delete했으니까 size 1 감소
		return item; // delete한 item 리턴
	}
}

 

 

3. replace (item 교체 함수)

void replace(ArrayList* L, int pos, element item) {
	// pos위치에 있는 요소를 item으로 변경
	if (is_empty(L)) { // 비어있으면 replace 불가
		fprintf(stderr, "Error : ArrayList is empty\n");
		return;
	}
	if (pos<0 || pos>=L->size) { // 위치가 알맞지 않으면 delete 불가
		fprintf(stderr, "Error : Can't access that pos\n");
	}
	else {
		L->list[pos] = item;
	}
}

 

 

4. Full Code (ArrayList With Array)

#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE 5

typedef int element;

typedef struct {
	element list[MAX_LIST_SIZE];
	int size; // list배열에 현재 존재하는 item 개수
}ArrayList;

void init_list(ArrayList* L) {
	L->size = 0;
}

int is_empty(ArrayList* L) {
	return L->size == 0;
}

int is_full(ArrayList* L) {
	return L->size == MAX_LIST_SIZE;
}

void insert(ArrayList* L, int pos, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	if (!is_full(L) && pos >= 0 && pos <= L->size) {
		for (int i = (L->size - 1); i >= pos; i--) 
			// insert할 pos ~ 마지막 item 인덱스까지 1칸씩 뒤로 옮기기
			L->list[i + 1] = L->list[i];
		L->list[pos] = item;
		L->size++; 
		// item을 하나 추가했으니까 size (현재 리스트에 있는 item 개수) 1 증가
	}
}

void insert_last(ArrayList* L, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	else
		L->list[L->size++] = item;
	    /*
		L->size == 현재 item의 마지막 인덱스 다음 인덱스 = 빈공간에다가 item 삽입
		그리고 L->size 1 증가
		*/
}

void insert_first(ArrayList* L, element item) {
	if (is_full(L)) {
		fprintf(stderr, "Error : ArrayList is full\n");
		return;
	}
	else {
		for (int i = (L->size - 1); i >= 0; i--) 
			L->list[i + 1] = L->list[i]; // 리스트의 모든 item을 1칸씩 뒤로 옮기기
		L->list[0] = item; // 리스트의 처음에 item insert
		L->size++;
	}
}

element delete(ArrayList* L, int pos) {
	// pos에 있는 item을 리턴 후 리스트에서 삭제
	if (is_empty(L)) { // 비어있으면 delete 불가
		fprintf(stderr, "Error : ArrayList is empty\n");
		return;
	}
	if (pos <= 0 || pos >= L->size) { // 위치가 알맞지 않으면 delete 불가
		fprintf(stderr, "Error : Can't access that pos\n");
	}
	else {
		element item = L->list[pos]; // pos에서 꺼낸 item 저장
		for (int i = pos; i < (L->size-1); i++)
			// pos ~ 마지막 item 인덱스까지 1칸씩 앞으로 당기기
			L->list[i] = L->list[i + 1];
		L->size--; // 하나의 item을 delete했으니까 size 1 감소
		return item; // delete한 item 리턴
	}
}

element get_entry(ArrayList* L, int pos) {
	// pos에 있는 item을 리턴
	if (is_empty(L)) { // 비어있으면 get_entry 불가
		fprintf(stderr, "Error : ArrayList is empty\n");
		return;
	}
	if (pos <= 0 || pos >= L->size) { // 위치가 알맞지 않으면 get_entry 불가
		fprintf(stderr, "Error : Can't access that pos\n");
	}
	else
		return L->list[pos];
}

int get_length(ArrayList* L) {
	// 현재 list에 보유하고 있는 item 개수(size) 리턴
	return L->size;
}

int max_size(ArrayList* L) {
	// ArrayList 전체 size 리턴
	return MAX_LIST_SIZE;
}

void clear(ArrayList* L) {
	// 리스트 초기화 함수
	L->size = 0;
	printf("ArrayList is clear\n\n");
}

void print_list(ArrayList* L) {
	for (int i = 0; i < L->size; i++) 
		printf("%d -> ", L->list[i]);
	printf("\n\n");
}

void replace(ArrayList* L, int pos, element item) {
	// pos위치에 있는 요소를 item으로 변경
	if (is_empty(L)) { // 비어있으면 replace 불가
		fprintf(stderr, "Error : ArrayList is empty\n");
		return;
	}
	if (pos<0 || pos>=L->size) { // 위치가 알맞지 않으면 delete 불가
		fprintf(stderr, "Error : Can't access that pos\n");
	}
	else {
		L->list[pos] = item;
	}
}

int main(void) {
	ArrayList L;
	init_list(&L);

	printf("ArrayList size : %d\n\n", max_size(&L));

	printf("### insert 10 (pos 0)\n"); insert(&L, 0, 10); print_list(&L);
	printf("### insert 20 (pos 0)\n"); insert(&L, 0, 20); print_list(&L);
	printf("### insert 30 (pos 1)\n"); insert(&L, 1, 30); print_list(&L);
	printf("### insert_first 100\n"); insert_first(&L, 100); print_list(&L);
	printf("### insert_last 200\n"); insert_last(&L, 200); print_list(&L);
	printf("### insert_last 300\n"); insert_last(&L, 200); print_list(&L);
	printf("### replace (pos 0) 400\n"); replace(&L, 0, 400); print_list(&L);
	printf("### delete (pos 1) : %d\n", L.list[1]); delete(&L, 1); print_list(&L);
	printf("### get_entry (pos1) : %d\n", L.list[1]); get_entry(&L, 1); print_list(&L);
	printf("### get_length (현재 item 개수(size) 리턴) : %d\n\n", get_length(&L));
	printf("### clear\n"); clear(&L);
	printf("### insert 10 (pos 0)\n"); insert(&L, 0, 10); print_list(&L);

	return 0;
}