[Java] 컬렉션 프레임워크_LinkedList

LinkedList

연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋습니다. 

 

 특징

   1) 인접 참조를 링크해서 체인처럼 관리함
   2) 특정 인덱스에서 객체를 제거하거나 추가하게 되면 앞 뒤의 링크만 연결하면 됨
   3) 빈번한 객체의 삽입과 삭제가 일어나는 곳에서는 ArrayList보다 더 큰 성능을 발휘함
     (단, 중간에 데이터 삽입과 삭제가 일어나는 경우에만 해당)

---

ArrayList로 추가하는 데 걸리는 시간과 LinkedList로 추가하는데 걸리는 시간 비교하기

package collection;

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

public class Ex03 {

	public static void main(String[] args) {
		
	List<Integer> list1 = new ArrayList<Integer>();
	List<Integer> list2 = new LinkedList<Integer>();
	
	// long타입 변수 start, end변수 선언
	long start, end;
	
	// 1. ArrayList로 추가하는 데 걸리는 시간
	start = System.nanoTime();		// 10억분의 1초 값을 구하는 메소드 => long 타입으로 반환
	
	for(int i=0; i<10000; i++) {
		list1.add(0,i);
	}
	
	end = System.nanoTime();
	
	System.out.printf
		("ArrayList로 추가하는데 걸린 시간 : %,d ns\n", (end-start));
	
	// 2. LinkedList로 추가하는데 걸리는 시간
	start = System.nanoTime();
	
	for(int i=0; i<10000; i++) {
		list2.add(0, i);
	}
	
	end = System.nanoTime();
	
	System.out.printf
		("LinkedList로 추가하는 데 걸린 시간 : %,d ns", (end-start));

	}

}