[Java 파헤쳐보기] ArrayDeque와 LinkedList

 이번 포스팅에서는 JCF에서 LinkedList와 ArrayDeque가 어떻게 구현되어 있는지 살펴보겠습니다.

 

1.  ArrayDeque

개념

 

 Deque는 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미합니다.

 

그리고 이 Deque 인터페이스를 구현하는 클래스가 ArrayDeque입니다. 

 

JCF에서 어떻게 구현되어 있나?

  elements와 head, tail

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{

    transient Object[] elements; // non-private to simplify nested class access

    transient int head;

    transient int tail;
    
    ...

 

 

JCF에서 ArrayDeque를 들여다보면, 우선 배열의 형태로 요소(elements)를 구성하는 것을 확인 할 수 있습니다.

 

그리고 head와 tail이라는 int 형 인덱스를 통해, deque의 시작 부분과 끝 부분을 나타내는 것을 볼 수 있습니다.

 

 

  기본 할당 사이즈

public ArrayDeque() {
    elements = new Object[16];
}

 

생성자를 통해 기본 할당 값은 16으로 받는 것을 볼 수 있습니다.

 

  최소 할당 사이즈

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

 

 만약 생성자에 사이즈를 지정한다면, 아래와 같은 과정을 거치게 됩니다.

 

private static final int MIN_INITIAL_CAPACITY = 8;

    // ******  Array allocation and resizing utilities ******

    private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    private void allocateElements(int numElements) {
        elements = new Object[calculateSize(numElements)];
    }

 

MIN_INITIAL_CAPACITY라는 변수를 통해 최소 할당 사이즈 값을 8로 할당하는 모습을 볼 수 있습니다. 

 

 allocateElements() 메서드를 통해, Object[] 배열의 크기를 calculateSize()메서드를 통해 지정하는데, 이 메서드는 요소의 개수를 기반으로 배열의 크기를 계산합니다. 

 

 초기 용량은 MIN_INITIAL_CAPACITY 로 설정됩니다. 이 메서드는 요소의 개수가 초기 용량보다 큰 경우, 요소의 개수를 기반으로 적절한 크기를 계산하는데, 이때 계산된 크기는 항상 2의 제곱수가 되도록 조정되는 것을 볼 수 있습니다.

 

 

  addFirst() 메서드를 통해 추가적인 특징 알아보기

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

 

 addFirst 메서드를 들여다보면 우선 Null값을 허용하지 않는 것을 볼 수 있습니다. Null값이 들어오면 NullPointerException을 터트립니다.

 

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

 

 그리고 head와 tail 인덱스를 통해 배열 요소를 관리하는데, 이 때, 요소를 추가할 때 용량이 부족하면 doubleCapacity 메서드를 통해 배열의 크기를 두 배로 늘리는 것(int newCapacity = n <<1;)을 볼 수 있습니다.

 

  pollFirst() 메서드

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

 

pollFirst() 메서드를 살펴보면, 값을 제거할 때 해당 요소를 null 값으로 설정하는 것을 볼 수 있고, deque의 시작 인덱스인 head를 업데이트하여 다음 요소를 가리키도록 하는 것을 볼 수 있습니다.

 

 이처럼 ArrayDeque는 배열을 기반으로, head와 tail 인덱스를 통해 동작하는 것을 볼 수 있습니다.

 

 

주요 특징 정리

ArrayDeque의 주요 특징을 정리하면 아래와 같습니다.

---

1. 배열의 형태이다.

2. head와 tail 인덱스를 통해 deque의 시작과 끝을 가르킨다.

3. 기본 할당 크기는 16이고, 최소 크기는 8이다.

4. 용량을 늘릴 때는 2배로 늘린다. 크기는 2의 제곱 수로 설정된다.

5. null 값을 허용하지 않는다.

---

 

 

 

 

 

2. LinkedList

출처 : https://suyeon96.tistory.com/27

 

 LinkedList는 자료의 주소 값으로 서로 연결되어있는 구조입니다. 내부적으로 양방향의 연결리스트로 구현되어있습니다. 

 

 

JCF에서 어떻게 구현되어 있나?

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

  elements

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 클래스로 구성되어있습니다.

 

transient int size = 0;

 

그리고 기본 할당 사이즈는 0인 것을 알 수 있습니다. 

 

  addFirst() 메서드를 통해 추가적인 특징 알아보기

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> new Node = new Node<>(null, e, f);
    first = new Node;
    if (f == null)
        last = new Node;
    else
        f.prev = new Node;
    size++;
    modCount++;
}

 

우선 LinkedList와는 다르게 Null 요소를 추가할 수 있습니다.

 

