[Data Structure] Array List 구현
[구현 바로 가기]
Array List는 자료구조에서 제일 기본이자 핵심적인 자료구조이다.
🎯Array List와 Array의 차이는 뭘까?
int[] arr = new int[5];
이런 배열은 한 번 배열의 크기를 정해주면 끝까지 최대 5의 값의 공간을 지닌다.
일반 배열은 고정된 크기의 자료 구조이고 타입은 기본형, 참조형 모두 가능하다.
일반 배열은 성능이 좋고 구조가 단순하다. 계획적인 프로그래밍에서는 메모리가 더 효율적일 수 있다.
일반 배열의 한계
1. 크기가 고정되어 메모리 낭비나 크기가 부족할 때 문제가 생긴다.
2. 기능들이 부족하다.
동적 배열을 위한 ArrayList
자바에서는 공식적으로 ArrayList라는 클래스가 존재한다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
java.util.ArrayList 는 List 인터페이스를 구현한 클래스이다. 해당 ArrayList 클래스는 Type이 객체만 가능하다.
아마 기본형으로 list에 값을 넣으면 오토박싱으로 래퍼 클래스로 변경될 것이다.
java.util.ArrayList는 다양한 메서드들이 존재하고 List로부터 상속받은 메서드들도 존재하여 매우 많은 기능들이 존재한다.
ArrayList의 장점
1. 크기가 자동적으로 조절이 가능하다. (동적 배열)
2. 유용한 메서드들을 제공한다.
3. 삽입과 삭제가 편리하고 중간 요소도 쉽게 조작이 가능하다.
ArrayList의 한계
1. java.util.ArrayList에서는 객체 타입만 저장 가능하다. 기본형이 저장 시 오토박싱으로 래퍼 클래스로 사용된다.
2. 성능이 다소 느리다. (배열 복사 등 부하 존재)
3. 오토 박싱/언박싱으로 오버헤드가 존재한다.
🤷♂️어떤 상황에서 무엇을 사용해야 할까??
| 상황 | 추천 |
| 크기가 고정이고 성능이 중요한 경우 | 배열(Array) |
| 요소의 삽입/삭제가 자주 발생, 크기가 동적일 때 | ArrayList |
| 유틸리티 메서드들을 다양하게 활용할 때 | ArrayList |
| 기본형 타입만 다룰 경우 | 배열(Array) |
가장 큰 것은, 크기가 동적이고 값을 얼마나 삽입할지 잘 모를 경우 ArrayList를 사용해 동적 할당을 이용하자.
구현
Java에서도 공식적으로 지원하지만 학습을 위해 직접 구현해 보았다.
객체만 넣을 수 있으므로 제네틱 타입 변수 E를 사용하였다.
제네릭 타입으로 오토박싱으로 기본형도 사용할 수 있게 끔 한다.
ArrayList를 구현하기 전, 선형 자료 구조들은 공통적인 기능들이 존재해 List라는 인터페이스를 별도로 만들었다.
List 인터페이스는 나중에 LinkedList 등 다양한 리스트들이 구현하여 공통적인 기능들을 오버라이딩 할 수 있게 한다.
List 인터페이스 코드
package list;
public interface ListI<E> {
/**
* List 맨 앞에 요소를 추가합니다. (append)
*
* @param element 새롭게 추가되는 값
*/
public void addFirst(E element);
/**
* List 특정 index에 요소를 추가합니다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
*/
public void add(int index, E element);
/**
* List에 요소 추가 기본적으로 append 맨 뒤에 추가.
*
* @param element list에 삽입할 값
*/
public void add(E element);
/**
* List 맨 마지막에 요소를 추가합니다.
*
* @param element 새롭게 추가되는 값
*/
public void addLast(E element);
/**
* 특정 요소가 몇 번째 index에 존재하는지 반환하는 메서드
*
* @param element 찾고자 하는 값
* @return 찾았을 때 index값 반환
* 없다면 -1 반환
*/
public int indexOf(E element);
/**
* 특정 index에 요소 제거
*
* @param index 제거하고자 하는 특정 index값
* @return 제거한 값 반환
*/
public E remove(int index);
/**
* 리스트가 공백 상태인지 확인하는 메서드
*
* @return 공백일 시 true 공백이 아닐 시 false
*/
public boolean isEmpty();
/**
* 리스트가 포화 상태인지 확인하는 메서드
*
* @return 포화일 시 true 포화가 아닐 시 false
*/
public boolean isFull();
/**
* 특정 index의 요소 반환
* @param index 찾을 위치 index
* @return 찾은 요소 반환
*/
public E get(int index);
/**
* 특정 index의 요소를 매개변수 요소로 변경하는 메서드
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
*/
public void set(int index, E element);
/**
* @param element
* @return element값이 리스트에 존재하면 true 아니면 false
*/
public boolean contains(E element);
/**
* 리스트에 존재하는 요소의 개수 반환
*
* @return 리스트의 총 용량
*/
public int size();
/**
* 리스트의 총 용량 반환.
*
* @return 리스트의 총 용량
*/
public int capacity();
}
//2025-05-21 weonhyeok
ArrayList 생성자와 클래스, 인스턴스 변수(필드)들, 동적 할당
ArrayList의 인스턴스 변수는 크게 3개이다.
size = List의 총 크기
list = 요소들이 저장되는 곳
count = List에 요소가 몇 개인지 체크하는 변수
Default size는 10이다. 사용자가 따로 ArrayList의 크기를 설정해주지 않는다면 10을 기본사이즈로 한다.
public class ArrayList<E> implements ListI<E> {
private int size;
private E[] list;
private int count;
/**
* 기본 생성자 list 기본 사이즈 10
*/
public ArrayList() {
this(10);
}
/**
* 생성자 입력받은 size만큼 배열 생성
* 메모리 누수 예외 처리 기능도 수행
*
* @param size 배열 크기 정수값 변수
*/
public ArrayList(int size) {
try {
this.size = size;
list = (E[]) (new Object[size]);
} catch (OutOfMemoryError oome) {
System.out.println("메모리 에러");
oome.printStackTrace();
}
}
}
[동적할당]
C언어와 달리 동적할당이 존재하지 않는다. JVM이 알아서 메모리를 관리하니
malloc(), free() 함수 같은 게 존재하지 않아. 따로 만들어 주었다.
기본적인 메커니즘은 이러하다.
1. 포화 상태
count==size는 리스트의 총 크기와 요소들의 개수가 동일하므로 리스트가 꽉 찬 상태인 것이다.
꽉 찬 상태(포화) 일 경우 list의 size를 2배를 늘려준다. 여기서 기존에 저장해 두었던 List 요소들을 System.arraycopy로 빠른 배열 복사를 한다.
2. 절반 미만 상태 (메모리 낭비)
count <size/2가 true일 시 배열의 절반 이상이 놀고 있는 상태이므로 메모리 낭비이다. 배열의 크기를 절반 줄여준다.
/**
* 동적 할당을 위한 메서드
* size값과 list에 존재하는 요소 개수와 list 크기 size값이 동일할 경우
* 포화 상태이므로 배열 size 2배로 늘린다.
* <p>
* count값이 size/2 보다 작다면 메모리 낭비이니 배열의 크기를 반으로 줄인다.
*/
private void mallocSize() {
if (count == size) {
E[] copy = (E[]) new Object[size * 2];
size *= 2;
System.arraycopy(list, 0, copy, 0, count);
list = copy;
return;
}
if (count < size / 2) {
E[] copy = (E[]) new Object[size / 2 + 1];
size /= 2;
System.arraycopy(list, 0, copy, 0, count);
list = copy;
return;
}
}
add (삽입 연산)
List 인터페이스를 보면 add 메서드가 한 개가 아닌 여러 개 존재한다.
1. addFirst(E element)
2. addLast(E element)
3. add(E element)
4. add(int index)
addFirst는 list의 맨 앞에 요소를 추가한다.
addLast는 list의 맨 뒤에 요소를 추가한다.
add()는 addLast를 호출해 뒤에 요소를 추가한다.
add(index)는 특정 index에 요소를 추가한다.
우선 Java 공식 ArrayList에서는 기본적인 삽입 연산은 뒤에서 리스트 요소를 추가한다.
addFirst(E element)
리스트에 맨 앞에 요소를 넣는 기능. 기존에 있던 모든 요소들을 index 1칸씩 뒤로 밀어야 한다.
addLast(E element)
count 변수로 바로 삽입한다.
add(int index E element)
add 연산자 중 add(int index) 특정 인덱스에 요소를 삽입하는 경우가 제일 복잡한 로직일 것이다.
중간 삽입 기능인데 인수로 넘어온 index값에 요소를 넣어야 하니 기존에 존재했던 요소와 그 요소 다음 요소들을 전부 다 1칸씩 밀어야 한다.
모든 add 기능은 데이터를 추가하고 인스턴스 변수 count값을 증가시킨다.
1. 데이터 추가
2. count 증가
[나중에 추가할 그림 05 21]
add 메서드들 소스 코드
/**
* List 맨 앞에 매개변수 element 삽입.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
if (isFull()) {
System.out.println("꽉 참");
mallocSize();
}
for (int i = count; i > 0; i--) {
list[i] = list[i - 1];
}
list[0] = element;
count++;
}
/**
* Java에서 지원하는 ArrayList도 기본적으로 append 형식
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
}
/**
* param index 포함해서 index 앞에 있던 요소들을 한 칸 씩 뒤로 옮긴다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
* @throws IndexOutOfBoundsException 잘못된 index 접근 시 예외 발생
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || size < index) {
System.out.println("index 접근 잘 못 함.");
throw new IndexOutOfBoundsException();
}
if (index == size - 1) {
addLast(element);
}
if (isFull()) {
mallocSize();
}
for (int i = count - 1; i >= index; i--) {
System.out.println(i);
list[i + 1] = list[i];
}
list[index] = element;
count++;
}
/**
* @param element 새롭게 추가되는 값
*/
@Override
public void addLast(E element) {
if (isFull()) {
mallocSize();
}
list[count] = element;
count++;
}
remove() 삭제
remove도 사실 index를 이용한 삭제와 특정 요소값을 통한 삭제가 존재하지만
index를 이용한 삭제 연산만 구현하였다.
index값이 0 미만이거나 count 보다 같거나 크면 잘못된 인덱스 참조니 예외 발생시킨다.
remove 연산은 우선 특정 index에 존재하는 요소를 삭제를 먼저 한다. (null로 변경)
null로 변경 후 index+1부터 count-1번째 요소들을 모두 한 칸 앞 당긴다.
코드에서는 null로 변경된 index값부터 index+1의 대입시킨다.
/**
* index값에 존재하는 요소 삭제한다. 삭제한 후 index 다음 요소들을 다 한 칸씩 앞 당긴다.
* @param index 제거하고자 하는 특정 index값
* @return 삭제한 요소
* @throws IndexOutOfBoundsException 잘못된 index 접근 시 예외 발생
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= count) {
throw new IndexOutOfBoundsException();
} else {
E removeE = list[index];
list[index] = null;
for (int i = index; i < count - 1; i++) {
list[index] = list[index + 1];
}
list[count - 1] = null;
mallocSize();
System.out.println("제거된 값: " + removeE);
count--;
return removeE;
}
}
각 종 유틸리티
각 종 유틸리티이다.
get, set, indexOf, contains, isEmpty, isFull, size, capacity 등이 존재하는데 ArrayList를 구현하는 개발자 혹은 불러와서 사용하는 개발자가 필요에 따라 새로운 기능들을 추가하고 수정하면 된다.
isEmpty() && isFull()
공백과 포화상태를 체크하는 메서드이다. 사실 ArrayList에서는 포화상태가 존재하진 않을 것이다. 동적할당으로 인해 메모리를 전부 다 사용하지 않는 한 포화상태는 존재하지 않을 것이다.
/**
* count 변수가 0일 시 list에 어떠한 요소도 존재하지 않다. true 반환
*
* @return count==0 true, 공백 상태
*/
@Override
public boolean isEmpty() {
return count == 0;
}
/**
* size와 count가 동일하거나 count가 크면 true 반환
*
* @return true = 포화 false = 포화 상태가 아님.
*/
@Override
public boolean isFull() {
return size <= count;
}
get(int index)
매개변수 index를 통해 특정 index에 존재하는 요소를 반환하는 메서드이다.
/**
* 특징 index에 존재하는 요소 반환
*
* @param index 찾고자 하는 index 값
* @return index값에 요소 존재하면 해당 요소 반환
* @throws IndexOutOfBoundsException index 잘 못 접근 시 예외 발생
*/
@Override
public E get(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
return list[index];
}
}
set(int index, E element)
특정 인덱스 요소를 인수로 받은 새로운 요소로 바꾸는 기능이다. 즉, change
/**
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
* @throws IndexOutOfBoundsException
*/
@Override
public void set(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
list[index] = element;
}
}
indexOf(E element)
인수 요소가 존재하는 index값 반환하는 메서드.
/**
* 특정 요소의 index값 반환하는 메서드
*
* @param element 찾고자 하는 값
* @return element가 존재하면 index값 반환, 존재하지 않으면 -1 반환
*/
@Override
public int indexOf(E element) {
if (isEmpty()) {
System.out.println("리스트가 비어있습니다.");
return -1;
} else {
for (int i = 0; i < count; i++) {
if (list[i].equals(element)) {
return i;
}
}
}
return -1;
}
contains(E element)
indexOf는 index값 반환이면 contains는 true, false로 boolean형으로 반환한다.
존재하면 true, 존재하지 않으면 false
/**
* indexOf()는 index값을 반환하는 메서드라면
* contains()는 true, false boolean 타입으로 반환
*
* @param element 찾고자하는 요소
* @return 존재하면 true, 아니면 false
*/
@Override
public boolean contains(E element) {
for (E value : list) {
if (value == element) {
return true;
}
}
return false;
}
size()와 capacity()
size(): 리스트에 존재하는 요소들의 개수 반환
contains(): 리스트의 크기 반환(총 크기)
/**
* 리스트의 요소가 몇 개인지 반환
*
* @return count값 반환
*/
@Override
public int size() {
return count;
}
/**
* 리스트의 최대 크기(요소를 가질 수 있는 최대 값)을 반환
*
* @return size값 반환 총 용량
*/
@Override
public int capacity() {
return size;
}
✨전체 코드
package list;
import java.util.Arrays;
public class ArrayList<E> implements ListI<E> {
private int size;
private E[] list;
private int count;
/**
* 기본 생성자 list 기본 사이즈 10
*/
public ArrayList() {
this(10);
}
/**
* 생성자 입력받은 size만큼 배열 생성
* 메모리 누수 예외 처리 기능도 수행
*
* @param size 배열 크기 정수값 변수
*/
public ArrayList(int size) {
try {
this.size = size;
list = (E[]) (new Object[size]);
} catch (OutOfMemoryError oome) {
System.out.println("메모리 에러");
oome.printStackTrace();
}
}
/**
* 동적할당을 위한 메서드
* size값과 list에 존재하는 요소 개수와 list 크기 size값이 동일할 경우
* 포화 상태이므로 배열 size 2배로 늘린다.
* <p>
* count값이 size/2 보다 작다면 메모리 낭비이니 배열의 크기를 반으로 줄인다.
*/
private void mallocSize() {
if (count == size) {
E[] copy = (E[]) new Object[size * 2];
size *= 2;
System.arraycopy(list, 0, copy, 0, count);
list = copy;
return;
}
if (count < size / 2) {
E[] copy = (E[]) new Object[size / 2 + 1];
size /= 2;
System.arraycopy(list, 0, copy, 0, count);
list = copy;
return;
}
}
/**
* List 맨 앞에 매개변수 element 삽입.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
if (isFull()) {
System.out.println("꽉 참");
mallocSize();
}
for (int i = count; i > 0; i--) {
list[i] = list[i - 1];
}
list[0] = element;
count++;
}
/**
* Java에서 지원하는 ArrayList도 기본적으로 append 형식
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
}
/**
* param index 포함해서 index 앞에 있던 요소들을 한 칸 씩 뒤로 옮긴다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
* @throws IndexOutOfBoundsException 잘못된 index 접근 시 예외 발생
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || size < index) {
System.out.println("index 접근 잘 못 함.");
throw new IndexOutOfBoundsException();
}
if (index == size - 1) {
addLast(element);
}
if (isFull()) {
mallocSize();
}
for (int i = count - 1; i >= index; i--) {
System.out.println(i);
list[i + 1] = list[i];
}
list[index] = element;
count++;
}
/**
* List 맨 뒤에 요소 추가
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addLast(E element) {
if (isFull()) {
mallocSize();
}
list[count] = element;
count++;
}
/**
* 특정 요소의 index값 반환하는 메서드
*
* @param element 찾고자 하는 값
* @return element가 존재하면 index값 반환, 존재하지 않으면 -1 반환
*/
@Override
public int indexOf(E element) {
if (isEmpty()) {
System.out.println("리스트가 비어있습니다.");
return -1;
} else {
for (int i = 0; i < count; i++) {
if (list[i].equals(element)) {
return i;
}
}
}
return -1;
}
/**
* @param index 제거하고자 하는 특정 index값
* @return
* @throws IndexOutOfBoundsException
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= count) {
throw new IndexOutOfBoundsException();
} else {
E removeE = list[index];
list[index] = null;
for (int i = index; i < count - 1; i++) {
list[index] = list[index + 1];
}
list[count - 1] = null;
mallocSize();
System.out.println("제거된 값: " + removeE);
count--;
return removeE;
}
}
/**
* count 변수가 0일 시 list에 어떠한 요소도 존재하지 않다. true 반환
*
* @return count==0 true, 공백 상태
*/
@Override
public boolean isEmpty() {
return count == 0;
}
/**
* size와 count가 동일하거나 count가 크면 true 반환
*
* @return true = 포화 false = 포화 상태가 아님.
*/
@Override
public boolean isFull() {
return size <= count;
}
/**
* 특징 index에 존재하는 요소 반환
*
* @param index 찾고자 하는 index 값
* @return index값에 요소 존재하면 해당 요소 반환
* @throws IndexOutOfBoundsException index 잘 못 접근 시 예외 발생
*/
@Override
public E get(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
return list[index];
}
}
/**
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
* @throws IndexOutOfBoundsException
*/
@Override
public void set(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
} else {
list[index] = element;
}
}
/**
* indexOf()는 index값을 반환하는 메서드라면
* contains()는 true, false boolean 타입으로 반환
*
* @param element 찾고자하는 요소
* @return 존재하면 true, 아니면 false
*/
@Override
public boolean contains(E element) {
for (E value : list) {
if (value == element) {
return true;
}
}
return false;
}
/**
* 리스트의 요소가 몇 개인지 반환
*
* @return count값 반환
*/
@Override
public int size() {
return count;
}
/**
* 리스트의 최대 크기(요소를 가질 수 있는 최대 값)을 반환
*
* @return size값 반환 총 용량
*/
@Override
public int capacity() {
return size;
}
/**
* list 상황을 쉽게 볼 수 있게 출력하는 메서드
*
* @return 리스트 배열 형식 문자열과 현재 요소가 몇 개 존재하지는 지 반환
*/
@Override
public String toString() {
return "ArrayList{" +
"list=" + Arrays.toString(list) +
"} count=" + count;
}
}
피드백 적극 환영입니다.