Portfolio

ArrayList vs LinkedList 🚞 ArrayList ArrayList의 시간복잡도 ArrayList의 조회 ArrayList의 삽입과 삭제 📎 LikedList LinkedList의 시간복잡도 LinkedList의 조회 LinkedList의 삽입과 삭제 👀 성능 실험해보기 🧑🏻‍⚖️ 결론 📚 REF

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의 경우 요소간의 연결만 변경해주면 되기 때문에 더 효율적인 모습을 확인할 수 있습니다.