Hanbit the Developer

[Java] ArrayList, LinkedList Implementation 본문

Java

[Java] ArrayList, LinkedList Implementation

hanbikan 2024. 3. 25. 12:04

배경

Java에서 List의 대표적인 구현체인 ArrayList와 LinkedList의 구현을 알아보겠습니다.

ArrayList

ArrayList는 MutableList의 기본 구현체이다.

코틀린에서 mutableListOf() 함수를 사용하면 ArrayList가 기본 구현체로서 반환됩니다.

/**
 * Returns an empty new [MutableList].
 * @sample samples.collections.Collections.Lists.emptyMutableList
 */
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> mutableListOf(): MutableList<T> = ArrayList()

 

@SinceKotlin("1.1") public actual typealias ArrayList<E> = java.util.ArrayList<E>

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // ...
}

여기서 MutableList를 구현하지 않은 자바의 ArrayList가, 어떻게 코틀린의 MutableList의 구현체로 올 수 있는지 의문이어서 GPT와 Q&A를 해보았습니다.

Q&A with GPT 4.0

Q: ArrayList가 MutableList를 구현하지 않는데 어떻게 MutableList의 구현체로 제공될 수 있는 것인가?

A: Kotlin에서 ArrayList가 MutableList 인터페이스의 구현체로 나오는 것은 Kotlin의 타입 시스템과 자바의 컬렉션 프레임워크 간의 상호 운용성 때문입니다. Kotlin은 자바 플랫폼 위에서 동작하므로, 자바의 컬렉션을 Kotlin에서 직접 사용할 수 있도록 설계되었습니다. 그 과정에서 Kotlin은 자신만의 컬렉션 인터페이스를 제공하는데, 이는 기본적으로 자바의 컬렉션 인터페이스에 대응되도록 설계되었습니다.

Q: 코드만으로는 상호 운용성이 어떻게 구현됐는지 알 수 없는 것인가?

네, 맞습니다. 단순히 코드를 보고서는 ArrayList가 MutableList 인터페이스의 구현체로 어떻게 동작하는지 직접적으로 알 수 없습니다.

Kotlin과 자바 사이의 이러한 연결은 주로 Kotlin 컴파일러와 런타임에서 처리됩니다. Kotlin 컴파일러는 Kotlin 코드를 컴파일할 때 Kotlin의 컬렉션 타입을 자바의 컬렉션 타입으로 변환하거나 매핑하는 규칙을 적용합니다. 이 과정에서 mutableListOf() 함수가 반환하는 ArrayList 인스턴스는 MutableList<T> 타입으로 사용될 수 있게 됩니다. 이러한 타입 변환과 매핑은 컴파일 시간에 정의되며, 실행 시간에 Kotlin과 자바 코드 간의 원활한 상호 작용을 보장합니다.

Implementation

이제 본격적으로 구현을 알아보겠습니다.

add(E e)

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

/**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
 */
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);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
 */
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}
  • modCount: 리스트에 아이템이 추가되거나 제거되는 등 ‘구조적 변경’이 발생한 횟수입니다. iterator에서 아이템을 순회하다가 중간에 이 값이 바뀌면 ConcurrentModificationException를 던지는 식으로 활용됩니다.
  • grow(): 리스트가 꽉 찼을 경우 호출하여 리스트의 크기를 늘립니다. 기존 리스트가 비어있지 않은 경우 사이즈가 증가된 복사본을 생성하고, 비어있는 경우 빈 array를 생성합니다.
  • 추가된 공간에 원소를 넣습니다.
  • 시간 복잡도: 리스트에 여유 공간이 있을 경우에는 O(1), 그렇지 않은 경우에는 O(N)

remove(Object o)

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * {@code Objects.equals(o, get(i))}
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
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 remove method that skips bounds checking and does not
 * return the value removed.
 */
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;
}
  • 찾고자 하는 아이템의 인덱스를 찾습니다.
  • fastRemove(): arraycopy() 함수로 아이템을 제거한 리스트의 복사본을 생성하여 적용합니다.
  • 시간 복잡도: O(N)

결론

변경을 할 수는 있으나 변경 시 시간 복잡도가 O(N)이므로 변경에 잦을 때 불리한 구현체입니다.

LinkedList

Implementation

기본 구현

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;
    
    // ...
    
    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;
        }
    }
    
    // ...
}

addFirst(E e)

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
  • 삽입할 값에 대한 Node(newNode)를 생성하고 first로 설정합니다.
  • 기존에 리스트가 비어있는 경우, last 또한 newNode로 설정합니다. 그렇지 않은 경우, f.prev를 newNode로 설정합니다.(newNode ← first)
  • size를 증가시킵니다.
  • 시간 복잡도: O(1)*addLast()도 같은 방식입니다.

*addLast()도 같은 방식입니다.

removeFirst()

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

 /**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
  • f를 null 처리하여 GC를 유도하고 first를 next로 옮깁니다.([f → next] ⇒ [null … next(first)])
  • first를 지움으로써 리스트가 비워진 경우, last도 null로 설정합니다. 그렇지 않은 경우, next.prev로 null을 설정합니다.
  • size를 감소시킵니다.
  • 시간 복잡도: O(1)

*removeLast()도 같은 방식입니다.

add(int index, E element)

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

/**
 * Inserts element e before non-null Node succ.
 */
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++;
}
  • index == size이면 linkLast()를 호출합니다.
  • 아닐 경우 linkBefore()를 호출합니다.
    • node(): 인덱스에 해당하는 아이템을 찾습니다. 이때 효율적인 탐색을 위해 index가 size의 절반보다 작을 경우 앞에서부터, 클 경우 뒤에서부터 찾습니다.
    • linkBefore(): succ가 첫번째 노드인 경우, 아닌 경우를 나누어 노드를 연결합니다.(pred(succ.prev) → newNode → succ)
  • 시간 복잡도: O(N)

remove(Object o)

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * {@code Objects.equals(o, get(i))}
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
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;
}

/**
 * Unlinks non-null node x.
 */
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;
}
  • 앞에서부터 o를 찾고 unlink()를 호출합니다. 아이템이 제거된 경우 true, 그렇게 못 한 경우 false를 반환합니다.
  • unlink(): [prev → x → next]를 [prev → next]로 언링크합니다. x가 첫 번째 노드거나 마지막 노드일 경우 처리를 해줍니다.
  • 시간 복잡도: O(N)
저작자표시 비영리

'Java' 카테고리의 다른 글

[Java] hashCode() Implementation  (0) 2024.03.25
'Java' Related Articles more