[Java] LinkedList, ArrayList 비교

 

남궁성님의 Java의 정석(3rd Edition)을 보고 정리한 글입니다.

 

LinkedList는 ArrayList와 제공하는 기능을 거의 똑같지만 내부적으로 매우 다르게 동작한다. LinkedList의 3가지 유형을 소개하고 ArrayList와 차이점을 정리해보겠다.

 

1. 단방향 연결 리스트(Singly Liked List) 란?

Class Node {
		Node next; // 다음 요소의 주소를 저장
		Object obj; // 데이터
}

• 노드(객체)끼리의 주소(포인터)를 서로 가리키며 링크(참조)로 이어지는 구조.
• 메모리에 순차적으로 저장되지 않고 데이터의 순서를 link를 통해서 순서를 보장하므로 데이터 추가, 삭제시 배열을 복사하지 않고, link 만 변경해주면 되기 때문에 배열의 단점을 보완함.
• 장점
  • 비순차적인 데이터 추가 또는 삭제 시간은 빠름
• 단점
  • 읽기(접근시간)이 느림
  • 이전 노드를 접근해야 할 때 매우 비효율적이다.

 

삭제, 추가 과정

• 데이터 추가시 한번의 Node 객체 생성과 두번의 참조변경만으로 추가
• 데이터 삭제시 한번의 참조 변경만으로 삭제

 

2. 양방향 연결 리스트(Doubly Liked List) 란?

Class Node {
		Node next; // 다음 노드의 주소를 저장
		Node prev; // 이전 노드의 주소를 저장 
		Object obj; // 데이터
}

• 단방향 LinkedList에서 이전 노드의 주소를 담고있는 필드가 추가
• 역순으로도 접근이 가능하기 때문에 단방향 LikedList보다 많이 사용된다.
• Java에서 LinkedList 클래스는 양방향 연결 리스트로 구현되어 있다.(ArrayList와 마찬가지로 동기화 처리가 되어 있지 않다.)

 

3. 양방향 원형 연결 리스트(Doubly Circular Liked List)

• 양방향 연결 리스트보다 접근성이 더 개선된 구조
• 첫번째 노드와 마지막 노드를 각각 연결시켜 원형 구조를 가진다.

 

4. ArrayList vs. LinkedList

컬렉션	읽기	추가 / 삭제	리사이징	비고
ArrayList	빠르다	느리다	공간이 부족할 경우 새로운 배열에 복사하는 시간 발생	순차적인 추가삭제는 빠름
LinkedList	느리다	빠르다	X	데이터가 많을수록 접근성이 떨어짐

 

 

읽기 속도 차이 비교

public class Main {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList(100000);
        LinkedList linkedList = new LinkedList();
        add(arrayList);
        add(linkedList);

        System.out.println("접근시간 테스트");
        System.out.println("ArrayList : " + access(arrayList));
        System.out.println("LinkedList : " + access(linkedList));
    }

    private static void add(List list) {
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
    }

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

실행결과
접근시간 테스트
ArrayList : 2
LinkedList : 4910

 

 

수정, 삭제 속도 차이 비교

public class Main {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList(2000000);
        LinkedList linkedList = new LinkedList();

        System.out.println("==순차적 추가==");
        System.out.println("ArrayLst : " + add1(arrayList));
        System.out.println("LikedList : " + add1(linkedList));
        System.out.println();
        System.out.println("== 중간 추가==");
        System.out.println("ArrayLst : " + add2(arrayList));
        System.out.println("LikedList : " + add2(linkedList));
        System.out.println();
        System.out.println("==중간 삭제==");
        System.out.println("ArrayLst : " + remove2(arrayList));
        System.out.println("LikedList : " + remove2(linkedList));
        System.out.println();
        System.out.println("==순차 삭제==");
        System.out.println("ArrayLst : " + remove1(arrayList));
        System.out.println("LikedList : " + remove1(linkedList));
    }

    private static long add1(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) list.add(i);
        return System.currentTimeMillis() - start;
    }

    private static long add2(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) list.add(500, 1);
        return System.currentTimeMillis() - start;
    }

    private static long remove1(List list) {
        long start = System.currentTimeMillis();
        for (int i = list.size() - 1; i >= 0; i--) list.remove(i);
        return System.currentTimeMillis() - start;
    }

    private static long remove2(List list) {
        long start = System.currentTimeMillis();
        for (int i = 10; i < 10000; i++) list.remove(i);
        return System.currentTimeMillis() - start;
    }
}

실행결과
==순차적 추가==
ArrayLst : 0
LikedList : 147

== 중간 추가==
ArrayLst : 4278
LikedList : 16

==중간 삭제==
ArrayLst : 1534
LikedList : 76

==순차 삭제==
ArrayLst : 0
LikedList : 15