- 배열의 경우 다음 2가지 불편함이 있음
- 배열의 길이를 동적으로 변경할 수 없음
- 데이터를 추가하기 불편함
- 데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 밀어야함
- 배열의 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료구조를 List라고 함
리스트 자료 구조
- 순서가 있고, 중복을 허용하는 자료구조를 리스트라고 함
- 일반적으로 배열과 리스트는 구분해서 이야기함
- 리스트는 배열보다 유연한 자료구조로, 크기가 동적으로 변할 수 있음
- 배열 : 순서가 있고 중복을 허용하지만 크기가 정적으로 고정됨
- 리스트 : 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있음
- 참고로 Set이라는 자료구조의 경우 중복을 허용하지 않음
1. 정적 배열
- 배열의 활용해서 리스트 자료구조를 만들기
- 먼저 정적인 배열을 그대로 사용하여 구현
package collection.array;
import java.util.Arrays;
public class MyArrayListV1 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV1() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV1(int initialCapacity) {
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(Object e) {
elementData[size] = e;
size++;
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = get(index);
elementData[index] = element;
return oldValue;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
size + ", capacity=" + elementData.length;
}
}Object[] elementData: 다양한 타입의 데이터를 보관하기 위해 Object 배열을 사용함DEFAULT_CAPACITY: 리스트(MyArrayListV1)를 생성할 때 사용하는 기본 배열의 크기- 배열의 크기를 다르게 만들고 싶으면
MyArryListV1(int initialCapacity)생성자를 사용하면 됨
- 배열의 크기를 다르게 만들고 싶으면
size: 리스트 크기- 배열의 크기를 뜻하는
capacity와 다름 - 예를 들어서 배열의 크기가 5인데, 입력된 데이터가 하나도 없으면
size는 0이 됨
- 배열의 크기를 뜻하는
add(Object e): 리스트에 데이터를 추가함get(index): 인덱스에 있는 항목 조회set(index, element): 인덱스에 있는 항목 변경indexOf(Ojbect o): 검색 기능- 리스트를 순차 탐색해서 인수와 같은 데이터가 있는 인덱스의 위치를 반환함
- 데이터가 없으면
-1을 반환함
Arrys.copyOf(elementData, size):size크기의 배열을 새로 만듦- 여기서는
toString()출력시size이후의 의미없는 값을 출력하지 않기 위해 사용함
- 여기서는
package collection.array;
public class MyArrayListV1Main {
public static void main(String[] args) {
MyArrayListV1 list = new MyArrayListV1();
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);
System.out.println("==기능 사용==");
System.out.println("list.size(): " + list.size());
System.out.println("list.get(1): " + list.get(1));
System.out.println("list.indexOf('c'): " + list.indexOf("c"));
System.out.println("list.set(2, 'z'), oldValue: " + list.set(2, "z"));
System.out.println(list);
System.out.println("==범위 초과==");
list.add("d");
System.out.println(list);
list.add("e");
System.out.println(list);
//범위 초과, capacity가 늘어나지 않으면 예외 발생
list.add("f");
System.out.println(list);
}
}실행결과
==데이터 추가==
[] size=0, capacity=5
[a] size=1, capacity=5
[a, b] size=2, capacity=5
[a, b, c] size=3, capacity=5
==기능 사용==
list.size(): 3
list.get(1): b
list.indexOf('c'): 2
list.set(2, 'z'), oldValue: c
[a, b, z] size=3, capacity=5
==범위 초과==
[a, b, z, d] size=4, capacity=5
[a, b, z, d, e] size=5, capacity=5
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out
of bounds for length 5
at collection.array.MyArrayListV1.add(MyArrayListV1.java:25)
at collection.array.MyArrayListV1Main.main(MyArrayListV1Main.java:30)
list.add("a")[a] size=1, capacity=5- 리스트의 사이즈는 실제 데이터가 입력된 크기
- 배열의 크기와는 무관함
-
size가 배열의 크기인capacity에 도달하면 더는 데이터를 추가할 수 없음 -
따라서 f값을 입력할 때 예외가 발생함
-
동적으로 저장할 수 있는 크기가 커지는 상황은 아니기 때문에, 데이터의 크기가 동적으로 변할 수 있도록 코드를 변경해야함
2. 동적 배열
```java
package collection.array;
import java.util.Arrays;
public class MyArrayListV2 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV2() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV2(int initialCapacity) {
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(Object e) {
//코드 추가
if (size == elementData.length) {
grow();
}
elementData[size] = e;
size++;
}
//코드 추가
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = get(index);
elementData[index] = element;
return oldValue;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
size + ", capacity=" + elementData.length;
}
}-
추가된 부분은
grow()메서드와 이 메서드를 호출하는add()메서드 -
add()메서드에서 데이터를 추가할 때size가 배열의 크기에 도달했다면 더는 데이터를 추가할 수 없음 -
따라서 이때는
grow()를 호출해서 기존 배열을 복사한 새로운 배열을 만들고 배열의 크기도 여유있게 2배로 늘려줌Arrays.copyOf(기존배열, 새로운 길이): 새로운 길이로 배열을 생성하고 기존 배열의 값을 새로운 배열에 복사함
package collection.array;
public class MyArrayListV2Main {
public static void main(String[] args) {
MyArrayListV2 list = new MyArrayListV2(2);
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("d");
System.out.println(list);
list.add("e");
System.out.println(list);
list.add("f");
System.out.println(list);
}
}실행결과
[] size=0, capacity=2
[a] size=1, capacity=2
[a, b] size=2, capacity=2
[a, b, c] size=3, capacity=4
[a, b, c, d] size=4, capacity=4
[a, b, c, d, e] size=5, capacity=8
[a, b, c, d, e, f] size=6, capacity=8배열의 크기를 초과할 때
- (1) 데이터를 추가하면
size가 배열의 크기인 capacity를 초과하게 됨 - (2) 이때
grow()메서드를 호출하는데, 이 메서드는 다음과 같은 역할을 수행함- (2) 2배 큰 배열을 새로 생성한다.
- (3) 새로운 배열에 기존 배열의 값을 복사한다.
Arrays.copyOf(기존배열, 새로운길이)를 사용해서 2배 큰 배열을 새로 생성하면서 동시에 새로운 배열에 기존 배열의 값을 복사함- (4) 참조값을 변경함
- 이렇게 되면 내부 데이터를 보관하는
elementData는 기존보다 2배 큰capacity를 가진 배열을 보유하게 됨 - (5) 이렇게 증가된 배열에 데이터를 추가하면 됨
- 기존 배열(
x001)은 더는 참고하는 곳이 없으므로GC의 대상이 됨
grow()를 호출할 때 배열의 크기는 기존과 비교해서 2배씩 증가함
-
예)
2-> 4-> 8 -> 16 -> 32 -> 64 -> 128 -
데이터가 하나 추가될 때마다 배열의 크기를 1씩만 증가하게 되면 배열의 복사하는 연산이 너무 자주 발생할 가능성이 높음
-
배열을 새로 복사해서 만드는 연산은 배열을 새로 만들고 또 기존 데이터를 복사하는 시간이 걸리므로 가능한 줄이는 것이 좋음
- 이렇게 2배씩 증가하면 배열을 새로 만들고 복사하는 연산을 줄일 수 있음
- 반면에 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지는 단점이 발생할 수 있음
-
참고로 예제0를 단순히 하기 위해 여기서는 2배씩 증가를 했지만, 보통 50% 정도 증가하는 방법을 사용함
정리
MyArrayListV2는 정적인 배열과 다르게 크기가 동적으로 변하는 자료구조- 따라서 데이터의 크기를 미리 정하지 않아도 됨
- 물론
MyArrayListV2내부에서는 배열을 사용하지만,MyArrayListV2를 사용하는 개발자는 이런 부분을 신경쓰지 않아도 됨
Backend development