Java- 컬렉션 프레임워크(LinkedList)

1. LinkedList(연결리스트)

배열은 간단하고 데이터 읽어오는데 시간이 빠르다는 장점들이 존재합니다.

 

그러나 단점 또한 존재합니다.

 

• 크기 변경 X
  • 새로운 배열 생성하여 복사 작업
  • 메모리 낭비
• 비순차적 CRUD 작업 오래걸림
  • 빈자리에 넣는 것이 오래걸림

이러한 것을 보완하기 위해 연결리스트가 나왔습니다.

LinkedList는 서로 비순차적인(불연속적)인 데이터들을 서로 연결해줍니다.

 

1 2 3 4 5
1 -> 2 -> 3 -> 4 -> 5

LinkedList에는 다음요소의 주소를 저장하는 next와 데이터를 저장하는 요소가 존재합니다.

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

즉 자료구조 연결리스트에서 많이 보셨을거라 생각합니다.

 

• 삽입

1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> 3 -> 6 -> 4 -> 5

6을 3과 4 중간에 삽입하고자 한다면 

 

이전 요소의 참조(3)를 새로운 요소에 참조(6)로 바꾸고 새로운 요소(6)가 다음 요소(4)에 대해서 참조하도록 바꾸면 됩니다.

 

• 삭제

1 -> 2 -> 3 -> 4 -> 5
1 -> 2 -> 4 -> 5

3이라는 요소를 삭제하고자 한다면

 

2가 삭제하고자 하는 3요소의 다음 요소 4를 참조하도록 하면 됩니다. 굉장히 빠르게 처리가 가능합니다.

 

2. Double Linked List(이중연결리스트)

앞서 말한 연결리스트는 단일입니다. 즉 이전 요소에 대한 접근이 힘듭니다. 한 방향으로만 가기 때문이죠.

 

그러나 이중연결리스트는 다음 요소, 이전 요소 접근이 굉장히 편합니다.

 

이전 요소 주소와 다음 요소 주소를 저장할 Node만 있으면 됩니다.

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

1 -> 2 -> 3 -> 4 -> 5
1 <-> 2 <-> 3 <-> 4 <-> 5

3. Double Circular Linked List(이중원형연결리스트)

이중연결리스트를 향상시킨 것입니다.

 

즉 첫 요소와 마지막 요소를 연결 시켜 마치 순환..? 하는 것처럼 보입니다.

 

0 <-> 1 <-> 2 <-> 3 <-> 4
┌-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-┐
└-------------------------------┘

4. 예제

ArrayList vs LinkedList(성능 비교)

 

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

        System.out.println("순차적으로 추가");
        System.out.println("ArrayList : " + add1(arrayList));
        System.out.println("linkedList : " + add1(linkedList));

        System.out.println();

        System.out.println("중간에 추가");
        System.out.println("ArrayList : " + add2(arrayList));
        System.out.println("linkedList : " + add2(linkedList));

        System.out.println();

        System.out.println("순차적으로 삭제");
        System.out.println("ArrayList : " + remove2(arrayList));
        System.out.println("linkedList : " + remove2(linkedList));

        System.out.println();

        System.out.println("중간에 삭제");
        System.out.println("ArrayList : " + remove1(arrayList));
        System.out.println("linkedList : " + remove1(linkedList));


    }
	//순차적 추가
    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 : 201	
linkedList : 860

중간에 추가
ArrayList : 2023
linkedList : 8

순차적으로 삭제
ArrayList : 2024
linkedList : 108

중간에 삭제
ArrayList : 8
linkedList : 14

LinkedList는 중간에 추가/삭제하는 경우 ArrayList보다 빠릅니다.

ArrayList는 순차적으로 추가/삭제하는 경우 LinkedList보다 빠릅니다.

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

        System.out.println("access time test");
        System.out.println("Array List : " + access(arrayList));
        System.out.println("Linked List : " + access(linkedList));
    }

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

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

access time test
Array List : 7
Linked List : 9223

ArrayList가 접근하는데 LinkedList보다 빠릅니다.

왜냐하면 배열은 메모리에서 바로 가져오지만 LinkedList는 불연속적이고 스캔을 하는데 속도가 느립니다.

 

컬렉션	읽기	추가/삭제	설명
ArrayList	빠름	느림	순차 추가삭제는 빠르지만 비효율적
LinkedList	느림	빠름	빅데이터일 경우 접근성 비효율적