[자료구조] ArrayList vs LinkedList

 

Java에서 List 인터페이스를 사용할 때 대표적으로 쓰이는 클래스가 ArrayList와 LinkedList 입니다.

두 클래스의 특성과 어떠한 차이가 있는지 알아보겠습니다.

 

ArrayList

1. 내부 구조

• 배열을 사용하여 구현합니다.

2. 추가, 삭제, 조회

• 인덱스 기반으로 데이터에 접근 가능합니다.
• 요소가 추가될 때마다 배열의 크기를 동적으로 조절한 후 새로운 요소를 추가합니다.

3. 메모리 사용

• 내부 배열의 크기를 늘리거나 줄일 때마다 새로운 배열을 할당한 후 기존 배열을 복사해야 합니다.
• 따라서 메모리 사용이 불규칙해질 수 있습니다.

 

LinkedList

1. 내부 구조

• 노드들의 연결 리스트로 구현되어 있습니다.
• 각 요소는 링크로 연결되어 있으며, 새로운 요소를 추가할 때마다 새로운 노드를 만듭니다.

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

 

2. 추가, 삭제, 조회

• 인덱스 기반으로 데이터에 접근할 수 없습니다.
• 검색 속도가 느리지만 요소를 삽입하거나 삭제하는 경우 연결 리스트의 노드를 재구성하는 것이 더 쉬울 수 있습니다.

3. 메모리 사용

• 요소를 추가 또는 삭제할 때마다 노드를 만들고 제거합니다.
• 따라서 메모리 사용이 많이 필요합니다.

 

ArrayList vs LinkedList

• ArrayList는 배열 기반이기 때문에, 조회를 자주 해야 하는 경우 유리하다.
• LinkedList는 삽입과 삭제의 작업이 빈번하게 일어나는 경우 유리하다.

 

---

 

ArrayList vs Array(배열)

• 두 자료구조 모두 배열 기반이기 때문에 성능은 비슷하다.(ArrayList가 살짝 더 느림)
• Array는 정적인 크기, ArrayList는 동적인 크기(수동)
• ArrayList는 처음에는 0의 크기, 선언 시 10의 크기인 배열로 이루어짐
• ArrayList에서 더 큰 배열이 필요할 시 현재 크기의 50% 증가된 배열로 교체

 

 

ArrayList vs HashMap

• 조회에 관해서는 둘다 시간복잡도는 O(1)의 빠른 시간복잡도를 가짐
• 하지만 데이터에 접근하는 물리적인 시간은 ArrayList 리스트가 더 빠름
• List에 없는 Map의 기능을 활용할 게 아니라면 ArrayList가 속도에서 유리