배열 리스트 (ArrayList)

배열 리스트(Array List)는 배열(Array)을 사용하는 선형 자료구조이다. 

배열과의 차이점은, 배열은 중간에 데이터를 빼면 빈 공간이 생겨 메모리 공간이 낭비될 수 있지만, 배열 리스트는 순차적으로 저장된다는 리스트의 특성을 가지고 있기 때문에 중간에 공간이 뻥 하고 뚫려 메모리가 낭비되는 일은 없다. 

위의 그림을 살펴보면 6개짜리 char 배열이 생성되어 있는 것을 확인할 수 있고 그 안에는 A부터 F까지 알파벳으로 초기화 되어 있다. 

배열의 특징을 가지고 있기 때문에 리스트의 원소(element)에 접근하기 위해서는 배열의 인덱스(index) 값으로 접근하여야 한다. 

이러한 특성 때문에 특정 원소에 접근할 때 빠른 속도로 접근할 수 있다.

다만 추가, 삭제가 자주 일어날 경우 해당 인덱스 뒤에 있는 원소들이 한 칸씩 모두 이동해야 하므로 많은 부하가 일어날 가능성이 있다.

배열리스트에서 구조체를 통해서 배열과 최대 저장원소, 현재 저장원소 등을 관리하면 편하다. 

리스트 생성

---

동적 할당을 통해 최대 저장 원소 n개를 가지는 배열을 생성한다. 

원소 추가

---

순차적으로 4까지 추가한 모습이다.

데이터가 하나 추가될때마다 ArrayList 구조체 안에 있는 currentElementCount도 +1씩 증가한다.

만약 이런 순차적인 증가가 아니라 어떤 포지션(position) 값을 주고 중간에 삽입하려는 구조라면, 

리스트는 순차적인 구조이므로 삽입하려는 곳 오른쪽으로 한 칸씩 이동 시켜야 한다.

이로써 삽입이 완료 되었다.

여기서 주의할점은 만약 인덱스 5까지 원소가 가득 차있으면 더 이상 원소를 받아들이지 못하고, Overflow가 발생한다는 점이다. (예외처리 주의)

원소 삭제

---

 

원소를 삭제 하는 과정 또한 중간에 데이터를 삽입하는 것과 비슷하다. 

삭제할 원소의 position값으로 해당 원소에 접근한다.

해당 원소를 삭제한 후 뒤에 있는 원소들은 왼쪽으로 한 칸씩 이동시킨다.

삭제 후 ArrayList 구조체 안에 있는 currentElementCount를 -1 해준다. 

삭제후 정렬이 완료된 모습.

나머지는 리스트 ADT를 보면서 적절하게 코드를 작성해주자. 

유의할 점은 C로 코드를 작성하였을 경우, 배열 리스트 자체를 삭제할 때 동적 할당 되어 있는 상태이기 때문에 반드시!! free 함수를 써 줘야 하는 것이다.