그리고 인덱스를 사용하는 것이 아닌, 노드를 추가함으로써 크기를 설정하는 것(size++) 을 볼 수 있습니다.

 

그래서 매 연산마다 노드를 사용하기 때문에, 메모리 사용량이 비교적 높다는 것이 특징입니다.

 

 

 

3. ArrayDeque와 LinkedList 차이 비교

 두 클래스의 차이를 비교해보면,  ArrayQueue가 첫 번째와 마지막 원소를 삽입/삭제하는 자료구조인 Deque의 특성에 최적화된 것을 알 수 있습니다. 내부의 int 형 index만 변화시키면서, 포인터처럼 데이터를 관리하기 때문에 LinkedList보다 빠르고, 메모리도 적게 쓰는 것을 볼 수 있습니다. 

 

 그리고 LinkedList에는 Null 요소를 추가할 수 있지만, ArrayDeque는 불가능한 것을 확인할 수 있었습니다.

 

 

 실제로 속도 차이가 얼마나 나는지 테스트를 해보았습니다.

 

 

코드

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class test3 {

    public static void main(String[] args) {
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        long arrayDequeStart = System.currentTimeMillis();
        for(int i = 0;i<10000000;i++){
            arrayDeque.addFirst(i);
        }
        long arrayDequeEnd = System.currentTimeMillis();
        long arrayDequeTime = arrayDequeEnd-arrayDequeStart;
        System.out.println("arrayDequeTime: "+arrayDequeTime+"ms");

        Deque<Integer> linkedList = new LinkedList<>();
        long linkedListStart = System.currentTimeMillis();
        for(int i = 0;i<10000000;i++){
            arrayDeque.addFirst(i);
        }
        long linkedListEnd = System.currentTimeMillis();
        long linkedListTime = linkedListEnd-linkedListStart;
        System.out.println("linkedListTime: "+linkedListTime+"ms");
    }
}

 

arrayDeque가 빠른 것을 확인할 수 있습니다.

 

 

그럼 어떤 걸 써야할까 ??

각각의 상황에 따라 판단해서 사용해야합니다. 여러 포스팅을 통해 정리해본 것은 아래와 같습니다.

ArrayList

 인덱스로 데이터에 접근하고 끝에 삽입 및 삭제만 필요한 경우에는 ArrayList를 사용하는 것이 적합합니다.

 

 ArrayList는 내부적으로 배열을 사용하여 요소에 접근하기 때문에 인덱스로 빠르게 접근할 수 있습니다. 또한 요소의 삽입과 삭제가 끝에서 발생하는 경우에 효율적입니다. 

 

ArrayDeque

스택(Stack), 큐(Queue), 혹은 덱(Deque)의 기능이 필요한 경우에는 ArrayDeque를 사용하는 것이 좋습니다. ArrayDeque는 배열 기반이기 때문에, 요소의 추가와 삭제가 빈번하게 발생하는 경우에도 높은 성능을 보이기 때문입니다. 특히 스택과 큐의 기능을 동시에 사용해야 하는 경우에도 적합합니다.

 

LinkedList

 리스트를 순회할 때 요소의 삽입, 삭제가 빈번하게 발생하거나 O(1)인 최악의 경우에 요소를 리스트의 끝에 삽입해야 하는 경우에는 LinkedList를 사용하는 것이 좋습니다. LinkedList는 각 요소가 이전 요소와 다음 요소를 가리키는 링크로 구성되어 있어 요소의 삽입 및 삭제가 빠르게 수행되기 때문입니다. 또한 리스트의 끝에 요소를 삽입하는 경우에도 O(1)의 시간 복잡도를 가집니다.

 

 

 

 

 

참고자료

https://tech-monster.tistory.com/159

https://velog.io/@djawnstj/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Java%EC%9D%98-LinkedList%EC%99%80-ArrayDeque

https://velog.io/@jongmee/%ED%9A%8C%EA%B3%A0-%EC%9A%B0%ED%85%8C%EC%BD%94-%EB%B0%B1%EC%97%94%EB%93%9C-6%EA%B8%B0-Level-1

https://velog.io/@wlsgur1533/ArrayDeque-%EA%B8%B0%EB%B0%98%EA%B3%BC-Linked-list%EA%B8%B0%EB%B0%98-%EB%B0%A9%EC%8B%9D%EC%9D%98-Queue-%EA%B5%AC%ED%98%84%EC%B2%B4%EC%9D%98-%ED%8A%B9%EC%A7%95-%EB%B0%8F-%EC%84%A0%ED%83%9D-%EA%B8%B0%EC%A4%80