보통 개발유튜브 같은 곳에서 "프로젝트는 어떻게 진행해야할까요? 뭐부터 시작해야할까요? 그냥 완벽히 공부하고 시작하면 안될까요?"라는 질문에 대해서 "그냥 시작해라"라고하는데, 그래서 나도 어제 그냥 시작했다.
근데 CS지식이 약간 모자르다보니 자료를 어떻게 관리해야하고 어떤 기능이 있고는 아직 좀 헷갈렸다. 그러다보니 코드가 좀 꼬였는데 다시 풀자니 어디가 잘못될지 몰라서 제대로 풀지도 못하고.. 역시 자바의정석을 좀 읽읍시다.
오늘부터하는 내용은 컬렉션 프레임웍의 하위클래스들에 대해서 알아볼 예정이다.
1. 컬렉션 - 리스트 - ArrayList / Vector
ArrayList는 List 인터페이스의 구현체이기 때문에 데이터가 순서대로, 중복을 허용하며 저장된다. JDK1.2, 그러니까 컬렉션이 등장하기 전부터 있던 Vector를 개선한 것으로 두 클래스는 크기 가변적인 배열을 지원하기 위해 사용되기 시작했다. 어제 작성한 글에도 있지만 둘의 다른점은 동기화. 동기화에서 성능차이가 발생한다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
}ArrayList 클래스 내부의 일부. ArrayList 역시 내부적으로는 배열을 사용하고 있으며, 하나의 예시로 add() 메서드를 사용하여 값을 요소를 추가하면 배열의 크기를 동적으로 조정하며 배열에 값을 추가한다.
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}그리고 elementData가 Object 배열로 선언되어있어 아무객체나 다 받을 수 있다는 것이 특징이다.
Object 배열인 elementData에 저장된 각 요소 반환해야할 때는 마지막에 캐스팅만 진행하여 반환한다.
Objects.checkIndex(index, size)는 저장 중인 elementData보다 큰 값을 인덱싱하려하면 에러가 발생하게한다. 모든 클래스의 상위클래스인 Object 클래스가 아니다.
그래서 성능이 중요한 경우가 아니라면 에러 가능성도 적고 작성할 코드도 줄어드는 ArrayList를 사용하는 것이 좋다.
기본적인 메서드
ArrayList() //크기가 10인 ArrayList 생성
ArrayList(Collection c) //주어진 컬렉션이 저장된 ArrayList 생성
ArrayList(int initialCapacity) //초기 크기가 정해진 ArrayList 생성public void trimToSize() //내부 배열의 빈공간을 없앤다.
public void ensureCapacity(int minCapacity) //ArrayList의 용량이 최소한 minCapacity가 되도록한다.
public int size() //ArrayList에 저장된 객체의 수 반환
public boolean isEmpty() //ArryList가 비었는지 확인
public boolean contains(Object o) //ArrayList 내부에 o가 있는지 확인
public int indexOf(Object o) //o의 위치를 처음에서부터 조사하여 첫 번째 반환
public int lastIndexOf(Object o) //o의 위치를 끝에서부터 조사하여 첫 번째 위치 반환
public Object clone() //복제
public Object[] toArray() //ArrayList를 객체배열로 반환한다.
public <T> T[] toArray(T[] a) //ArrayList에 저장된 객체를 객체배열 a에 담아 반환
public E get(int index) //지정된 인덱스의 값 반환
public E set(int index, E element) //주어진 객체 element를 index 위치에 저장. 덮어쓰기
//inex 위치에 element 또는 컬렉션 c 저장. 요소들이 하나씩 뒤로 밀린다.
//인덱스값이 전해지지 않으면 배열의 끝에 저장한다.
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
//index 위치 또는 객체 o를 찾아서 요소 삭제. 배열들이 하나씩 앞으로 당긴다.
public E remove(int index)
public boolean remove(Object o)
public boolean removeAll(Collection<?> c)
//리스트 비우기
public void clear()
//지정된 요소, 컬렉션을 제외하고 전부제거
public boolean retainAll(Collection<?> c)
//listIterator 반환
public ListIterator<E> listIterator(int index)
public ListIterator<E> listIterator()
//이터레이터 객체반환
public Iterator<E> iterator()
//특정위치를 리스트화하여 반환
public List<E> subList(int fromIndex, int toIndex)좀 많다.
컬렉션에서 받은것과 리스트에 받은 것을 오버라이드하고 있다..
public static void main(String[] args) {
List<Integer> l = new ArrayList<>();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
l.add(5);
for (int idx = 0; idx < l.size(); idx++) {
if (idx % 2 == 0){
System.out.println("Removed: " + l.get(idx));
l.remove(idx);
}
}
for (Integer i : l) {
System.out.println(i);
}
}추가로 .remove()와 관련하여 책에서 예제를 보여주고 있는데,
반복변수를 0부터 ArrayList.lenth까지 돌면서 배열의 값을 제거하면 인덱스의 배열을 제거하고 인덱스 이후의 배열요소들을 앞으로 앞당기게되는데, 그렇기 때문에 원하는 값을 얻을 수 없다.
위 코드는 idx 값을 증가시키면서 배열의 짝수요소만 제거하도록 되어있는데, .remove() 메서드는 선술한대로 제거 후 빈공간을 채우기 위해 나머지 요소들을 앞으로 당기기 때문에 원하는 값을 받을 수 없다.
이렇게 원래 배열에서 0번째 요소였던 1, 4번째 요소였던 4만 남고, 2, 3, 5번째 요소는 제거되지 않는다.
public static void main(String[] args) {
List<Integer> l = new ArrayList<>();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
l.add(5);
for (int idx = l.size(); idx >= 0; idx--) {
if (idx % 2 == 0){
System.out.println("Removed: " + l.get(idx));
l.remove(idx);
}
}
for (Integer i : l) {
System.out.println(i);
}
}그래서 remove() 메서드를 사용할 때 반복문이 ArrayList의 사이즈에서 0까지 내려오도록 작성해야한다.
홀수가 삭제되는 이유는 ArrayList의 시작값은 1이지만 인덱스의 시작값은 1부터이기 때문이다.
예시를 ArrayList로 들었지만 Vector도 동일하다. ArrayList와 Vector의 기능들은 성능을 제외하면 같기 때문이다.
trimToSize(), add() (추가하려는 값의 인덱스 위치가 현재 배열의 크기를 벗어날 때) 내부적으로 배열의 크기를 조정하는 메서드들이 있는데, ArrayList는 크기를 조정할 수 있으나 배열은 크기를 조정할 수 없기 때문에 내부적으로 배열의 크기를 조정하면 그 때마다 새 배열이 새로 생기고 기존 배열은 GC 대상이된다.
자바의정석 ch.11 620쪽에 자세히 나와있는데,
10 크기의 ArrayList나 Vector를 생성하고 임의의 값을 5개 추가하고 trimToSize() 메서드를 사용했으면, 내부적으로는 크기가 10인 배열이 있다가 크기가 5인 배열로 변경되게된다. 기존 배열은 GC 대상이되며 접근할 수 없다.
이런상황에서 만약 add() 메서드를 사용하여 요소를 추가했다면 크기가 6인 배열이 새로 생긴다.
이외에도 serSize(int capacity) 등의 메서드를 사용해도 내부적으로는 비슷한 과정을 거치며,
clear() 메서드를 사용한다면 새 인스턴스가 생성되지 않고 배열의 모든 요소를 null로 교체한다.
그렇기 때문에 ArrayList와 Vector는 배열의 자료를 읽고 사용하는데 효율적이지만, 용량을 변경해야할 때마다 새 배열이 생성되기 때문에 상당히 효율이 떨어진다. 그래서 크기가 가변적인 배열이라고 마구 add, trimToSize, setSize를 할 것이 아니라 생성 전부터 미리 저장할 데이터의 수를 잘 고려해야한다.
LinkedList
기존의 배열은 그 시간이 빠르고 간단하다는 장점이 있었으나, 크기를 동적으로 설정하지 못하고 (ArrayList와 Vector도 내부적으로 배열을 사용했기 때문에 크기를 조정하려면 새 배열을 매번 선언해야해서 동적크기조정은 불가능했다.), 배열의 중간부분에서 데이터를 추가 / 삭제하면 나머지 데이터들의 위치도 조정했어야했기 때문에 시간이 오래걸렸다.
이러한 단점들을 보완하고자 등장한 것이 링크드리스트이다.
C에서 구조체에 포인터 변수를 변수 이전 구조체와 다음 구조체를 명시하여 일련의 배열로 사용할 수 있듯이, 링크드 리스트 역시 다음 요소의 주소를 저장한다. 각 요소를 노드라고 칭한다.
각 노드에는 저장할 값과 자신과 연결된 다음 노드의 주소를 가지고있다.
가장 마지막 노드는 다음 노드의 주소를 null로 저장한다.
삭제 역시 삭제할 노드와 연결된 노드에서 다음 노드의 주소를 수정하면 되기 때문에 간단하다. 그래서 동적으로 배열의 크기를 조정할 수 있고 배열의 크기를 조정할 때마다 배열을 복사하지 않아도된다.
새 값을 추가할 때도 노드만 수정해주면 되기 때문에 간편하다.
다만 링크드리스트는 단방향으로 움직이기 쉽지만, 반대로 이전요소의 노드가 어떤 것인지 알기는 어렵다. 그래서 보완된 것이 노드에 이전 노드의 주소까지 추가하는 더블링크드리스트이다.
더블링크드리스트는 링크드리스트에서 이전요소에 대한 참조가 가능하도록 참조변수를 하나 추가한 형태다.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}자바에서 제공하는 LinkedList 클래스도 더블링크드리스트 형태로 지원한다.
여기서 접근성을 더 향상시킨 것이 '더블 써큘러 링크드 리스트'(이중원형연결리스트)이다.
첫 번째 노드의 이전노드주소가 가장 마지막 노드가되며, 가장 마지막 노드의 다음노드주소가 첫 번째 노드의 주소가 된다. 즉, 링크드리스트를 계속 순회하며 요소에 접근할 수 있다.
LinkedList의 메서드 역시 List에의 구현체이기 때문에 ArrayList와 거의 비슷하다.
다만 LinkedList는 JDK5부터 Queue, JDK6부터 Deque 인터페이스를 구현하기 때문에 이 메서드들이 추가되었다.
이건 소단원인 스택과 큐에서 해보는걸로하고
나머지 메서드들은 ArrayList와 비슷하기 때문에 굳이 하진 않겠다.
성능비교
public static void main(String[] args) {
ArrayList<Integer> a = new ArrayList();
LinkedList<Integer> b = new LinkedList<>();
long befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 10000000; idx++){
a.add(idx);
}
long after = System.currentTimeMillis();
System.out.println("ArrayList: " + (after - befor));
befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 10000000; idx++){
b.add(idx);
}
after = System.currentTimeMillis();
System.out.println("LinkedList: " + (after - befor));
}반복문을 돌면서 1부터 1천만까지의 값을 각각 ArrayList와 LinkedList에 추가하는 작업을 실행하면
ArrayList가 거의 10배는 빠르다.
ArrayList의 배열복사가 일어나지 않도록 초기 capacity 값을 수정하면 그 시간은 더 줄어든다.
즉, 단순히 마지막요소에 값을 추가하거나 삭제하는 경우, 순차적 추가/삭제의 경우에는 ArrayList가 더 빠르다. (순차적 삭제는 역순 삭제를 의미한다.)
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> a = new ArrayList(20000000);
LinkedList<Integer> b = new LinkedList<>();
for (Integer idx = 0; idx < 10000000; idx++){
a.add(idx);
}
long befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 100; idx++){
a.add(idx, idx % 101);
}
long after = System.currentTimeMillis();
System.out.println("ArrayList: " + (after - befor));
for (Integer idx = 0; idx < 10000000; idx++){
b.add(idx);
}
befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 10000; idx++){
b.add(idx, idx % 101);
}
after = System.currentTimeMillis();
System.out.println("LinkedList: " + (after - befor));
}
}
반면 기존배열의 중간에서 데이터를 추가하거나 삭제하는 경우네는 LinkedList가 더 빠르다. ArrayList가 배열에서 요소 100개를 추가하는데 770ms가 걸렸지만 LinkedList는 10000개를 추가하는데 69ms 밖에 걸리지 않았다.
LinkedList는 각 요소의 연결된 노드만 변경해주면되지만, ArrayList는 각 요소들을 이동시켜 추가할 공간을 확보해야하기 때문에 느린 편이다.
단, LinkedList의 중간데이터 추가/삭제를 0이 아닌 값부터 시작하면 시작위치까지 이동하는 시간 때문에 ArrayList가 더 느리다.
배열의 경우에는 메모리에 연속적으로 값이 저장되기 때문에 배열에서 원하는 인덱스의 주소는 (배열의 주소 (배열의 첫 번째 원소의 주소) + (저장된 데이터 타입의 크기) * (원하는 인덱스의 번호) 를 통해 곧바로 인덱스에 접근할 수 있으나, LinkedList에서는 메모리에 불연속적으로 값이 저장되기 때문에 원하는 인덱스의 번호만큼 다음노드를 따라 차례차례 이동하여야하기 때문이다.
위와 같은 에시들은 극명한 시간차이를 보이기 위해 이렇게 일부러 천만 번씩 반복문을 돌려가며 측정한 것이기에, 데이터의 개수가 크지 않다면 둘의 큰 성능차이는 없다. 다만 각 자료구조의 특징과 어느 상황에서 더 빠른지를 이해하고 잘 활용하여야 할 것이다.
다루고자하는 데이터의 개수가 변하지 않고, 단지 순차적 추가/제거만 하는 경우에는 ArrayList가 더 빠를 것이고, 데이터가개수가 변하는 경우, 배열의 중간에 개입하여 데이터를 추가/삭제해야하는 경우에는 LinkedList가 더 빠를 것이다.
컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스는 서로를 생성자의 매개변수로 담아 형변환이 가능한 경우가 많다. 따라서 ArrayList와 LinkedList를 적절히 형변환해가며 두 자료구조의 효율성을 극대화시키는 방향으로 사용해도 좋다. 가령 단순 데이터추가는 ArrayList에게, 값을 다 추가하고 배열 중간에서부터 값을 추가해야한다면 LinkedList에게.. 이런 식으로
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> a = new ArrayList();
List<Integer> b = new LinkedList<>();
long befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 10000000; idx++){
a.add(idx);
}
for (Integer idx = 0; idx < 1000; idx++){
a.add(idx, idx % 103);
}
long after = System.currentTimeMillis();
System.out.println("ArrayList: " + (after - befor));
befor = System.currentTimeMillis();
for (Integer idx = 0; idx < 10000000; idx++){
b.add(idx);
}
for (Integer idx = 0; idx < 1000; idx++){
b.add(idx, idx % 103);
}
after = System.currentTimeMillis();
System.out.println("LinkedList: " + (after - befor));
befor = System.currentTimeMillis();
a = new ArrayList<>();
for (Integer idx = 0; idx < 10000000; idx++){
a.add(idx);
}
b = new LinkedList<>(a);
for (Integer idx = 0; idx < 1000; idx++){
b.add(idx, idx % 103);
}
after = System.currentTimeMillis();
System.out.println("ArrayList + LinkedList: " + (after - befor));
}
}
'언어공부 > Java | Kotlin' 카테고리의 다른 글
| [CS] 자바의 정석 독서 #21 - 이터레이터 (1) | 2025.11.22 |
|---|---|
| [CS] 자바의 정석 독서 #20 - 스택과 큐 in Java (0) | 2025.11.22 |
| [CS] 자바의정석 독서 #18 - 컬렉션은 무엇인가? (1) | 2025.11.20 |
| [CS] 자바의 정석 독서 #17 - StringBuffer, StringBuilder (0) | 2025.11.19 |
| [CS] 자바의 정석 독서 #16 - String 클래스 파헤치기 (0) | 2025.11.18 |