[기본 개념] 6 | (1.3) LinkedList

[기본 개념] 6 | (1.3) LinkedList

1 컬렉션 프레임웍의 핵심 인터페이스

2 ArrayList

3> LinkedList

4 Stack과 Queue

5 Iterator, Listlterator, Enumeration

6 Arrays

7 Comparator와 Comparable

8 HashSet

9 TreeSet

10 HashMap과 Hashtable

11 TreeMap

12 Properties

13 Collections

14 컬렉션 클래스 정리 & 요약

3. LinkedList

 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트(linked list)는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되었다.

 

 링크드 리스트의 각 요소들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다. 따라서 삭제할 때 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 되므로 간단하며 처리속도가 매우 빠르다.

 

 링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 그래서 더블 링크드 리스트(doublly linked list)가 나왔는데 이는 링크드 리스트에 참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하도록 했다.

 

 여기서 더블 링크드 리스트보다 접근성을 향상시킨 더블 써큘러 링크드 리스트(doubly circular limked list)가 생겼는데 이는 더블 링크드 리스트의 첫번째 요소와 마지막 요소를 연결시킨 것이다. 

 

(단방향) 링크드 리스트 -> (양방향) 더블 링크드 리스트 -> (원) 더블 써큘러 링크드 리스트

 

 LinkedList클래스는 '링크드 리스트'가 아닌 '더블 링크드 리스트'로 구현되어 있다. 그리고 List인터페이스를 구현했기 때문에 ArryaList와 많이 비슷하다.

 

예제/ArrayListLinkedListTest.java

import java.util.*;

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 : " + add1(al));
        System.out.println("LinkedList : " + add1(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 add1(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 : 75
LinkedList : 112

=== 중간에 추가하기 ===
ArrayList : 1926
LinkedList : 8

=== 중간에서 삭제하기 ===
ArrayList : 1625
LinkedList : 112

=== 순차적으로 삭제하기 ===
ArrayList : 5
LinkedList : 15

 

결론 1 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.

결론 2 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

 

 배열의 경우 인덱스가 n인 요소의 값을 얻어오고자 한다면 '배열의 주소 + n * 데이터 타입의 크기'를 하면 된다.

 

 LinkedList는 불연속적으로 위치한 각 요소들이 연결된 것이라 처음부터 n번째 데이터까지 차례로 따라가야 원하는 값을 얻을 수 있기 때문에 데이터의 수가 많아질수록 데이터를 읽어오는 접근시간이 길어진다.

 

컬렉션	읽기 (접근시간)	추가 / 삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

 데이터의 개수가 변하지 않으면 ArrayList가 더 낫고, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 낫다. 그리고 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 낼 수도 있다. 

 

 

 

 

 

출처 | Java의 정석 (남궁 성)