LinkedList(JAVA)

# LinkedList

- 배열의 장점

가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다

- 배열의 단점

1. 크기를 변경할 수 없다.

- 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요하다.

- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하므로 메모리가 낭비된다.

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

- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,

- 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

# LinkedList란?
이러한 배열의 단점을 보완하기 위해서 링크드리스트(Linked list)라는 자료구조가 고안되었다.

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

링크드리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

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

링크드리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 하면 된다. 단 하나의 참조만 변경하면 삭제가 이루어지는 것이다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기때문에 처리속도가 매우 빠르다.

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.

링크드리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다.

이 점을 보완한 것이 더블 링크드리스트(이중 연결리스트, doubly linked list)이다.

더블링크드리스트는 단순히 링크드리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드리스트와 같다.

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

더블링크드리스트의 접근성을 보다 향상시킨 것이 더블 써큘러 링크드리스트(이중 원형 연결리스트, double circular linked list)인데,

단순히 더블 링크드리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 이렇게 하면, 마지막 요소의 다음요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다. 마치 TV의 마지막 채널에서 채널을 증가시키면 첫 번째 채널로 이동하고 첫 번째 채널에서 채널을 감소시키면 마지막 채널로 이동하는 것과 같다.

Source 01) ArrayListLinkedListEx01.java

package linkedList;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class ArrayListLinkedListEx01 {
 
    public static void main(String[] args) {
        // 추가할 데이터의 개수를 고려하여 충분히 잡아야한다.
        ArrayList al = new ArrayList(1000000);
        LinkedList ll = new LinkedList();
 
        System.out.println("= 작업 걸린시간 =");
        System.out.println();
 
        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + add1(al));
        System.out.println("LinkedList : " + add1(ll));
 
        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LinkedList : " + add2(ll));
 
        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LinkedList : " + remove2(ll));
 
        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 < 100000; 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 < 100000; i++)
            list.add(500, "x");
        long end = System.currentTimeMillis();
        return end - start;
    }
 
    // 중간에서 삭제하기
    public static long remove2(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++)
            list.remove(i);
        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.add(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
 
}

Result)

= 작업 걸린시간 =
 
= 순차적으로 추가하기 =
ArrayList : 29
LinkedList : 30
= 중간에 추가하기 =
ArrayList : 1910
LinkedList : 84
= 중간에서 삭제하기 =
ArrayList : 44
LinkedList : 2
= 순차적으로 삭제하기 =
ArrayList : 3
LinkedList : 3

따라서,

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

순차적으로 삭제한다는 것은 마지막 데이터부터 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다는 것을 알 수 있다.

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

중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다.
반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.

- 접근시간 테스트

Source 02) deepAndShallowCopyEx02.java

package deepAndShallowCopy;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class deepAndShallowCopyEx02 {
 
    public static void main(String[] args) {
        ArrayList al = new ArrayList(1000000);
        LinkedList ll = new LinkedList();
        add(al);
        add(ll);
 
        System.out.println("= 접근시간 테스트 =");
        System.out.println("ArrayList : " + access(al));
        System.out.println("LinkedList : " + access(ll));
    }
 
    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 < 10000; i++)
            list.get(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
 
}

Result)

= 접근시간 테스트 =
ArrayList : 1
LinkedList : 84

배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 이처럼 간단한 계산만으로 원하는 n번째 데이터의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만, LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는 시간, 즉 접근시간(access time)이 길어진다는 단점이있다.

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

다루고자 하는 데이터의  개수가 변하지 않는 경우라면, ArrayList가 최상의 선택이 되겠지만,

데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.

두 클래스의장점을 이용하여 두 클래스를 혼합해서 사용하는 방법도 생각해 볼 수 있다. 
처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용한 다음,
작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있을 것이다.

ArrayList al = new ArrayList(1000000);
for(int i=0; i<100000; i++) al.add(i+"");
 
LinkedList ll = new LinkedList(al);
for(int i=0; i<1000; i++) ll.add(500,"x");

- 출처 및 참고자료 : JAVA의정석(남궁성 저)