ArrayList
Object[] 객체 배열을 사용하는 자료구조로 사이즈를 정하지 않고 동적으로 활용할 수 있다.
리스트 계열 자료구조는 데이터 사이에 빈 공간을 허락하지 않는다.
package Interface_form;
/**
*
* 자바 List Interface입니다. <br>
* List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다.
*
* @author st_lab
* @param <E> the type of elements in this list
*
* @version 1.0
*
*/
public interface List<E> {
/**
* 리스트에 요소를 추가합니다.
*
* @param value 리스트에 추가할 요소
* @return 리스트에서 중복을 허용하지 않을 경우에 리스트에 이미 중복되는
* 요소가 있을 경우 {@code false}를 반환하고, 중복되는 원소가
* 없을경우 {@code true}를 반환
*/
boolean add(E value);
/**
* 리스트에 요소를 특정 위치에 추가합니다.
* 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
*
* @param index 리스트에 요소를 추가할 특정 위치 변수
* @param value 리스트에 추가할 요소
*/
void add(int index, E value);
/**
* 리스트의 index 위치에 있는 요소를 삭제합니다.
*
* @param index 리스트에서 삭제 할 위치 변수
* @return 삭제된 요소를 반환
*/
E remove(int index);
/**
* 리스트에서 특정 요소를 삭제합니다. 동일한 요소가
* 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
*
* @param value 리스트에서 삭제할 요소
* @return 리스트에 삭제할 요소가 없거나 삭제에 실패할
* 경우 {@code false}를 반환하고 삭제에 성공할 경우 {@code true}를 반환
*/
boolean remove(Object value);
/**
* 리스트에 있는 특정 위치의 요소를 반환합니다.
*
* @param index 리스트에 접근할 위치 변수
* @return 리스트의 index 위치에 있는 요소 반환
*/
E get(int index);
/**
* 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
*
* @param index 리스트에 접근할 위치 변수
* @param value 새로 대체할 요소 변수
*/
void set(int index, E value);
/**
* 리스트에 특정 요소가 리스트에 있는지 여부를 확인합니다.
*
* @param value 리스트에서 찾을 특정 요소 변수
* @return 리스트에 특정 요소가 존재할 경우 {@code true}, 존재하지 않을 경우 {@code false}를 반환
*/
boolean contains(Object value);
/**
* 리스트에 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
*
* @param value 리스트에서 위치를 찾을 요소 변수
* @return 리스트에서 처음으로 요소와 일치하는 위치를 반환.
* 만약 일치하는 요소가 없을경우 -1 을 반환
*/
int indexOf(Object value);
/**
* 리스트에 있는 요소의 개수를 반환합니다.
*
* @return 리스트에 있는 요소 개수를 반환
*/
int size();
/**
* 리스트에 요소가 비어있는지를 반환합니다.
* @return 리스트에 요소가 없을경우 {@code true}, 요소가 있을경우 {@code false}를 반환
*/
boolean isEmpty();
/**
* 리스트에 있는 요소를 모두 삭제합니다.
*/
public void clear();
}
1. 클래스 및 생성자 구성
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; // 요소를 담을 배열
// 생성자1 (초기 공간 할당 X)
public ArrayList() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
// 생성자2 (초기 공간 할당 O)
public ArrayList(int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
}
2. 동적할당을 위한 resize
size(요소의 개수)가 용적(capacity)에 얼마만큼 차있는지를 확인하고, 적절한 크기에 맞게 배열의 용적을 변경해야한다.
용적은 외부에서 마음대로 접근하면 데이터의 손상을 야기할 수 있기때문에 private로 접근을 제한한다.
private void resize() {
int array_capacity = array.length;
// 1. if array's capacity is 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));
return;
}
}
1) if (Arrays.equals(array, EMPTY_ARRAY))
생성자 단계에서 용적을 별도로 설정하지 않은 경우 EMPTY_ARRAY로 초기화되어 용적이 0인 상태이다.
새로운 array의 용적을 할당하기 위해 최소 용적으로 설정해두었던 DEFAULT_CAPACITY 크기만큼 배열을 생성해주고 메소드를 종료한다.
(주소가 아닌 값을 비교해야하기 때문에 equals 사용)
2) if (size == array_capacity)
데이터가 용적 크기만큼 꽉 찰 경우에 용적을 더 늘려야 한다. 현재 용적 크기의 2배로 늘린다.
또한 기존에 담겨있던 요소들을 새롭게 복사해와야 하는데 Arrays.copyOf(복사할 배열, 용적의 크기) 메소드를 쓴다.
복사할 배열 < 용적의 크기 인 경우, 나머지 빈 공간은 null로 채워진다.
3) if (size < (array_capacity / 2))
데이터가 용적 크기의 절반 미만을 차지 할 경우인데, 불필요한 공간을 줄여줘야 한다.
3. add
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
if (size == array.length) {
resize();
}
array[size] = value;
size++;
}
@Override
public void add(int index, E value) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == size) {
addLast(value);
}
else {
if(size == array.length) {
resize();
}
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = value;
size++;
}
}
public void addFirst(E value) {
add(0, value);
}
1) 기본(마지막 위치) 삽입 : add(E value) & addLast(E value)
2) 중간 삽입 : add(int index, E value)
index가 범위를 벗어나지 않는지 확인 후 그 뒤에 있는 데이터들을 모두 한칸씩 밀어 중간에 데이터를 삽입한다.
3) 첫번째 위치 삽입 : addFirst(E value)
모든 데이터들을 뒤로 밀어 index=0 자리에 데이터를 삽입한다.
4. get, set, indexOf, contains
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if(index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
return (E) array[index];
}
@Override
public void set(int index, E value) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
} else {
array[index] = value;
}
}
@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 - 1; i >= 0; i--) {
if(array[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public boolean contains(Object value) {
if(indexOf(value) >= 0) {
return true;
}
else {
return false;
}
}
1) get(int index)
index로 들어오는 값을 인덱스삼아 해당 위치에 있는 요소를 반환하는 메소드로
배열의 위치를 찾아가는 것이기때문에 반드시 잘못된 위치 참조에 대한 예외처리가 필수적이다.
여기서 @SuppressWarnings("unchecked") 에 대해 잠깐 언급하고 가겠다.
@SuppressWarnings("unchecked")을 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다. 반환되는 것을 보면 E 타입으로 캐스팅을 하고 있고 그 대상이 되는 것은 Object[] 배열의 Object 데이터다. 즉, Object -> E 타입으로 변환을 하는 것인데 이 과정에서 변환할 수 없는 타입을 가능성이 있다는 경고로 메소드 옆에 경고표시가 뜨는데, 우리가 add하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재한다.
그렇기 때문에 형 안정성이 보장된다. 한마디로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 것이 @SuppressWarnings("unchecked") 이다. 물론 절대 남발하면 안되고, 형 변환시 예외 가능성이 없을 확실한 경우에 최소한의 범위에서 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있기 때문이다.
2) set(int index, E value)
기존 index에 위치한 데이터를 새로운 데이터로 교체하는 메소드이다. (add=추가, set=교체 의미)
3) indexOf(Object value)
사용자가 찾고자하는 요소의 위치(index)를 반환하는 메소드이다.
찾고자하는 요소가 중복된다면 가장 먼저 마주치는 요소의 인덱스를 반환하며, 요소가 없다면 -1을 반환한다.
4) LastIndexOf(Object value)
거꾸로 요소의 위치를 탐색하는 메소드이다.
5) Contains(Object value)
사용자가 찾고자하는 요소의 존재여부를 검사하는 메소드이다.
5. remove
@SuppressWarnings("unchecked")
@Override
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
E element = (E) array[index];
array[index] = null;
for (int i = index; i < size; i++) {
array[i] = array[i + 1];
array[i + 1] = null;
}
size--;
resize();
return element;
}
@Override
public boolean remove(Object value) {
int index = indexOf(value);
if (index == -1) {
return false;
}
remove(index);
return true;
}
1) 특정 index의 요소 삭제 - remove(int index)
특정 위치에 있는 요소를 제거하는 메소드로, index에 위치한 데이터를 삭제 한 후 해당 위치 이후의 데이터들을 한 칸씩 당겨온다.
2) 특정 요소 삭제 - remove(Object value)
사용자가 원하는 특정 요소를 찾아 삭제하는 메소드로, 매칭되는 요소가 여러 개 있을 경우 가장 먼저 마주하는 요소만 삭제한다. remove(int index)메소드와 마찬가지로 데이터 삭제 후 이후의 데이터들을 한 칸씩 당겨온다.
6. size, isEmpty, clear
@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();
}
1) size() - 요소 개수 반환
2) isEmpty() - 요소가 비어있는지 확인
3) clear() - 모든 요소를 비워버리는 메소드
7. clone
기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 생성하는 메소드(복제)
단순히 연산자로 객체를 복사하게 되면 주소를 복사하는 것이기때문에 복사한 객체에서 데이터 조작을 할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(Shallow copy)가 된다. 이러한 점을 방지하기 위해서 깊은 복사가 필요한데 이때 쓰이는 메소드이다.
Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 사용자 클래스의 경우 Cloneable 인터페이스를 implement해야한다. (public class ArrayList<E> implements List<E>에 Cloneable 추가)
ArrayList<Integer> original = new ArrayList<>();
original.add(10); // original에 10추가
ArrayList<Integer> copy = original;
ArrayList<Integer> clone = (ArrayList<Integer>) original.clone();
copy.add(20); // copy에 20추가
clone.add(30); // clone에 30추가
System.out.println("original list");
for(int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + original.get(i));
}
System.out.println("\ncopy list");
for(int i = 0; i < copy.size(); i++) {
System.out.println("index " + i + " data = " + copy.get(i));
}
System.out.println("\nclone list");
for(int i = 0; i < clone.size(); i++) {
System.out.println("index " + i + " data = " + clone.get(i));
}
System.out.println("\noriginal list reference : " + original);
System.out.println("copy list reference : " + copy);
System.out.println("clone list reference : " + clone);@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;
}
8. toArray
ArrayList<Integer> list = new ArrayList<>();
// get list to array (using toArray())
Object[] array1 = list.toArray();
// get list to array (using toArray(T[] a)
Integer[] array2 = new Integer[10];
array2 = list.toArray(array2);1) Object[] toArray()
아무런 인자 없이 ArrayList의 객체를 객체배열(Object)로 반환해주는 메소드
ArrayList에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환되는 장점이 있다.
2) T[] toArray(T[] a)
이미 생성된 다른 배열에 ArrayList를 복사해주는 메소드
객체 클래스로 상속관계에 있는 타입이거나 Wrapper클래스같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다.
리스트에 원소 5개가 있고, array2배열에 10개의 원소가 있다면 array2의 0~4 index에 리스트에 있던 원소가 복사되고, 그 외의 원소는 기존 array2배열에 초기화 되어있던 원소가 그대로 남는다.
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;
}
출처 및 참고
https://st-lab.tistory.com/161
[JAVA 자료구조] List Interface (리스트 인터페이스)
배열 vs List 인터페이스 공통점 1. 동일한 특성의 데이터타입을 묶는다. 2. 반목문내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다. 차이점 - 배열 1. 처음 선언한 배열의 크기는
prinha.tistory.com
'Programming > Algorithm&DataStructure' 카테고리의 다른 글
| [JAVA 자료구조] Doubly LinkedList (이중 연결리스트) (0) | 2021.08.09 |
|---|---|
| [JAVA 자료구조] Singly LinkedList (단일 연결리스트) (0) | 2021.08.05 |
| [JAVA 자료구조] List Interface (리스트 인터페이스) (0) | 2021.08.04 |
| [Algorithm] 정렬 알고리즘 요약 정리 (0) | 2021.08.01 |
| [Algorithm] 시간 복잡도 & Big-O표기법 (0) | 2021.07.30 |
