ArrayList & LinkedList

ArrayList vs LinkedList

🚞  ArrayList

• ArrayList는 기본적으로 배열을 사용하지만 일반 배열과 차이점이 존재한다.

• 일반 배열은 처음에 메모리를 할당할 때 크기를 지정해 주어야 하지만 ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.
• 하지만 실제로 배열의 크기가 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다.
• 내부 코드를 보게되면 Arrays.copyOf()를 통해서 배열을 옮기는 과정에서 원소의 수가 적으면 큰 문제가 없겠지만 원소의 수가 많으면 시간도 많이 소모되며 효율적이지 못합니다.

ArrayList의 시간복잡도

• get() : O(1)

• add() : O(1)

• remove: O(n)

ArrayList의 조회

• 데이터는 각각 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한번에 가져올 수 있다.

ArrayList의 삽입과 삭제

• 데이터 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰줘야 한다.

• 예를들어 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 네개는 앞으로 한칸씩 이동해야 하며 중간에 데이터를 삽입하는 과정도 이와 비슷하다.

• 만약 삽입과 삭제가 많다면 ArrayList를 사용하는 것은 효율적이지 못하다.

📎 LikedList

• LinkedList는 내부적으로 양방향의 연걸리스트로 구성되어 있으며 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회가 가능하다.

• 배열의 단점을 보완하기 위해서 LinkedList가 고안되었다.

LinkedList의 시간복잡도

• get() : O(n)

• add() : O(1) amortized

• remove() : O(n)

LinkedList의 조회

• LinkedList는 순차적 접근이기 때문에 검색속도는 느리다.

LinkedList의 삽입과 삭제

• 데이터를 추가, 삭제시 가리키고 있는 주소값만 변경해주면 되기 때문에 ArrayList에 비해서 상당히 효율적이다.

• 예를 들어 4번째 값을 삭제한다면 3번째 값은 5번째 노드를 가리키게만 하면 된다.

• 삽입 삭제가 많을 경우에는 LinkedList가 효율적이다

👀  성능 실험해보기

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + addl(al));
        System.out.println("LinkedList : " + addl(ll));
        System.out.println();
        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LinkedList : " + add2(ll));
        System.out.println();
        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LinkedList : " + remove2(ll));
        System.out.println();
        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList : " + remove1(al));
        System.out.println("LinkedList : " + remove1(ll));
    }

    public static long addl(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(i+"");
        }

        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long add2(List list) {
        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000; i++) {
            list.add(500, "X");
        }

        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long remove1(List list) {
        long start = System.currentTimeMillis();

        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }

        long end = System.currentTimeMillis();
        return end - start;
    }

    public static long remove2(List list) {
        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000; i++) {
            list.remove(i);
        }

        long end = System.currentTimeMillis();
        return end - start;
    }
}

• 순차적으로 데이터를 추가 및 삭제하는 경우에는 배열 원소들이 이동하는 일이 없기 때문에 ArrayList가 더 효율적인 모습을 확인할 수 있습니다. LinkedList의 경우는 순차적으로 추가하면 추가하고자 하는 곳으로 계속해서 탐색을 하는 과정에서 조금 더 오래걸리는 모습을 보이지만 큰 차이는 나지 않는 모습을 확인할 수 있었습니다.

• 중간에 데이터를 추가하거나 삭제하는 경우에는 ArrayList의 경우 데이터를 해당 위치 전 후로 나눠 공간을 확보하는 작업을 하거나 원소들이 이동하는 작업이 발생하기 때문에 처리속도가 느리지만 LinkedList의 경우 요소간의 연결만 변경해주면 되기 때문에 더 효율적인 모습을 확인할 수 있습니다.

🧑🏻‍⚖️  결론

• 소량의 데이터를 가지고 사용할 경우에는 큰 차이를 보이진 않지만, 정적인 데이터를 활용하면서 조회할 일이 많다면 ArrayList를 사용하는 것이 효율적이고 동적으로 추가/삭제 요구사항이 많다면 LinkedList를 사용하는것이 더 효율적이다.