Java 컬렉션 : LinkedList

List : LinkedList 란?

배열의 장단점

배열은 구조가 간단하고 데이터를 읽어오는 시간이 짧은 장점이 있지만 단점도 존재한다.

• 크기를 변경할 수 없어 변경이 필요한 경우 새로운 배열을 생성 후 데이터를 복사한 후 참조를 변경해야 한다
• 미리 큰 배열을 생성하는 방법도 있지만 메모리가 낭비된다
• 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다

LinkedList는 ArrayList가 배열을 이용하는 데에 발생하는 단점을 극복하기 위해 고안되었다. 배열은 모든 데이터가 연속적으로 저장되는 구조지만 LinkedList는 불연속적으로 존재하는 데이터를 서로 연결하는 노드로 구성되어 있다.

Singly Linked List

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

Singly Linked List는 단방향으로만 연결되어 있어 데이터 접근성이 나쁜데, 다음 노드에 대한 접근은 쉽지만 이전 노드에 대한 접근이 어렵다.

Doubly Linked List

class Node {
    Node next;
    Node prev; // 이전 노드의 주소 저장
    Object obj;
}

Dobuly Linked List는 단일 연결 리스트의 단점을 보완한 것으로 이전 노드의 주소도 저장하여 접근이 용이하다는 특징이 있다.

Doubly Circular Linked List

이중 원형 연결 리스트로 단순히 Doubly Linked List에서 첫번째 요소와 마지막 요소를 서로 연결시킨 것이다.

ArrayList vs LinkedList

데이터 추가/삭제 비교

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class prac {
	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 :167
LinkedList :316

= 중간에 추가하기 =
ArrayList :3190
LinkedList :21

= 중간에서 삭제하기 =
ArrayList :2087
LinkedList :182

= 순차적으로 삭제하기 =
ArrayList :12
LinkedList :41

• 순차적인 추가/삭제의 경우 ArrayList가 빠르다
  • ArrayList의 공간이 모자라 새로 배열을 복사하는 경우가 있었다면 LinkedList가 빠를 수도 있다
• 비순차적인 추가/삭제의 경우 LinkedList가 훨씬 빠르다
  • 데이터의 갯수가 많지 않다면 어느 것을 사용해도 비슷하다

데이터 접근 시간 비교

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class prac {
	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;
	}
}

= 데이터 접근 시간 =
ArrayList :1
LinkedList :214

• 데이터를 접근하는 시간은 ArrayList가 빠르다
• 배열은 연속적으로 저장되기 때문에 원하는 데이터를 바로 읽어올 수 있지만, LinkedList는 노드를 하나하나 거쳐가야 해서 느릴 수 밖에 없다.

결론

데이터의 범위를 효율적으로 잡을 수 있다면 ArrayList가 효율적이지만 변경이 잦은 작업이라면 LinkedList가 더 좋은 방법이 될 수도 있다.