[Java] LinkedList 파헤쳐 보기
Java의 ArrayList의 실제 구현코드를 살펴보았던 이전 게시글에 이어서 LinkedList도 소스코드를 파헤쳐보자.
(참고: 2021.10.06 - [Language/Java] - [Java] ArrayList 파헤쳐 보기)
Doubly-linked list implementation of the List and Deque interfaces.
LinkedList는 이전/이후의 리스트와 연결되어 있는 구조이다. 이는 다음과 같은 특징을 가진다.
o element 갯수에 대해 정해진 limit 없음
o Reference Type만 가질 수 있음
o Thread Safe 하지 않음
ArrayList가 내부적으로 Object[]으로 이루어졌던거에 비해 LinkedList는 Node로 이루어져있다.
코드를 통해서 살펴보자.
o 인스턴스 변수
: LinkedList는 Deque 인터페이스를 구현하고 있는 양 방향 접근이 가능한 자료이다. ("double ended queue")
내부적으로 첫 노드를 가리키는 first Node와 마지막 노드를 가리키는 last Node를 가진다. 그리고 ArrayList와 동일하게 element 갯수를 의미하는 size 변수를 가진다.
transient int size = 0;
transient Node<E> first; // Pointer to first node.
transient Node<E> last; // Pointer to last node.
* Node class
: 내부에서 계속해서 쓰이는 Node는 다음과 같이 이전/이후 Node의 pointer와 item값을 가진다.
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;
}
}o 데이터 삽입
: List 인터페이스를 구현한 add()메서드는 데이터를 (1) 맨 뒤에 추가하거나, (2) index에 삽입하는 두가지 경우로 나뉜다.
중간에 삽입되는 (2)번의 경우를 살펴보면 내부적으로 linkBefore() 메서드가 호출된다.
newNode를 생성하여 삽입 전에 index 위치에 존재하던 node를 succ로, 해당 node의 prev를 pred로 값을 넣어준다. --> new Node<>(pred, e, succ)
pred의 next값을 newNode로 업데이트해준다.
LinkedList에 데이터가 하나 추가되었으므로 size++; 를 해준다.
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
}
코드보다도 그림으로 보면 쉽게 이해가 될 것이다.
o 데이터 삭제
: List 인터페이스의 remove(index) 메소드를 구현한 부분에서는 unlink(node) 를 호출한다.
index에 해당하는 node를 찾아 다음과 같이 연결을 해제한다.
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 이전 노드의 next와 x의 next를 연결
x.prev = null; // 연결해제된 x의 prev는 null
}
if (next == null) {
last = prev;
} else {
next.prev = prev; // 삭제하고자 하는 x 다음 노드의 prev와 x의 prev를 연결
x.next = null; // 연결해제된 x의 next는 null
}
x.item = null;
size--; // 사이즈 감소
modCount++;
return element;
}
모든 데이터를 삭제하는 clear() 메소드의 경우에는 모든 Node들을 순회하며 item, next, prev를 모두 null로 바꾼다.
o 데이터 탐색
: List 인터페이스 메소드를 구현한 get()은 ArrayList에서 데이터를 가져오는 것과는 큰 차이가 있다.
ArrayList의 경우 RandomAccess가 가능한 데이터 타입인데, LinkedList는 그렇지 않다. index를 통해 값을 바로 찾는 것이 불가능 하며 index 값을 앞 or 뒤에서 부터 이동시켜가며 해당 위치의 데이터를 찾아야만 한다.
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // index가 전체 사이즈/2보다 작으면 앞부터 탐색
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index가 전체 사이즈/2보다 크거나 같으면 뒤부터 탐색
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}즉, 총 n개의 데이터가 저장되어있다고 가정할 때 LinkedList에서는 최대 n/2번의 탐색이 발생하므로, ArrayList보다 비효율적임을 알 수 있다.
이를 통해 두 자료형을 서로 비교해서 생각해보자. LinkedList는 데이터의 삽입/삭제가 빈번하고 탐색이 적은 케이스에 ArrayList보다 더 유용하다.