자바 배열과 배열 리스트(Array List)

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

 

이제 컬렉션 프레임 워크로 들어왔다.

 

컬렉션 프레임 워크를 마치게 된다면, 다음 강의는 실전 자바 고급 편이다.

 

이름에 고급이 들어가니 익히고 나면 고수가 될 것 같은 느낌이 들어 얼른 배우고 싶다.

 

배열을 메모리 관점에서 알아보자.

 

자바의 배열은 정적 크기를 갖고 있다.

 

한번 선언되면, 힙영역에 해당 크기만큼 할당되며, 메모리 주소는 연속된다.

 

int[] array = new int[5];

위와 같이 배열을 선언하였다.

 

array의 주소가 x001라고 가정해 보자.

 

그렇다면 array [0]의 주솟값 또한 x001로 같을 것이고 array [1]의 주솟값은 int타입이 4byte이기에, x005로 될 것이다.

 

그렇다면 배열에 인덱스로 접근하는 것은 굉장히 빠를 것이라는 것을 유추할 수 있다.

 

왜냐하면 굳이 탐색을 하지 않아도, 인덱스와 타입의 크기만 알면 바로 해당 인덱스의 주솟값을 구할 수 있기 때문이다.

 

따라서 배열의 인덱스 접근 시간 복잡도는 O(1)이다.

 

여기까지만 보고

 

이제 배열 리스트에 대해 알아보자.

 

사실 배열이랑 크게 다를 바가 없다.

 

배열리스트의 구현도 배열로 되어있기 때문이다.

 

배열 + 기능(메서드)을 통해 배열리스트 구현이 가능하다.

 

배열의 단점인 정적 메모리 할당을 가변적으로 크기가 늘릴 수 있게 하여 보완하였다.

 

하지만 이런 배열리스트도 단점이 존재한다.

 

- 메모리 크기를 정확히 알지 못하면 낭비되는 공간이 존재한다.

- 값을 추가하고 삭제하기 번거롭다.

 

배열리스트의 단점은 Linked List를 통해 해결할 수 있다.

(물론 Linked List도 단점이 있다.)

 

추가적으로 Array List에 제네릭을 도입하면 타입 안전성 또한 챙길 수 있다.

 

왜냐하면 Array가 Object 타입으로 받으니(코드 보면 됨), 타입을 정해주지 않으면, String, int 등 각종 타입들이 무작위로 들어갈 수 있다.

 

코드를 통해 알아보자.

 

Array List 구현

package middle2.collection.array;

import java.util.Arrays;

public class MyArrayListV4<E> {

    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;
    private int size = 0;

    public MyArrayListV4() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayListV4(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++;
    }

    public void add(int index, E e) {
        if (size == elementData.length) {
            grow();
        }
        shiftRightFrom(index);
        elementData[index] = e;
        size++;
    }

    //요소의 마지막부터 index까지 오른쪽으로 밀기
    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elementData[index];
    }

    public E set(int index, E element) {
        E oldValue = get(index);
        elementData[index] = element;
        return oldValue;
    }

    public E remove(int index) {
        E oldValue = get(index);
        shiftLeftFrom(index);

        size--;
        elementData[size] = null;
        return oldValue;
    }

    //요소의 index부터 마지막까지 왼쪽으로 밀기
    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }

    public int indexOf(E o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" + size + ", capacity=" + elementData.length;
    }

}

 

 

Main

package middle2.collection.array;

import java.util.Arrays;

/**
 * 배열의 특징
 */
public class ArrayMain2 {

    public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        System.out.println(Arrays.toString(arr));

        //배열의 첫번째 위치에 추가
        //기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 첫번째 위치에 추가
        System.out.println("배열의 첫번째 위치에 3 추가 O(n)");
        int newValue = 3;
        addFirst(arr, newValue);
        System.out.println(Arrays.toString(arr));

        //index 위치에 추가
        //기본 배열의 데이터를 한 칸씩 뒤로 밀고 배열의 index 위치에 추가
        System.out.println("배열의 index(2) 위치에 4 추가 O(n)");
        int index = 2;
        int value = 4;
        addAtIndex(arr, index, value);
        System.out.println(Arrays.toString(arr));

        System.out.println("배열의 마지막 위치에 5 추가 O(1)");
        addLast(arr, 5);
        System.out.println(Arrays.toString(arr));
    }

    private static void addLast(int[] arr, int newValue) {
        arr[arr.length - 1] = newValue;
    }

    private static void addFirst(int[] arr, int newValue) {
        for (int i = arr.length - 1; i > 0; i--) {
            arr[i] = arr[i - 1];
        }
        arr[0] = newValue;
    }

    private static void addAtIndex(int[] arr, int index, int value) {
        for (int i = arr.length - 1; i > index; i--) {
            arr[i] = arr[i - 1];
        }
        arr[index] = value;
    }
}

 

실행결과 

[1, 2, 0, 0, 0]
배열의 첫번째 위치에 3 추가 O(n)
        [3, 1, 2, 0, 0]
배열의 index(2) 위치에 4 추가 O(n)
        [3, 1, 4, 2, 0]
배열의 마지막 위치에 5 추가 O(1)
        [3, 1, 4, 2, 5]

 

Array List Class의 구현은 필요한 기능을 메서드로 쪼개서 구현하였다.

 

그렇다면 어떠한 메서드가 구현되어 있는지 알아보자.

 

size() // 현재 배열의 사이즈를 반환한다.

add(data) // 배열에 data추가

add(index, data) // 배열의 index위치에 data추가

shiftRightFrom(index) // 배열의 마지막부터 index까지 오른쪽으로 밀기 -> 리스트 중간 데이터 삽입 때 사용

shiftLeftFrom(index) // 배열의 index부터 마지막까지 왼쪽으로 밀기 -> 마지막 데이터가 아닌, 나머지 데이터 삭제 때 사용

get(index) // index 값 반환

set(index, data) // index위치 데이터 data로 수정

remove(index) // index위치 데이터 삭제 후 반환

indexOf(data) // 리스트에서 data의 위치 반환, 없으면 -1

grow() // 리스트의 크기 추가 할당 

 

위와 같은 기능을 구현하면 ArrayList를 사용할 수 있다.

 

물론 collection에서 ArrayList를 기본으로 제공해 준다.

 

다음에는 Linked List에 대해 알아보자.