ArrayDeque vs LinkedList

Expression 의 SepartorDeque의 요소와 OperandDeque의 요소가 모두 일치하는 객체는 같은 객체라고 판단한다
Expression의 상태는 외부에서 변경할수 없으며 상태 변경 요청시 새로운 Expression을 반환한다

 

이런 Expression 객체가 있다고 생각해보자

이녀석을 생성하기 위해선 Deque<>를 생성자에 넣어주어야 한다.

Deque는 ArrayDeque와 LinkedList 두가지로 모두 선언 할 수 있는데 어떤 것을 써야 할까?

 

먼저 LinkedList를 알아보자

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
...

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
...
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
...

LinkedList는 List와 Deque을 구현하고 AbstractList를 상속받는 형태로 구현되어 있다.

즉 이녀석은 이름에서도 알 수 있듯이 List이고 ArrayList에 비하면 가족관계가 좀 복잡하다.

 

반면 ArrayDeque은 가족관계가 꽤나 간단하다

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

ArrayDeque은 그냥 Deque을 구현한 collection이라 보면 된다.

 

 

 

이제 Expression의 관점에서 생각해보자

Expression 이 가지고 있는 두가지 collection( operand, separator)안의 요소가 같다면 같은 Expression이라고 판단해야 한다.

 

이라는 기능을 구현해야 할 때 어떻게 할 수 있을까?

 

LinkedList가 상속하고 있는 AbstractList<>에서 equals는 다음과 같이 동작한다.

LinkedList 자체는 따로 equals를 오버라이딩 하지 않는다.

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
...
public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }
...

 

즉 컬렉션 내의 요소가 같다면 같은 객체로 취급하는 셈.

즉 Deque 인터페이스가 아닌 LinkedList<>를 직접 사용하면 equals를 쉽게 사용할 수 있다.

 

반면 Deque<>의 구현체중 하나인 ArrayDeque<>은 따로 equals를 오버라이딩 하지 않는다. 그렇기 때문에 따로 equals를 오버라이딩 하여 요소하나한를 확인해야 하는 셈.

 

지금까지는 Deque이 아닌 LinkedList자체를 필드로 쓰는 것이 편해보인다. 이것이 좋은 것일까?

private final LinkedList<Operand> operandList;
private final LinkedList<Separtor> separatorList;

 

 

이제 ArrayDeque과 LinkedList에 대해 조금 더 살펴보도록 하자

비교항목	ArrayDeque	LinkedList
내부 구조	배열 (원형 배열)	이중 연결 리스트
접근 시간	양 끝 삽입/삭제 O(1), 중간 O(n)	양 끝 삽입/삭제 O(1), 중간 삽입/삭제 O(1), 중간 접근 O(n)
메모리 효율성	메모리 오버헤드 적음	추가 메모리 사용 (노드 생성 및 포인터)
중간 삽입/삭제 성능	비효율적 (배열 이동이 필요, O(n))	효율적 (연결 변경만으로 가능, O(1))
크기 제한	동적으로 배열 확장 (무한정 커질 수 있지만, 배열 재할당 필요)	동적으로 노드 추가 (크기 제한 없음)

 

LinkedList는 ArrayDeque에 비해 속도가 느리다. 이중연결 리스트이므로 새롭게 객체를 할당할 때 ArrayDeque보다 느릴수 밖에 없다. 또한 Expression객체를 봤을때 자료구조의 중간에 새로운 Operand나 Separator를 삽입 할 필요가 없다. 즉 중간 삽입이 가능하지만 비용이 비싼 LinkedList를 굳이 쓸 필요가 없는 것이다.

LinkedList가 편한 것은 단지 equals를 그대로 가져다가 쓸 수 있다는 것 하나 뿐이다.

 

그렇다면 Expression은 LinkedList를 필드로 갖는 것이 아닌 ArrayDeque으로 갖고 있는게 맞다.

당연한 이야기일수도 있다. 애초에 Expression객체가 Deque을 사용하는 것도 중간삽입 연산이 필요하지 않았기 때문.

 

Deque을 LinkedList로 선언하면 비용이 비싸고 쓸수없는 기능도 생긴다. 그럼 도대체 왜 그런 기능이 있을까?

 

LinkedList는 ArrayDeque에 비해 Deque을 만들기에는 안좋아 보인다. LinkedList의 가장 큰 장점 중 하나인 중간 삽입도 Deque을 통해 선언하면 사용할 수 없다. 그렇다면 도대체 왜 Deque<> deque = new LinkedList<> 형식으로 생성되게 만들었을까? 언제 Deque을 LinkedList를 통해 생성해야 할까?

 

ArrayDeque을 살펴보자

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

ArrayDeque (Java Platform SE 8 )

ArrayDeque()
Constructs an empty array deque with an initial capacity sufficient to hold 16 elements.

ArrayDeque의 초기 크기는 16이다. 즉 LinkedList와는 다르게 capacity가 존재하는 녀석이다.

 

