S E P H ' S
[자료구조] 1. ArrayList 본문
ArrayList
- ArrayList는 다른 자료구조와 달리 Object[] 배열, 즉 객체 배열을 두고 사용한다.
- 모든 자료구조는 '동적 할당'을 전제로 한다. 동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적 배열을 선언하는 것과 차이가 없다.
- 데이터의 개수를 알 수 없는데 배열을 쓰고 싶을 때 ArrayList, LinkedList 등의 자료구조를 선택한다.
- 데이터 사이에 빈 공간을 허락하지 않는다. 항상 리스트 계열 자료구조는 데이터들이 '연속적'이어야 한다.
ArrayList 구현
<필수 목록>
- 클래스 및 생성자 구성
- resize 메소드 구현
- add 메소드 구현
- get, set, indexOf, contains 메소드 구현
- remove 메소드 구현
- size, isEmpty, clear 메소드 구현
<부가 목록>
- clone, toArray 구현
<필수 목록>
클래스 및 생성자 구성
ArrayList 이름으로 생성한 뒤 List 인터페이스를 implements 한다.
public class ArrayList<E> implements List<E> {
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 크기
private static final Object[] EMPTY_ARRAY = {};
private int size; // 요소 개수
Object[] array; // 요소를 담을 배열
// 생성자 (초기 공간 할당 X)
public ArrayList() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
// 생성자 (초기 공간 할당 O)
public ArrayList(int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
}
DEFAULT_CAPACITY : 배열이 생성될 때 최소 할당 크기이자 최소 할당 용적 변수로 기본값은 10으로 설정하였다.
EMPTY_ARRAY : 아무것도 없는 빈 배열
size : 배열에 담긴 요소 개수
array : 요소들을 담을 배열
생성자를 두 개를 두었는데 두 생성자의 차이점은 첫번째 생성자는 사용자가 공간 할당을 안하고 객체만 생성하고 싶을 때, array 변수를 EMPTY_ARRAY로 초기화 시켜둔다.
ArrayList<Integer> list = new ArrayList<>();
두번째 생성자는 사용자가 데이터의 개수를 예측할 수 있어서 미리 공간 할당을 하고 싶을 경우에 사용한다. array의 공간할당을 입력된 수만큼 배열을 만든다. 마찬가지로 size를 0으로 초기화 시켜둔다. size는 요소의 개수를 의미한다. 공간을 할당하는 것과는 다른 개념이다.
ArrayList<Integer> list = new ArrayList<>(100);
동적 할당을 위한 resize 메소드 구현
동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적 배열을 선언하는 것과 차이가 없다고 했다. 데이터는 작은데 할당한 크기가 크다면 메모리가 낭비가 되고, 반대로 데이터가 많으면 넘치는 데이터를 담을 수 없는 상황이 발생할 수 있다.
그렇기 대문에 size(요소의 개수)가 capacity(용량)에 얼마만큼 있는지를 확인하고, 적절한 크기에 맞게 배열의 capacity를 변경해야 한다. 또한 용량은 외부에서 마음대로 접근하면 데이터의 손상을 야기할 수 있기 때문에 private로 접근을 제한한다.
private void resize() {
int array_capacity = array.length;
// 조건문 1 : 만일 array의 용량이 0이면
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_CAPACITY];
return;
}
// 조건문 2 : 용량이 가득 찼을 경우
if (size == array_capacity) {
int new_capacity = array_capacity * 2;
// copy
array = Arrays.copyOf(array, new_capacity);
return;
}
// 조건문 3 : 용량의 절반 미만으로 요소가 차지하고 있을 경우
if (size < (array_capacity / 2)) {
int new_capacity = array_capacity / 2;
// copy
array = Arrays.copyOf(array, Math.max(new_capacity, DEFAULT_CAPACITY));
}
}
현재 array의 용량(array의 길이)과 데이터의 개수(size)를 비교한다.
조건문 1
생성자에게 사용자가 용량을 별도로 할당하지 않은 경우 EMPTY_ARRAY로 초기화되어 있다면 용량이 0인 상태이다. 이 경우를 고려하여 새로 array의 용량을 할당하기 위해 최소 용량으로 설정해뒀던 DEFAULT_CAPACITY의 크기만큼 배열을 생성하고 메소드를 종료한다.
또한 주소가 아닌 '값'을 비교해야 하기 때문에 Arrays.equals() 메소드를 사용한다.
조건문 2
데이터가 가득 찼을 경우는 데이터(요소)를 더 받아오기 위해 용량을 늘려야 한다. 데이터의 개수가 용량과 같다는 것은 배열이 가득 찼다는 것을 의미한다. 이때 현재 용량의 2배로 설정한다.
또한 기존에 있던 요소들을 새로 복사해와야 한다. Arrays.copyOf() 메소드를 사용한다. Arrays.copyOf() 메소드는 첫 번째 파라미터로 복사할 배열을 넣어주고 두 번째 파라미터는 용량의 크기를 넣어주면 된다. 만약 복사할 배열보다 용량의 크기가 클 경우 먼저 배열을 복사하고, 나머지 빈 공간은 null로 채운다.
조건문 3
데이터의 양이 용량의 절반에 미치지 못했을 경우이다. 이 경우 빈 공간이 메모리를 차지하고 있기 때문에 낭비가 되는 상황이다. 따라서 새로운 용량을 현재 용량의 절반으로 설정하고 조건문 2의 방법과 같이 Arrays.copyOf()를 사용하여 새로운 용량 크기를 갖는 배열을 만들어 준다. 만약 복사할 배열보다 용량의 크기가 작을 경우에는 새로운 용량까지만 복사하고 반환하기 때문에 예외 발생에 대해 안전하다.
add 메소드 구현
add 메소드는 크게 3가지로 분류가 된다.
- 가장 마지막에 추가 (기본값) - addLast(E value)
- 가장 앞부분에 추가 - addFirst(E value)
- 특정 위치에 추가 - add(int index, E value)
현재 자바에 내장되어 있는 ArrayList에서는 addLast()역할을 add() 메소드가 하고, 특정 위치에 추가는 add(int index, E element)로 오버로딩된 메소드가 하고 addFirst()는 없다.
1. 기본 삽입 : add(E value) && addLast(E value) 메소드
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
// 꽉 차있으면 용량 재할당
if (size == array.length) {
resize();
}
array[size] = value; // 마지막 위치에 요소 추가
size++; // 용량 1 증가
}
2. 중간 삽입 : add(int index, E value)
우선 index가 범위를 벗어나진 않는지 먼저 확인하고, 중간에 삽입할 경우 기존에 있던 index의 요소와 그의 뒤에 있는 데이터들을 모두 한 칸씩 뒤로 밀어야 한다. 따라서 addLast와는 다르게 중간 삽입은 데이터를 미루는 코드가 추가된다.
@Override
public void add(int index, E value) {
if (index > size || index < 0) { // 범위를 벗어나는지 먼저 확인
throw new IndexOutOfBoundsException();
}
if (index == size) { // index가 마지막 위치면 addLast 메소드로 요소 추가
addLast(value);
} else {
if (size == array.length) { // 꽉 차있으면 용량 재설정
resize();
}
// index 기준 뒤에 있는 요소들을 뒤로 미루는 코드
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = value;
size++;
}
}
먼저 index로 들어오는 값이 size를 벗어나지 않는지(List는 빈 공간을 허락하지 않는다 !!!) 혹은 음수가 들어오는지를 확인한다. 만약 범위를 벗어난다면 예외를 발생시키도록 한다.
그리고 size와 index가 같다면 마지막에 추가시키는 것과 같으므로 구현해둔 addLast 메소드를 활용한다.
그 외의 경우가 이제 중간에 삽입되는 경우인데 먼저 요소의 개수가 배열의 길이와 같다면(꽉 차있다는 것) resize() 메소드를 통해 용량을 재설정한다. 그 다음, index 기준으로 뒤에 있는 요소들을 한칸씩 뒤로 미루고 나서 해당 index에 value를 삽입한다. 그리고 나서 size를 증가시킨다.
3. addFirst(E value)
public void addFirst(E value) {
add(0, value);
}
어차피 가장 맨 앞에 넣는 것이라면 나머지 모든 기존의 요소들을 뒤로 미뤄야한다. add 메소드를 활용해 0 index에 value를 넣어주면 된다.
get, set, indexOf, contains 메소드 구현
remove() 메소드에서 유사한 동작을 필요로 하기 때문에 먼저 이 메소드들부터 구현한다.
1. get(int index) 메소드
반드시 잘못된 위치 참조에 대한 예외처리를 해야한다.
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// Object 타입에서 E 타입으로 캐스팅 후 반환
return (E) array[index];
}
@SuppressWarnings("unchecked")란?
이것을 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다. 반환되는 것을 보면 E 타입으로 캐스팅을 하고 있고 그 대상은 Object[] 배열의 Object 데이터이다. 이 과정에서 변환할 수 없는 가능성이 있다고 보고 경고로 메소드 옆에 경고 표시가 뜨는데, add 하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재한다.
그렇기 때문에 형 안전성이 보장된다. ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 말이다. 물론 이것은 남발하면 안되고 형 변환시에 예외 가능성이 없을 확실한 경우에만 최소한의 범위에 사용하는 것이 좋다. 그렇지 않다면 경고 메세지를 놓칠 수 있기 때문이다.
2. set(int index, E value) 메소드
set 메소드는 index에 위치한 데이터를 새로운 데이터로 교체하는 것이다. add는 추가이지만 set은 교체이다.
index로 참조하는 모든 메소드들은 IndexOutOfBoundsException을 반드시 검사해야한다.
@Override
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
array[index] = value;
}
}
3. indexOf(Object value) 메소드
indexOf 메소드는 사용자가 찾고자 하는 요소의 위치를 반환한다.
만약 찾고자 하는 요소가 중복된다면? 가장 먼저 마주치는 요소의 인덱스를 반환한다. (실제 자바의 indexOf 또한 이렇게 작동한다.)
찾고자하는 요소가 없다면 -1을 반환한다.
그리고 객체끼리 비교할때는 equals로 비교해야 한다. 객체끼리 비교할 때 동등 연산자를 사용하게 되면 주소를 비교하기 때문에 주의해야 한다.
@Override
public int indexOf(Object value) {
int i = 0;
for (i = 0; i < size; i++) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
3 - 1. LastIndexOf(Object value) 메소드
indexOf와는 다르게 반대로 거꾸로 탐색하는 과정의 메소드이다. 사용자가 찾고자 하는 인덱스가 뒤 쪽이라고 예상가능하다면 굳이 앞쪽에서 부터 탐색할 필요가 없다. 또한 Stack에서 사용할 때 유용하게 쓰인다.
public int lastIndexOf(Object value) {
for (int i = size; i >= 0; i--) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
4. contains(Object value) 메소드
indexOf가 사용자가 찾고자 하는 요소의 위치를 반환했다면 contains는 사용자가 찾고자 하는 요소가 List에 존재하는지의 여부를 반환한다. indexOf 메소드를 활용해 0 이상이라면 요소가 존재한다는 뜻이므로 true를 반환하고 그렇지 않다면 false를 반환하도록 한다.
@Override
public boolean contains(Object value) {
return indexOf(value) >= 0;
}
remove 메소드 구현
remove 메소드가 가장 에러가 많이 나고 어려운 구현이다. remove 메소드는 크게 두 가지로 나눌 수 있다.
- 특정 index의 요소를 삭제 - remove(int index)
- 특정 요소를 삭제 - remove(Object value)
자바에 내장되어 있는 ArrayList도 remove()는 없다. remove(int index)와 remove(Object value)만 존재한다. 하지만 이후에 다룰 Stack, LinkedList, Queue의 다양한 자료구조에서는 존재한다.
만약 remove() 기능을 넣어 가장 앞 또는 뒤 요소를 제거하는 기능을 넣고 싶다면 remove(int index)를 활용하여 파라미터로 0 혹은 size - 1를 넘겨주면 된다.
1. remove(int index) 메소드
add 메소드가 index 위치 다음의 요소들을 다음으로 미루고 index 위치에 값을 넣었다면 remove는 역순이다. (해체는 조립의 역순,,,)
삭제되면서 데이터가 일정 이상 비워졌다면 resize()를 통해 용량을 조정해준다.
@SuppressWarnings("unchecked")
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E element = (E) array[index]; // 삭제될 요소를 임시로 담아줌
array[index] = null;
// 삭제한 요소의 뒤에 있는 요소들을 한 칸씩 당겨온다.
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
array[i + 1] = null;
}
size--;
resize();
return element;
}
Object 타입을 E 타입으로 캐스팅하면서 경고창이 뜬다. get메소드처럼 E 타입 외에 들어오는 것이 없기 때문에 @SuppressWarning을 사용한다.
마지막 원소의 인덱스는 size - 1이다. 그렇게 때문에 범위 체크, 이후 배열 요소들을 한 칸씩 당겨올 때 시작점, 끝 점을 잘 생각하며 참조해야 한다. 그리고 명시적으로 요소를 null 처리를 해주어야 GBC(가비지 컬렉터)에 의해 더 이상 쓰지 않는 데이터의 메모리를 수거해주기 때문에 최대한 null 처리를 하는 것이 좋다. (명시적으로 안해도 크게 문제는 없으나 가비지 컬렉터가 쓰지 않는 데이터라도 나중에 참조될 가능성이 있는 데이터로 볼 가능성이 높아진다. 이는 결국 메모리를 많이 잡아먹을 수 있는 가능성이 있다. 결과적으로 프로그램 성능에도 영향을 미친다.)
2. remove(Object value) 메소드
이 메소드는 사용자가 원하는 특정 요소(value)를 리스트에서 찾아 삭제하는 것이다. indexOf 메소드와 같이 리스트안에 특정 요소와 매칭되는 요소가 여러개일 경우, 가장 먼저 마주하는 요소를 삭제한다.
그렇다면 필요한 동작은 value와 같은 요소가 존재하는지, 몇번째 위치에 존재하는지 확인하는 동작 하나. 그 위치(index)에 위치하는 데이터를 지우고 나머지 뒤의 요소들을 하나씩 당기는 것. 이러한 두가지 동작이 필요하다.
리스트에 특정 요소와 같은 요소의 index를 찾는 작업은 indexOf 메소드로,
index를 통해 삭제하는 작업은 remove(int index)메소드를 활용하면 된다.
@Override
public boolean remove(Object value) {
int index = indexOf(value);
// 만일 index 가 -1이라면 요소가 없다는 것이므로 false 반환
if (index == -1) {
return false;
}
// index 를 활용해 요소 삭제
remove(index);
return true;
}
size, isEmpty, clear 메소드 구현
1. size() 메소드
ArrayList가 동적으로 할당 되면서 요소의 삽입, 삭제가 많아진다면 사용자가 리스트의 요소개 몇 개인지 기억하기 힘들다. 더군다나 size 변수는 private 접근 제한자를 갖고 있기 때문에 외부에서 직접 참조할 수 없다. (외부에서 접근한다면 고의적으로 변경할 수 있기 때문이다.) 그래서 size 변수의 값을 반환해줄 메소드가 필요하다.
@Override
public int size() {
return size;
}
2. isEmpty() 메소드
size는 요소의 개수를 의미하는 것이니 size 메소드를 활용하여 size가 0이라면 빈 것이므로 true, 아니라면 false를 반환하도록 한다.
@Override
public boolean isEmpty() {
return size() == 0;
}
3. clear() 메소드
모든 요소들을 비워버리는 작업이다. size도 0으로 초기화해주어야 한다. 배열의 용량 또한 절반으로 줄일 수 있도록 한다.
배열의 용량을 절반으로 줄이는 이유는 다음과 같다. 배열의 용량의 사이즈를 조절하는 resize 메소드에서는 현재 배열의 용량의 두배를 새로운 용량으로 주거나 현재 배열의 용량의 절반을 새로운 용량으로 주거나 하는 등, 데이터의 양에 따라서 적절하게 조절한다.
clear 메소드는 필요에 의해 초기화 하는 것을 목적으로 하고 있다. 그렇다면 새로 이 리스트에 들어올 데이터 또한 현재 용량에 근접할 가능성이 높다. 그렇게 때문에 일단 절반으로만 줄이도록 한다.
@Override
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
resize();
}모든 배열을 명시적으로 null 처리한다.
<부가 목록>
clone, toArray 메소드 구현
이 메소드들은 추가해주면 좋을 메소드들이지만 굳이 중요한 부분은 아니다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 만드는 것, toArray는 리스트를 출력할 때 for-each문을 쓰기 위해 만들어보았다.
원래는 Iterable을 implements하여 구현하면 된다.
1. clone() 메소드
사용자가 사용하고 있던 ArrayLisy를 복제하고 싶을 때 쓰는 메소드이다. 단순히 연산자를 통해 복사한다면 객체의 '주소'를 복사하는 것이기 때문에 원본 객체에도 영향을 끼치게 된다. (얕은 복사, shallow copy)
이를 방지하기 위해 깊은 복사를 하게 되는데, 이 때 필요한 것이 clone()이다. Object에 있는 메소드이지만 접근 제어자가 protected로 되어 있어 사용자 클래스의 경우 Cloneable 인터페이스를 implement 해야 한다.
즉, public class ArrayList<E> implements List<E>에 Cloneable도 추가해야 한다.
@Override
public Object clone() throws CloneNotSupportedException {
// 새로운 객체 생성
ArrayList<?> cloneList = (ArrayList<?>) super.clone();
// 새로운 객체의 배열도 생성해주어야 한다. (객체는 얕은 복사가 되기 때문)
cloneList.array = new Object[size];
// 배열의 값을 복사
System.arraycopy(array, 0, cloneList.array, 0, size);
return cloneList;
}
객체는 얕은 복사가 된다는 것을 생각하고 배열의 값까지 복사를 해주어야 완전히 깊은 복사가 가능하다.
2. toArray() 메소드
toArray() 메소드는 크게 두 가지가 있다.
하나는 아무런 인자 없이 현재 있는 ArrayList의 리스트를 객체배열(Object[])로 반환 해주는 Object[] toArray() 메소드, 다른 하나는 ArrayList를 이미 생성된 다른 배열에 복사해주고자 하는 T[] toArray(T[] a) 메소드가 있다.
ArrayList<Integer> list = new ArrayList<>();
Object[] array1 = list.toArray();
Integer[] array2 = new Integer[10];
array2 = list.toArray(array2);
1번의 장점은 ArrayList에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점.
2번의 장점은 객체 클래스로 상속관계에 있는 타입이거나 Wrapper 클래스(Integer -> int)와 같이 데이터 타입을 유연하게 캐스팅할 수 있다. 또한 리스트에 원소 5개가 있고 array2 배열에 10개의 원소가 있다면 array2 배열의 0~4 index에 리스트에 있던 원소가 복사되고 그 외의 원소는 기존 array2 배열에 초기화 되었던 원소가 그대로 남는다.
전체 코드
public class ArrayList<E> implements List<E>, Cloneable {
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 크기
private static final Object[] EMPTY_ARRAY = {};
private int size; // 요소 개수
Object[] array; // 요소를 담을 배열
// 생성자 (초기 공간 할당 X)
public ArrayList() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
// 생성자 (초기 공간 할당 O)
public ArrayList(int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
private void resize() {
int array_capacity = array.length;
// 만일 array의 용량이 0이면
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_CAPACITY];
return;
}
// 용량이 가득 찼을 경우
if (size == array_capacity) {
int new_capacity = array_capacity * 2;
// copy
array = Arrays.copyOf(array, new_capacity);
return;
}
// 용량의 절반 미만으로 요소가 차지하고 있을 경우
if (size < (array_capacity / 2)) {
int new_capacity = array_capacity / 2;
// copy
array = Arrays.copyOf(array, Math.max(new_capacity, DEFAULT_CAPACITY));
}
}
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
// 꽉 차있으면 용량 재할당
if (size == array.length) {
resize();
}
array[size] = value; // 마지막 위치에 요소 추가
size++; // 용량 1 증가
}
public void addFirst(E value) {
add(0, value);
}
@Override
public void add(int index, E value) {
if (index > size || index < 0) { // 범위를 벗어나는지 먼저 확인
throw new IndexOutOfBoundsException();
}
if (index == size) { // index가 마지막 위치면 addLast 메소드로 요소 추가
addLast(value);
} else {
if (size == array.length) { // 꽉 차있으면 용량 재설정
resize();
}
// index 기준 뒤에 있는 요소들을 뒤로 미루는 코드
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = value;
size++;
}
}
@SuppressWarnings("unchecked")
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
E element = (E) array[index]; // 삭제될 요소를 임시로 담아줌
array[index] = null;
// 삭제한 요소의 뒤에 있는 요소들을 한 칸씩 당겨온다.
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
array[i + 1] = null;
}
size--;
resize();
return element;
}
@Override
public boolean remove(Object value) {
int index = indexOf(value);
// 만일 index 가 -1이라면 요소가 없다는 것이므로 false 반환
if (index == -1) {
return false;
}
// index 를 활용해 요소 삭제
remove(index);
return true;
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// Object 타입에서 E 타입으로 캐스팅 후 반환
return (E) array[index];
}
@Override
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
array[index] = value;
}
}
@Override
public boolean contains(Object value) {
return indexOf(value) >= 0;
}
@Override
public int indexOf(Object value) {
int i = 0;
for (i = 0; i < size; i++) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
public int lastIndexOf(Object value) {
for (int i = size; i >= 0; i--) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
resize();
}
@Override
public Object clone() throws CloneNotSupportedException {
// 새로운 객체 생성
ArrayList<?> cloneList = (ArrayList<?>) super.clone();
// 새로운 객체의 배열도 생성해주어야 한다. (객체는 얕은 복사가 되기 때문)
cloneList.array = new Object[size];
// 배열의 값을 복사
System.arraycopy(array, 0, cloneList.array, 0, size);
return cloneList;
}
public Object[] toArray() {
return Arrays.copyOf(array, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
// copyOf(원본 배열, 복사할 길이, Class<? extends T[]> 타입)
return (T[]) Arrays.copyOf(array, size, a.getClass());
}
// 원본 배열, 원본 배열 시작위치, 복사할 배열, 복사할 배열 시작위치, 복사할 요소 수
System.arraycopy(array, 0, a, 0, size);
return a;
}
}정리
ArrayList에 대한 기본적인 메소드를 구현해봤다.
index를 통해 요소에 접근하는 것은 빠르지만, 중간 삽입, 삭제의 경우에는 후자의 요소들을 밀거나 당겨야하기 때문에 비효율적이라는 것이 명확하게 드러났다.
다음은 ArrayList와 앞으로 구현할 LinkedList의 각 메소드별 시간 복잡도이다.
| 작업 | 메소드 | ArrayList | LinkedList |
| add at last index | add() | O(1) | O(1) |
| add at given index | add(index, value) | O(N) | O(1) |
| remove by index | remove(index) | O(N) | O(1) |
| remove by value | remove(value) | O(N) | O(1) |
| get by index | get(index) | O(1) | O(N) |
| search by value | indexOf(value) | O(N) | O(N) |
표를 보고 보이는 가장 큰 차이점은 중간 삽입, 삭제는 느리고 검색에는 빠른 ArrayList와는 달리 LinkedList는 중간 삽입, 삭제가 빠르고 검색이 느리다는 것을 볼 수 있다.
'Programing & Coding > Data Structure' 카테고리의 다른 글
| [자료구조] 5. 스택(Stack) 구현 (0) | 2023.03.27 |
|---|---|
| [자료구조] 4. Java 스택 인터페이스 (Stack Interface) (0) | 2023.03.27 |
| [자료구조] 3. Doubly LinkedList (0) | 2023.03.24 |
| [자료구조] 2. Singly LinkedList (0) | 2023.03.24 |
| [자료구조] 0. Java 리스트 인터페이스 (List Interface) (0) | 2023.03.23 |
