List
JDK 1.2부터 도입된 컬렉션 프레임워크는 자료구조&알고리즘과 이를 구현한 표준 인터페이스를 제공한다. 컬렉션 프레임워크는 List 인터페이스를 제공한다. List를 구현한 클래스에는 ArrayList, LinkedList, AttributeList, AbstractList 등이 있으나 가장 자주 쓰이는 ArrayList와 LinkedList만 알아볼 예정이다(자바 내부 코드는 JDK 17 버전이다).
List
List는 순서가 있고 중복을 허용하는 자료구조이다.
1. ArrayList
ArrayList는 List 인터페이스를 구현한 컬렉션이다. 배열의 특징을 구현한 리스트지만, 배열과 달리 저장 용량(capacity)을 줄이거나 늘릴 수 있다.
1.1. 기본 설정
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[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
}ArrayList는 값을 elementData에 저장한다.
1.2. 생성
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
}
}ArrayList는 ArrayList 내부 코드에서 정의한 세 개의 생성자로 생성할 수 있다.
빈 값으로 생성: 저장 용량은 기본 용량인 10으로 설정
용량을 지정해서 생성
용량이 9보다 작으면 IllegalArgumentException
그 외의 경우 용량에 지정값 설정
다른 컬렉션을 복사해서 생성: 컬렉션 용량만큼 용량 설정
실제 ArrayList 생성 예시는 다음과 같다.
import java.util.ArrayList;
public class ArrayListEx {
public static void main(String[] args) {
// capacity: 10, size: 0
ArrayList<Integer> list1 = new ArrayList<>();
// capacity: 7, size: 0
ArrayList<Integer> list2 = new ArrayList<>(7);
// capacity: 5, size: 5
ArrayList<Integer> list3 = new ArrayList<>(List.of(1, 2, 3, 4, 5));
}
}
1.3. 추가
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
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;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity,
oldCapacity >> 1);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData =
new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
}ArrayList에 값을 추가할 때는 add 메서드를 호출한다. add 메서드는 ArrayList에 저장된 요소 개수와 사이즈를 비교해서 용량을 늘릴지 확인한다. ArrayList 용량을 늘리는 공식은 다음과 같다.
int prefLength = oldCapacity + Math.max(minCapacity - oldCapacity, oldCapacity >> 1);공식에 따라 기존 용량의 1.5배를 늘린다. 만일 기본 용량인 10이고 사이즈가 10인 경우 prefLength는 10 + Math.max(11 - 10, 5)이므로 10 + 5가 되어 15만큼 늘어난다. 용량을 늘린 후에는 기존 배열의 데이터를 새로운 배열에 복사하고 값을 ArrayList에 추가한다.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}add 메서드의 매개변수로 인덱스와 값을 같이 집어넣는 경우 해당 인덱스가 접근 가능한 범위인지 확인하고 용량을 늘린다. 그리고 arraycopy 메서드를 호출해 기존 배열에서 새로운 값이 들어갈 공간을 확보한 새로운 배열을 만든다. 즉 기존 값은 한칸 씩 뒤로 이동한다. 그리고 빈 공간에 값을 추가한다.
1.4. 삭제
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
}ArrayList에 값을 삭제할 때는 remove 메서드를 호출한다. remove 메서드는 삭제할 값이 있는지 확인하고 없으면 false를 반환한다. 만일 삭제할 값이 있으면 arraycopy 메서드를 호출해 기존 배열에서 삭제할 값의 공간을 없애고 새로운 배열을 만든다. 즉 기존 값은 한칸 씩 앞으로 이동한다. 그리고 기존 배열의 마지막 값을 null로 만든다.
2. LinkedList
LinkedList는 List 인터페이스를 구현한 컬렉션이다. ArrayList는 데이터를 집어넣는 순서대로 저장하지만, LinkedList는 데이터를 연결하는 순서대로 저장한다.
2.1. 기본 설정
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
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는 값을 Node 객체로 저장한다. Node는 값과 자신의 이전&이후 Node를 저장한다.
2.2. 생성
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
}LinkedList는 LinkedList 내부 코드에서 정의한 두 개의 생성자로 생성할 수 있다.
빈 값으로 생성
다른 컬렉션을 복사해서 생성
2.3. 추가
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
}LinkedList에 값을 추가할 때는 add 메서드를 호출한다. add 메서드는 만일 index가 있을 경우 해당 index에 값이 있는지 확인하고 없는 경우 IndexOutOfBoundsException을 발생시킨다. 그리고 index와 List의 크기를 비교해서 index가 사이즈와 같으면 linkLast, 사이즈와 다르면 linkBefore를 호출한다. linkLast와 linkBefore은 새로운 Node 객체를 생성하고 기존의 Node 객체와 연결한다. 만일 LinkedList의 맨 앞에 추가하는 경우 추가한 값이 first가 된다. node 함수는 추가할 값의 노드가 어디 있는지 탐색한다. 탐색은 전체 node 사이즈에서 절반을 나눈 값과 index를 비교해 index가 작은 경우 앞에서부터 탐색하고 index가 큰 경우 뒤에서부터 탐색한다.
2.4. 삭제
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null;
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
}LinkedList에 값을 삭제할 때는 remove 메서드를 호출한다. 매개변수가 없을 경우 remove 메서드는 removeFirst 메서드를 호출한다. removeFirst 메서드는 첫 번째 Node 객체를 찾고 없을 경우 NoSuchElementException을 발생시킨다. 객체가 있을 경우 unlinkFirst 메서드를 호출한다. unlinkFirst 메서드는 삭제할 Node의 연결을 해제하고 null로 만든다. 삭제한 값을 반환한다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
}매개변수로 index를 넣을 경우 remove 메서드는 해당 index에 Node 객체가 있는지 확인하고 없으면 IndexOutOfBoundsException을 발생시킨다. Node가 있으면 unlink 메서드를 호출한다. unlink 메서드는 unlinkFirst 메서드와 마찬가지로 삭제할 Node의 연결을 해제하고 null로 만든 뒤 기존 Node를 재연결한다.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
}매개변수로 삭제할 값을 넣을 경우 remove 메서드는 값을 검사한 후 unlink 메서드를 호출한다.
3. LinkedList와 ArrayList
ArrayList와 LinkedList의 추가 삭제를 간단히 나타내면 다음과 같다.
ArrayList는 리스트의 중간 위치에 값을 추가(삭제)하는 경우 공간을 확보하기 위해 값을 한 칸 씩 앞(뒤)로 이동해야 한다. 반면에 LinkedList는 리스트의 중간 위치에 값을 추가(삭제)하는 경우 추가(삭제)할 값과 기존의 Node를 재연결하기만 하면 된다. 따라서 LinkedList는 ArrayList에 비해 추가와 삭제에 이점이 있다. 단, 배열의 마지막에 값을 추가하거나 삭제하는 경우 이동이 필요없으므로 LinkedList와 큰 차이가 없다. 반면에 LinkedList는 index로 값을 조회하는 경우 전체 Node를 앞 혹은 뒤에서 탐색해야 한다. 반면에 ArrayList는 index로 값을 탐색하는 경우 바로 해당 값을 찾을 수 있다. 그래서 ArrayList는 조회에 이점이 있다. 단, LinkedList는 첫 번째 값과 마지막 값을 저장하므로 해당 값을 조회하는 경우 바로 값을 반환할 수 있어 ArrayList와 큰 차이가 없다.
Last updated