[JAVA] ArrayList vs LinkedList

ArrayList

Object배열을 이용해서 데이터를 순차적으로 저장한다.

 

크기를 변경할 수 없다.

배열에 더 이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장한다.  -> 이 과정에서 처리시간이 많이 소요되기 때문에 ArrayList를 생성할 때, 실제 저장할 개수보다 약간 여유 있는 크기로 지정하는 것이 좋다.

 

비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

 

공식문서

 

아래는 list2에서 list1과 공통되는 요소들을 삭제하는 코드다.

for문에서 변수i를 list2.size()-1 부터 감소시켜야 올바른 값을 얻을 수 있다.

 

import java.util.ArrayList;
public class Test {

    public static void main(String[] args) {
        ArrayList list1 = new ArrayList();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        
        ArrayList list2 = new ArrayList();
        list2.add(1);
        list2.add(4);
        list2.add(3);

        for (int i = list2.size()-1; i >= 0; i--) {
            if(list1.contains(list2.get(i))){
                list2.remove(i);
                System.out.println("list2: "+list2);
            }
        }
    }
}

 

실행결과:

list2: [1, 4]
list2: [1]
list2: []

 

for (int i = 0; i < list2.size(); i++) {
    if(list1.contains(list2.get(i))){
        list2.remove(i);
        System.out.println("list2: "+list2);
    }
}

 

실행결과:

list2: [4, 3]
list2: [4]

 

변수i 를 증가시키면서 삭제하면, 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 올바른 결과를 얻을 수 없다.

 

remove 메서드 수행과정:

1. 삭제할 데이터보다 뒤에 있는 데이터를 한 칸씩 앞으로 복사(System.arraycopy())해서 삭제할 데이터를 덮어쓴다.

2. 데이터가 모두 한 칸씩 앞으로 이동하였으므로 마지막 데이터는 null로 변경한다.

3. size 값을 1 감소시킨다.

 

마지막에 저장된 것부터 삭제하면 System.arraycopy() 를 호출하여 데이터 복사를 할 필요가 없기 때문에 작업시간이 짧지만, 중간에 위치한 객체를 추가하거나 삭제하는 경우에는 다른 데이터의 위치를 이동시켜 줘야 하기 때문에 데이터의 개수가 많을수록 작업시간이 오래 걸린다.

 

ArrayList나 Vector 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야 하기 때문에 효율이 떨어진다.

 

LinkedList

배열은 모든 데이터가 연속적으로 존재하지만 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있다.

 

삭제를 할 때, 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 다음 요소를 참조하도록 변경하기만 된다.

 

데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 좋다.

 

Linked list는 단방향이기 때문에 이전 요소에 대한 접근은 어렵다, 이 점을 보완한 것이 Doubly Linked List다. 

※ LinkedList는 이름과는 달리 Doubly Linked List로 구현되어 있다.

 

공식문서

 

LinkedList는 Queue의 구현체로 element(), offer(), peek(), poll(), remove() 메서드를 지원한다. (다음 포스트에서 설명)

그 외 메서드는 ArrayList와 거의 비슷하다.

ArrayList vs LinkedList 성능 테스트

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {

    public static void main(String[] args) {
        ArrayList arrayList1 = new ArrayList(1000000); // 100만개
        LinkedList linkedList1 = new LinkedList();

        System.out.println("순차적으로 추가하기");
        System.out.println("ArrayList : "+add1(arrayList1));
        System.out.println("LinkedList : "+add1(linkedList1));

        System.out.println("중간에 추가하기");
        System.out.println("ArrayList : "+add2(arrayList1));
        System.out.println("LinkedList : "+add2(linkedList1));

        System.out.println("중간에서 삭제하기");
        System.out.println("ArrayList : "+remove1(arrayList1));
        System.out.println("LinkedList : "+remove1(linkedList1));

        ArrayList arrayList2 = new ArrayList(1000000); // 100만개
        LinkedList linkedList2 = new LinkedList();
        add1(arrayList2);
        add1(linkedList2);

        System.out.println("접근 시간");
        System.out.println("ArrayList : "+access(arrayList2));
        System.out.println("LinkedList : "+access(linkedList2));

        System.out.println("순차적으로 삭제하기");
        System.out.println("ArrayList : "+remove2(arrayList2));
        System.out.println("LinkedList : "+remove2(linkedList2));
    }
    static long add1(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) list.add(i);
        long end = System.currentTimeMillis();
        return end-start;
    }
    static long add2(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.add(1000,0);
        long end = System.currentTimeMillis();
        return end-start;
    }

    static long remove1(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.remove(i);
        long end = System.currentTimeMillis();
        return end-start;
    }
    static long remove2(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;
    }

    static long access(List list){
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.get(i);
        long end = System.currentTimeMillis();
        return end-start;
    }

}

 

실행결과:

 

순차적으로 추가하기
ArrayList : 25
LinkedList : 179
중간에 추가하기
ArrayList : 4807
LinkedList : 32
중간에서 삭제하기
ArrayList : 5446
LinkedList : 312
접근 시간
ArrayList : 2
LinkedList : 254
순차적으로 삭제하기
ArrayList : 34
LinkedList : 130

배열의 경우 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

위와 같은 간단한 계산만으로 원하는 요소의 주소를 얻어 데이터를 곧바로 읽어올 수 있다.

 

LinkedList는 인덱스가 n인 요소의 값을 얻으려면 처음부터 n번째 데이터까지 차례대로 따라가야만 해서  데이터의 개수가 많아질수록 데이터를 읽어오는 접근 시간(Access Time)이 길어진다.

 

 

---

참고: 자바의 정석 - 남궁성

 

🤞자바의 정석 스터디 14일차 p578-603🤞