[Data Structure] #1-1 단순 배열리스트 (ArrayList)

단순 배열 리스트 (ArrayList)

 ArrayList는 말그대로 배열(Array)을 이용한 List 자료구조이다. 배열을 사용하기 때문에 삽입과 삭제시에 그 자리(position)의 데이터부터 끝까지 한 칸씩 옮겨야 하기 때문에 삽입/삭제 시에 상대적으로 속도가 느리다. 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100

typedef int element;
typedef struct{
 element list[MAX_LIST_SIZE];
 int length;
} ArrayListType;

void error (char* message){
 fprintf(stderr, "%s\n", message);
 exit(1);
}

void init(ArrayListType *L){
 L->length = 0;
}

int is_empty(ArrayListType *L){
 return L->length == 0;
}

int is_full(ArrayListType *L){
 return L->length == MAX_LIST_SIZE;
}

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

// position 은 0부터 들어올 수 있음
void add(ArrayListType *L, int position, element item){
 if(!is_full(L) && position >=0 && position <= L->length){
  int i;

  for(i=L->length-1; i>=position; i--)
   L->list[i+1] =L->list[i];
  L->list[position] = item;
  L->length++;
 }
}
// i가 L->length-1 부터 시작하는 이유는

// length는 실제 개수를 의미하기 때문이다. 

// 즉, 배열에서 L->list[length]는 아무것도 없기 때문에 옮길 것이 없다..

// 배열을 참조할 때는 length-1 을 해줘야함.

int del(ArrayListType *L, int position){
 int i;
 element item;
 if(position < 0 || position >= L->length)
  error("position error"); // exit program
 item = L->list[position];
 for(i=position; i<L->length; i++) 
  L->list[i] = L->list[i+1];
 L->length--;
 return item;
}

int main(){
 ArrayListType list1;
 ArrayListType *plist;

 init(&list1);
 add(&list1, 0, 10);
 add(&list1, 0, 20);
 add(&list1, 0, 30);
 display(&list1);

 plist = (ArrayListType *)malloc(sizeof(ArrayListType));
 init(plist);
 add(plist, 0, 10);
 add(plist, 0, 20);
 add(plist, 0, 30);
 display(plist);
 free(plist); 
 return 0;

} 

 여기서 중요한 점은 add 함수와 del 함수다. add 함수에서 list[i] 에 있는 값을 list[i+1]로 밀어낸다. 그래서 position 자리에 원하는 item을 넣는다. del 함수는 position 자리부터 시작한다. 왜냐하면 list[i+1]에 있는 값을 list[i]로 가져와서 position 자리를 position+1의 값으로 바꿔놓는다. 아주 쉬운 자료구조이기에 여기서 종료.