Collection Framework(2)

3. LinkedList

ArrayList와 LinkedList 모두 List라는 interface로 부터 상속 받아 구현되어져 있다. 하지만 두 List는 구현 방식이 다르고 성능도 다르다.

ArrayList에 대해서 회고하여보면 ArrayList는 정말 배열 그자체로 연속적인 공간이 배정이 된다.

반면 LinkedList는 데이터들이 다음 객체의 주소를 가지고 있어서 객체가 서로 이어져 있다.

class Node {
	Node next; // a link to the next element
	Object obj; // data
}

그래서 LinkedList라고 불리는 이유가 인스턴스간의 연결이 되어 있어서 이다.

Addition and deletion with linked lists

그러면 LinkedList를 사용하는 이유는 무엇인가? 삽입삭제가 효과적이기 때문

• Deleting an element from the linked list

삭제할때 그냥 주소만 바꾸어주면 된다.

![<https://images.velog.io/images/tonyhan18/post/e3549bfd-69c2-4c54-8b52-34597acee7b4/image.png>](<https://images.velog.io/images/tonyhan18/post/e3549bfd-69c2-4c54-8b52-34597acee7b4/image.png>)

반면 ArrayList는 중간에 비어둘 수 없기 때문에 삭제된 데이터를 기준으로 그 뒤에 있던 모든 데이터는 앞으로 한 칸씩 움직여야 하기에 많은 시간 소모가 발생하게 된다.

• Adding an element to the linked list

데이터를 삽입한다고 하더라도 데이터의 주소를 연결해주기만 하여도 삽입이 완료되게 된다.

![<https://images.velog.io/images/tonyhan18/post/3b702c1b-6aa3-4dcf-a49a-7890e2c5cebc/image.png>](<https://images.velog.io/images/tonyhan18/post/3b702c1b-6aa3-4dcf-a49a-7890e2c5cebc/image.png>)

Types of linked lists

• (Basic) linked lists

  

• Doubly linked list: better accessibility

앞 뒤로 데이터 참조가 쉽다.

![<https://images.velog.io/images/tonyhan18/post/00347330-2db2-4d8f-ae07-fc02e4b59634/image.png>](<https://images.velog.io/images/tonyhan18/post/00347330-2db2-4d8f-ae07-fc02e4b59634/image.png>)

• Doubly circular linked list

맨 앞과 뒤도 가리키게 만들어 주는 방법도 존재하다.

![<https://images.velog.io/images/tonyhan18/post/dff3f58b-fc55-4d64-8d29-332ba9277e1f/image.png>](<https://images.velog.io/images/tonyhan18/post/dff3f58b-fc55-4d64-8d29-332ba9277e1f/image.png>)

Example 1: ArrayList vs. LinkedList

public class Lecture {

	// Sequential Add
	public static long add1(List<String> list) {

    // 현재 시간은 Milisecond 단위로 저장한다.
		long start = System.currentTimeMillis();
		for(int i=0; i<1000000; i++) list.add(i+"");
		long end = System.currentTimeMillis();

    // 작업 시간이 반환
		return end - start;
	}

    // Non-Sequential Add
    // 500 번째부터 x를 삽입하라
	public static long add2(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=0; i<10000; i++) list.add(500, "X");
		long end = System.currentTimeMillis();
		return end - start;
	}

    // 맨 마지막에서 부터 remove 실행
	public static long remove1(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=list.size()-1; i>=0; i--) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}

    // 앞에서부터 remove 실행
	public static long remove2(List<String> list) {
		long start = System.currentTimeMillis();
		for(int i=0; i<10000; i++) list.remove(i);
		long end = System.currentTimeMillis();
		return end - start;
	}

	public static void main(String args[]) {
		ArrayList<String> al = new ArrayList<>(2000000);
		LinkedList<String> ll = new LinkedList<>();
		System.out.println("=== sequential add ===");
		System.out.println("ArraList : " + add1(al));
		System.out.println("LinkedList: " + add1(ll));
		System.out.println();
		System.out.println("=== non-sequential add ===");
		System.out.println("ArraList : " + add2(al));
		System.out.println("LinkedList: " + add2(ll));
		System.out.println();
		System.out.println("=== non-sequential delete ===");
		System.out.println("ArraList : " + remove2(al));
		System.out.println("LinkedList: " + remove2(ll));
		System.out.println();
		System.out.println("=== sequential delete ===");
		System.out.println("ArraList : " + remove1(al));
		System.out.println("LinkedList: " + remove1(ll));
	}
}