ArrayDeque은 그 크기가 모두 할당되면 grow 라는 메서드를 통해 용량을 늘리는데 다음과 같이 동작한다.

ArrayDeque내의 grow메서드

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
...
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int needed) {
        // overflow-conscious code
        final int oldCapacity = elements.length;
        int newCapacity;
        // Double capacity if small; else grow by 50%
        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
        if (jump < needed
            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
            newCapacity = newCapacity(needed, jump);
        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
        // Exceptionally, here tail == head needs to be disambiguated
        if (tail < head || (tail == head && es[head] != null)) {
            // wrap around; slide first leg forward to end of array
            int newSpace = newCapacity - oldCapacity;
            System.arraycopy(es, head,
                             es, head + newSpace,
                             oldCapacity - head);
            for (int i = head, to = (head += newSpace); i < to; i++)
                es[i] = null;
        }
    }
    
    /** Capacity calculation for edge conditions, especially overflow. */
    private int newCapacity(int needed, int jump) {
        final int oldCapacity = elements.length, minCapacity;
        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
            if (minCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            return Integer.MAX_VALUE;
        }
        if (needed > jump)
            return minCapacity;
        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
            ? oldCapacity + jump
            : MAX_ARRAY_SIZE;
    }
    ...

 

배열 크기가 64보다 작으면 기존 크기에 2를 더한 값으로 확장한다 
배열 크기가 64 이상이면 기존 크기의 50%만큼 증가시킨다.

 

즉 capacity가 다 찬다면 grow가 호출되며  새로운 배열을 할당하여 기존 데이터를 복사하는 과정이 필요하다.

deque의 사이즈가 계속해서 커진다면 오버헤드가 생기는 셈.

 

반면 LinkedList같은 경우 여러 Node들로 이루어져있어 cpacity라는 것이 없다. 그저 노드를 생성하고 이를 연결하는게 Array에 비해 느릴 뿐.

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

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;
...

 

Deque을 선언할때 LinkedList와 ArrayDeque의 가장 큰 차이는 capacity의 존재 유무이다. 

Deque의 요소가 계속해서 증가해야 한다면 오히려 ArrayDeque이 요소들을 복사하고 재할당하는 때 LinkedList보다 오버헤드가 더 커질 수 있다. 

 

 

다시 Expression으로 돌아가서 expression의 요구사항을 보자.

Expression의 상태는 외부에서 변경할수 없으며 상태 변경 요청시 새로운 Expression을 반환한다

 

Expression의 크기는 계속 증가 할 수 있다. 그러나 크기가 증가하는 과정에서 새로운 Expression을 반환하므로 Deque내부의 요소들은 다시 복제되어야 한다.(deep copy) 

그렇기 때문에 생성된 deque에 요소를 추가하는 것이 아닌 새로운 녀석을 복제해야 하므로 LinkedList의 장점이었던 요소 증가시 낮은 오버헤드는 소용이 없다. 요소를 조회하고 복제하는 것은 오히려 ArrayDeque이 빠르니깐.

 

결국 결론은 Expression 객체는 ArrayDeque을 사용해야 한다는 것.

Deque<Separtor> separatorDeque = new LinkedList<>();
Deque<Operand> operandDeque = new LinkedList<>();
Expression expression = new Expression(separatorDeque, operandDeque);

그리고 함부로 LinkedList를 사용하지 못하게 막을 것이다. LinkedList의 장점이 1도 없으므로....

ArrayDeque은 기본적으로 Objects.equals()를 오버라이딩 하지않아서 Deque내의 요소가 같다면 equals를 true로 반환하는 equals()를 새로 만들어주어야 한다. 대신 contains라는 메서드를 통해 요소비교는 가능한데

public boolean contains(Object o) {
        if (o != null) {
            final Object[] es = elements;
            for (int i = head, end = tail, to = (i <= end) ? end : es.length;
                 ; i = 0, to = end) {
                for (; i < to; i++)
                    if (o.equals(es[i]))
                        return true;
                if (to == end) break;
            }
        }
        return false;
    }

ArrayDeque이 가지고 있는 녀석이 equals를 오버라이딩한 객체(예를들면 값객체 - VO)면 편하게 확인할수 있다.

 

그래석 결국 CustomDeque을 만들어 Expression에서 사용하게 하였다.

public class CustomDeque<T extends ValueObject> extends ArrayDeque<T> {
   ...

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Deque<?> that)) return false;
        return this.size() == that.size() && this.containsAll(that);
    }
    ...

public abstract class ValueObject {
    @Override
    public abstract boolean equals(Object o);

    @Override
    public abstract int hashCode();
}

 

이제 요구사항을 만족하면서 조금 더 효율적인 Expression이 탄생하였다.

결론

Deque 생성 시 LinkedList와 ArrayDeque로 생성이 가능하다.

Deque에서 이 둘의 가장큰 차이는 capacity의 여부이다.

일반적으로는 ArrayDeque의 성능이 더 좋으나 Deque의 크기가 계속해서 증가하는 놈이라면 LinkedList도 고려해볼만 하다.