LinkedList

LinkedList

 

ArrayList와 달리 index와 무관하게 불연속적으로 존재하는 데이터의 연결

 

배열의 단점으로는 크게 두가지가 있는데 

첫째로는 배열의 길이를 미리 정해두어 크기를 변경하기 번거롭다는 것과,

둘째로는 비순차적인 데이터의 추가 및 삭제시 시간이 많이 소모된다는 것이다.

 

이러한 단점을 보완하기 위해 나온것이 LinkedList이다.

 

ArrayList와 LinkedList의 속도 비교

	순차적 추가/삭제	중간 추가/삭제	검색
ArrayList	빠름	느림	빠름
LinkedList	느림	빠름	느림

LinkedList 값 추가 / 삭제

LinkedList<String> ll = new LinkedList<String>();

ll.addFirst("A");
ll.addFirst("B");
ll.addFirst("C");
ll.addFirst("D");

System.out.println(ll);

ll.removeLast();
System.out.println(ll);

• removeLast( ) : 배열과 같은 컬렉션의 마지막 값을 제거

[실행결과]

[D, C, B, A]

[D, C, B]

---

예제 1.

<ArrayList와 LinkedList 중간 추가/삭제 속도 비교>

List<String> test1 = new ArrayList<String>();
List<String> test2 = new LinkedList<String>();

long startTime;
long endTime;

startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
test1.add(0, String.valueOf(i));
}
endTime = System.nanoTime();

System.out.println("ArrayList걸린 시간 : " + (endTime - startTime)); 

startTime = System.nanoTime();
for (int i = 0; i < 10000; i++) {
test2.add(0, String.valueOf(i));
}
endTime = System.nanoTime();

System.out.println("LinkedList걸린 시간 : " + (endTime - startTime));

• System.nanoTime( ) : 시스템 시간과 무관하게 기준 시점에서부터 경과시간을 측정 (ns단위)

[실행결과]

ArrayList걸린 시간 : 4879900
LinkedList걸린 시간 : 1548100

 

실행결과를 통해 중간 추가/삭제 속도는 ArrayList가 LinkedList보다 느린 것을 확인할 수 있다.