Java List - 직접 구현해보기 1

일반 배열의 경우 불편한 사항이 있고, 자신이 직접 구현하는 부분이 있다.

배열 길이를 동적으로 변경 불가능
데이터 추가 시 기존 데이터 유지되지 않음

배열의 불편함을 해소하고 데이터를 추가하는 자료 구조를 List(리스트)로 부른다.

List 자료 구조

순서가 있으며, 중복을 허용하는 자료구조를 리스트라 한다.

일반 배열과 리스트는 구번되어 이야기된다. 리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변한다.

배열
- 일련의 순서로 데이터 나열
- 중복 데이터 허용
- 크기가 정적으로 고정
리스트
- 일련의 순서로 데이터 나열
- 중복 데이터 허용
- 크기가 동적으로 변함

중복 데이터 허용은 같은 데이터를 두 번 넣을 수 있다. arr[0] = 1; arr[1] = 1; 코드로 중복 데이터를 허용한다.

자료 구조 중 중복 데이터를 허용하지 않는 Set 자료구조가 있다.

리스트 직접 구현 - CList

배열을 활용한 단순하고 간단한 코드로 구현한다.
추후에는 점진적으로 발전해 개선할 것임으로 단순한 구조로 만든다.

먼저 배열을 그대로 사용해 진행

CList

import java.util.Arrays;

public class CList {

    ...

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

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

    ...
}

CList 멤버 필드

private static final int DEFAULT_CAPACITY = 10;
private Object[] elementData;
private int size = 0;

DEFAULT_CAPACITY 리스트를 생성 시 지정된 기본 배열 전체 크기
- 배열을 다르게 주고 싶은 경우 CList(int initialCapacity) 생성자로 사용한다.
Object[] elementData 다양한 타입 보관하기 위해 Object 배열 사용
size 추가된 데이터마다 달라지는 리스트의 현재 크기를 나타내는 size 숫자형

size

public int size() {
    return size;
}

배열의 현재 사이즈를 반환한다.

add

public void add(Object e) {
    elementData[size] = e;
    size++;
}

인자의 Object 형으로 내부 배열로 저장한다.
배열의 사이즈를 증가시킨다.

get

public Object get(int index) {
    return elementData[index];
}

배열에 들어있는 인덱스의 값을 반환한다.

set

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

배열의 인덱스에서 값을 수정한다.
get 메소드로 값을 꺼내와 oldValue 변수로 바인딩하고 반환한다.

indexOf

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

배열 내부에 값이 있는지 찾는다.
- 인덱스 값으로 반환
없는 경우 -1 반환

toString

public String toString() {
    // [1,2,3,null,null]
    // capacity5, size3 인 경우 할당되지 않는 배열로 오류가 발생한다.
    // Arrays.copyOf 활용해 size 만큼만 출력하도록 한다.
    // [1,2,3]... 반환
    return Arrays.toString(Arrays.copyOf(elementData, size)) +
            ", size = " +
            size +
            ", capacity = " +
            elementData.length;
}

배열의 전체 값을 꺼내온다.

Main.class

CList list = new CList();
System.out.println("** 데이터 추가하기 **");
System.out.println(list);
list.add("a");
System.out.println(list);
list.add("b");
System.out.println(list);
list.add("c");
System.out.println(list);
list.add("c");
System.out.println(list);

System.out.println("** 메소드 기능 사용하기 **");
System.out.println("list.size() = " + list.size());
System.out.println("list.get(2) = " + list.get(2));
System.out.println("list.indexOf('c') = " + list.indexOf('c'));
System.out.println("list.set(2, 'z') = " + list.set(2, 'z'));
System.out.println("== 범위초과 ==");
list.add("d");
list.add("k");
list.add("k");
list.add("k");
list.add("k");
list.add("i");
System.out.println(list);

System.out.println("Crash");
list.add("i");

** 데이터 추가하기 **
[], size = 0, capacity = 10
[a], size = 1, capacity = 10
[a, b], size = 2, capacity = 10
[a, b, c], size = 3, capacity = 10
[a, b, c, c], size = 4, capacity = 10
** 메소드 기능 사용하기 **
list.size() = 4
list.get(2) = c
list.indexOf('c') = -1
list.set(2, 'z') = c
== 범위초과 ==
[a, b, z, c, d, k, k, k, k, i], size = 10, capacity = 10
Crash
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
at CList.add(CList.java:23)
at Main.main(Main.java:30)

마지막에 오류가 출력한다. add 하였을 때 배열의 크기를 넘는 인덱스에 데이터를 넣는 경우 오류 아웃 오브 바운드(밖에 있는 인덱스를 참조했다.) 오류가 발생한다.

capacity 10 넘어 참조하면 오류가 발생한다.

capacity 10 = array[0]~[9]
0                                       9
+---+---+---+---+---+---+---+---+---+---+---+---+
| a | b | z | c | d | k | k | k | k | i | i | ? |
+---+---+---+---+---+---+---+---+---+---+---+---+
                                              ↑
                                             "i"

동적 배열을 추가해 보완하도록 한다.