ArrayList와 LinkedList는 언제 쓰면 좋을까?

자바에서 데이터를 담는 자료구조는 크게 네가지로 구분할 수 있습니다.

• List : 순서가 있는 목록
• Set : 순서가 중요하지 않은 목록
• Queue : 선입선출
• Map : key-value 형태

오늘은 순서가 있는 목록인 List 인터페이스를 구현한 ArrayList와 LinkedList를 자세히 비교해 보겠습니다.

우선 List 자료형에 ArrayList와 LinkedList는 어떤 상황에서 쓰기 좋을지 생각을 해봅시다
ArrayList는 내부가 배열로 구현되어 있고, LinkedList는 연결리스트로 구현되어 있습니다.

ArrayList

ArrayList를 생성하는 코드를 살펴보겠습니다.

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 = {};

    transient Object[] elementData; // 실제 데이터 배열
    private int size;

    public ArrayList() {
        this.elementData = EMPTY_ELEMENTDATA;
    }
    ...

transient Object[] elementData;

여기서 배열을 선언하는 것을 볼 수 있습니다.

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient Node<E> first; // 첫 번째 노드
    transient Node<E> last;  // 마지막 노드
    transient int size = 0;

    public LinkedList() {
    }

    ...

LinkedList이 구현된 코드를 살펴보면 LinkedList는 노드를 통해 앞 뒤를 연결하는 것을 확인할 수 있습니다.

 

---

연속된 데이터 저장 형태인 배열과, 노드로 연결되어 연결 리스트를 만드는 것은 어떤 상황에서 장점을 가지고 단점을 가지는지 비교해보겠습니다.

대표적으로 접근 시간과 list에 요소를 추가/ 삭제할 때 차이를 보입니다.

접근 시간

ArrayList:
요소에 접근할 때 인덱스를 이용하여 바로 접근할 수 있어 O(1)의 시간 복잡도를 가집니다.

 

LinkedList:
요소에 접근할 때 첫 번째 노드부터 순차적으로 찾아가야 하므로 O(n)의 시간 복잡도를 가집니다.

요소 추가/삭제 시간

ArrayList:
중간에 요소를 추가하거나 삭제하는 경우, 해당 인덱스 이후의 요소들을 모두 이동시켜야 하므로 시간이 더 걸릴 수 있습니다.

시간 복잡도는 O(n)입니다.

 

LinkedList:
노드의 참조만 변경하면 되므로 중간에 요소를 추가하거나 삭제하는 경우에도 빠릅니다. 시간 복잡도는 O(1)입니다.

 

 

따라서, ArrayList는 요소에 빠르게 접근해야 하는 경우나 크기가 변경되지 않거나 변경이 적은 경우에 유리하고,
LinkedList는 중간에 요소를 자주 추가하거나 삭제해야 하거나 크기가 동적으로 변경되는 경우에 유리합니다.