ArrayList는 크기가 고정되지않은, 즉 동적 배열을 의미한다.
배열(Array)와의 차이점으로 배열은 초기화할 때 크기를 지정해야 하지만, ArrayList는 그러지 않아도 된다.
즉 배열은 고정값의 크기를 가지게 되고, 이후에 크기를 늘리는 행위를 하려면 새로운 배열을 생성하여 내용을 복사해야 하는 반면에, ArrayList는 그냥 추가해 주면 된다.
그렇다면 동적 크기를 갖는 ArrayList를 구현하려면 어떻게 해야할까?
다른 블로그 포스트들을 보면 똑같은 코드를 바탕으로 똑같은 설명을 반복하고 있다. 해당 내용을 보면 심화된 ArrayList를 구현할 수 있기 때문에 나는 기초 구현을 하겠다.
들어가기에 앞서서, 제네릭이라는 기술이 있다. 제네릭은 쉽게 말하면 하나의 구조에 대해 여러 자료형을 사용할 수 있도록 하는 것이다. 우리가 String name이라는 변수를 통해 홍길동, 김철수, 김영희 등을 지정하는 것 처럼 name을 String뿐만 아니라 Integer, Float, Boolean, 등 여러개의 자료형을 사용할 수 있도록 해주는 것이다.
이러한 제네릭을 사용하기 위해서는 제네릭 클래스를 만들어야하는데, 간혹 어떤 클래스를 볼 때 다음과 같은 구조를 본 적 있을 것이다.
class Point<T>{ ... }
여기서 <T>부분이 제네릭 부분이며, 내가 자료형을 T로 표현한 부분은 모두 해당 클래스를 사용할 때 지정한 자료형임을 나타내는것이다. 따라서 간략히 Point 내부에는 int x, y 혹은 Float x, y 대신 T x, y를 사용함으로써 Integer를 갖는 Point와 Float을 갖는 Point를 따로 만들지 않고 하나의 Point<T>를 통해 두가지를 모두 구현할 수 있게 되는 것이다.
Array List
이름을 보면 정답이 나온다.
Array List, 즉 Array를 이용하여 List를 만드는 것이다. Array는 고정 크기를 갖는데 어떻게 동적 크기를 만든다는거지?
본 게시글의 시작 부분에서 " ... 배열은 고정값의 크기를 가지게 되고, 이후에 크기를 늘리는 행위를 하려면 새로운 배열을 생성하여 내용을 복사 ... "
즉, ArrayList는 내부에 어떤 고정 크기를 갖는 배열을 가지고 있고, 어떤 요소를 추가할 때 그 배열의 크기를 넘어가게되면 배열의 크기를 늘려주면 된다.
ArrayList를 만들기에 앞서 목적이 무엇인지 생각해보자.
1. 어떠한 Data를 보관한다.
2. 보관된 Data를 반환한다.
1. Data를 보관할 때 조금 옵션을 추가해 보자면 제일 앞에, 제일 뒤에, 특정한 위치에 이렇게 3가지가 있을 수 있다. (제일 뒤는 가장 마지막으로 추가한 Data의 뒤를 의미)
2. Data를 반환할 때 마찬가지로 옵션을 추가해 보면 제일 앞에, 제일 뒤에, 특정한 위치에 이렇게 3가지가 있다.
위 목적을 바탕으로 ArrayList가 갖는 요소를 생각해 보면 Array, index(혹은 iterator)면 충분하다.
이제 ArrayList를 만들기 위한 준비는 끝났다.
Class ArrayList
class ArrayList{
Object[] arr = null;
int capacity = 0;
int size = 0;
ArrayList(int capacity){
this.capacity = capacity;
arr = new Object[capacity];
size = 0;
}
ArrayList(){
capacity = 1;
arr = new Object[capacity];
size = 0;
}
}시작은 위와 같다. ArrayList class에 대하여 array, arr의 크기를 알려주는 capacity, 그리고 현재 arr의 size를 반환해주는 size,를 만들었다. (size는 arr이 지금까지 사용하고 있는 크기, capacity는 arr의 length를 알려주는 변수이다.)
그리고 ArrayList를 생성함과 동시에 arr을 전달받은 size로 크기를 초기화하거나, 그렇지 않은 경우 배열의 크기를 1로 설정했다.(1 이상으로 해도 된다. 다만 0으로 할 경우, ArrayList 생성 후에 삽입을 한다면 에러가 발생하니 주의하자)
Data 보관
이제 데이터 보관을 구현할 차례다. 이 때 주의해야 할 점은 다음과 같다.
1. arr이 꽉찼다면, arr의 크기를 바꾸고 내용을 복사한다.
2. 삽입하는 위치가 특정 위치일 경우, 해당 위치부터 요소들을 뒤로 한칸씩 민다.
1번의 경우, 그림으로 표현하면 다음과 같다.
arr이 가득 찬 상태에서 새로운 요소를 추가한다면, 새로운 배열을 만들고, 해당 배열의 크기를 기존의 2배로 만들면 된다. 이후에 새로운 배열에 기존 배열을 복사 하고, 새로운 요소를 추가해주면 된다.
2번의 경우, 그림으로 표현하면 다음과 같다.
그림에서 보면 새로운 요소 5를 두번째에 추가하려고 한다.
하지만 이미 두번째부터 2, 3, 4라는 요소가 삽입되어 있다. 이럴 경우, 둘, 셋, 네 번째 위치의 요소들을 뒤로 한칸씩 밀어주고, 내가 원하는 위치에 데이터를 삽입하면 된다. 이를 응용하여, 제일 앞에 요소를 추가한다면, 모든 요소를 뒤로 한칸씩 밀어주면 된다.
이를 코드로 표현하면 다음과 같다.
class ArrayList{
...
public void add(Object element){
if(size == capacity){
expandArray();
}
arr[size++] = element;
}
public void addFirst(Object element){
add(0, element);
}
public void add(int index, Object element){
if(size == capacity){
expandArray();
}
for(int i = size; i >= index; i--)
arr[i] = arr[i-1];
arr[index] = element;
size++;
}
private void expandArray(){
capacity *= 2;
Object[] tempArr = new Object[capacity];
copyArr(tempArr, arr);
arr = new Object[capacity];
copyArr(arr, tempArr);
}
private void copyArr(Object[] arr1, Object[] arr2){
for(int i = 0; i < arr2.length; i++){
arr1[i] = arr2[i];
}
}
...
}요소를 추가할 때 마다 size는 증가하게되고 따라서 arr이 가득 차게 되면 size는 capacity와 값이 같아지게된다. 이를 조건으로 사용하여 arr이 가득 찼다면 expandArray함수를 호출함으로써 arr을 크기를 확장힌다.
기본적으로 add 함수는 배열의 가장 뒤에 요소를 추가하며, 추가하고자 하는 위치가 있을 경우 해당 index로 데이터를 삽입한다.
Data 반환
데이터를 반환하는 코드는 비교적 단순하다.
원하는 위치에 대해 Object를 반환해주면 끝이다.
class ArrayList{
...
public Object get(int index){
if(size <= 0){
System.out.println("배열이 비어있습니다.");
return null;
}
return arr[index];
}
...
}이 때 주의해야 할 점은 내가 구하고자 하는 위치가 배열의 크기를 넘어설 수 있다. 이를 따로 조건문으로 처리해주어도 되지만, 그냥 반환함으로써 Out Of Bounds 예외를 출력해주어도 되기 때문에 따로 작업하지 않았다.
추가적인 동작들
추가적으로 배열 초기화, 삭제, Size 반환, Capacity 반환 등이 있을 수 있다.
삭제의 경우, 삭제하고자 하는 위치가 배열의 크기를 넘어가는지, 이미 비어있는지 등을 확인하고 삭제, 반환해주면 된다. 나는 따로 조건을 추가하지 않았다.
초기화는 현재의 capacity로 arr를 초기화 시켜주면 된다.
class ArrayList{
...
public Object remove(int index){
/*
크기 초과, 이미 비어있는지 등 조건문은 원하는대로 추가해주면 된다.
*/
Object result = arr[index];
arr[index] = null;
return result;
}
public void reset(){
arr = new Object[capacity];
}
public int size(){
return this.size;
}
public int getCapacity() {
return this.capacity;
}
}전체 코드와 실행 결과
package DataStructure;
public class ArrayList<T> {
Object[] arr = null;
int capacity = 0;
int size = 0;
public ArrayList(int capacity){
this.capacity = capacity;
arr = new Object[capacity];
size = 0;
}
public ArrayList(){
capacity = 1;
arr = new Object[capacity];
size = 0;
}
public void add(T element){
if(size == capacity){
expandArray();
}
arr[size++] = element;
}
public void addFirst(T element){
add(0, element);
}
public void add(int index, T element){
if(size == capacity){
expandArray();
}
for(int i = size; i >= index; i--)
arr[i] = arr[i-1];
arr[index] = element;
size++;
}
private void expandArray(){
capacity *= 2;
Object[] tempArr = new Object[capacity];
copyArr(tempArr, arr);
arr = new Object[capacity];
copyArr(arr, tempArr);
}
private void copyArr(Object[] arr1, Object[] arr2){
for(int i = 0; i < arr2.length; i++){
arr1[i] = arr2[i];
}
}
public T get(int index){
if(size <= 0){
System.out.println("배열이 비어있습니다.");
return null;
}
return (T) arr[index];
}
public T remove(int index){
/*
크기 초과, 이미 비어있는지 등 조건문은 원하는대로 추가해주면 된다.
*/
T result = (T) arr[index];
arr[index] = null;
size--;
if(size > 0) {
/*
삭제한 이후부터 앞으로 한칸씩 땡긴다.
*/
for(int i = index; i < size; i++) {
arr[i] = arr[i+1];
}
}
return result;
}
public void reset(){
arr = new Object[capacity];
size = 0;
}
public int size() {
return this.size;
}
public int getCapacity() {
return this.capacity;
}
}package Main;
import DataStructure.ArrayList;
public class mainTask {
public static void main(String[] args) {
System.out.println("=====짧은머리 개발자=====");
ArrayList<Integer> arr = new ArrayList<Integer>();
System.out.println("배열 크기 : " + arr.getCapacity());
System.out.println("데이터 삽입 1~5");
for(int i = 0; i < 5; i++) {
arr.add((i+1));
}
//출력
System.out.println("\n==출력==");
for(int i = 0; i < arr.size(); i++) {
System.out.print(i + "번째 : " + arr.get(i) + " | ");
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
arr.add(1, 6);
arr.add(4, 7);
System.out.println("\n==출력2==");
for(int i = 0; i < arr.size(); i++) {
System.out.print(i + "번째 : " + arr.get(i) + " | ");
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
System.out.println("1번째 요소 삭제 : " + arr.remove(1));
System.out.println("\n==출력3==");
for(int i = 0; i < arr.size(); i++) {
System.out.print(i + "번째 : " + arr.get(i) + " | ");
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
System.out.println("\n==출력4==");
while(arr.size() > 0) {
System.out.println("0번째 삭제: " + arr.remove(0));
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
System.out.println("데이터 삽입 1~5");
for(int i = 0; i < 5; i++) {
arr.add((i*2));
}
//출력
System.out.println("\n==출력6==");
for(int i = 0; i < arr.size(); i++) {
System.out.print(i + "번째 : " + arr.get(i) + " | ");
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
System.out.println("초기화");
arr.reset();
System.out.println("\n==출력7==");
for(int i = 0; i < arr.size(); i++) {
System.out.print(i + "번째 : " + arr.get(i) + " | ");
}
System.out.println("\n배열 크기 : " + arr.getCapacity());
}
}
이상 ArrayList 게시를 마치고, 다음엔 Stack을 올려야겠다.
제네릭은 다음 글 부터 설명을 포함하여 쓰겠다. 일단 처음이니까 패스!
'언어 > Java' 카테고리의 다른 글
| [자료구조] Java Tree 구현 / 자바 트리 구현 (0) | 2021.06.28 |
|---|---|
| [자료구조] Java Queue 구현 / 자바 큐 구현 (0) | 2021.02.04 |
| [Interface-초급] Java Interface란? / 자바 인터페이스란? (0) | 2021.01.16 |
| [클래스] Java Abstract Class / 자바 추상 클래스 (0) | 2020.12.31 |
| [자료구조] Java Stack 구현 / 자바 스택 구현 (0) | 2020.12.29 |