LinkedList
ArrayList와 사용 방법은 동일한데, 내부 구조는 완전 다름 ArrayList과 LinkedList의 다른 점.
ArrayList은 생성할 때 용량을 지정하고, 용량보다 더 많은 요소가 추가된 경우에 용량을 늘여가며 수행.
LinkedList는 요소를 추가할 때마다 동적으로 요소의 메모리를 생성하기 때문에 배열처럼 용량을 늘리고 요소 값을 복사하는 번거러움이 없음.
또한 LinkedList는 자료를 중간에 추가하거나 삭제할 때 자료의 이동이 배열보다 적음.
ArrayList이 LinkedList 보다 효율적인 경우는 어떤 요소의 위치(i번째)를 찾는 경우.
ArrayList은 물리적으로 연결된 자료 구조이므르 i번째 요소 메모리 위치를 바로 계산할 수 있어 접근이 빠름.
예를 들어 int 배열의 두 번째 자료는 처음 주소부터 8바이트 떨어진 위치.
ArrayList는 내부 배열에 객체를 저장해서 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리 LinkedList에서 특정 인덱스의 객체를 제거하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않음 끝에서 부터(순차적으로) 추가 또는 삭제하는 경우에는 ArrayList가 빠르지만 중간에 추가, 삭제하는 경우는 앞뒤 링크 정보만 변경하 므로 LinkedList가 더 빠름
사용하는 자료의 변동(삽입, 삭제)이 많은 경우는 LinkedList를, 자료 변동이 거의 없는 경우에는 배열을 사용하는 것이 효율적.
package chapter20230901;
import java.util.*;
public class test03 {
/*
LinkedList
*/
public static void main(String[] args) {
// List<String> linkedList = new linkedList<>; // List로 선언시 addFirst(), removeLast() 사용 못함
LinkedList<String> linkedList = new LinkedList<>(); // 제네릭 사용,
// 링크드 리스트에 요소 추가
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
System.out.println(linkedList); // 리스트 전체 출력
// [A, B, C]
linkedList.add(1, "D"); // 1번 인덱스에 추가
System.out.println(linkedList);
// [A, D, B, C]
linkedList.addFirst("O"); // addFirst() : 사용 맨 앞에 추가 LinkedList에서 사용
System.out.println(linkedList);
// [O, A, D, B, C]
System.out.println(linkedList.removeLast()); // removeLast() : 맨 뒤의 요소 삭제 및 반환 LinkedList에서 사용
System.out.println(linkedList);
// [O, A, D, B]
}
}
ArrayList와 LinkedList의 실행 선능 비교
끝에서 부터 (순차적으로) 추가 또는 삭제하는 경우는 ArrayList가 빠르지만 중간에 추가, 삭제 하는경우에는 앞 뒤 링크 정보만 변경하는 LinkedList가 더 빠름
ArrayList는 뒤쪽 인덱스들을 모두 1씩 증가 또는 감소 시키는 시간이 필요하므로 처리 속도가 느림
package chapter20230901;
import java.util.*;
public class test04 {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
List<String> list2 = new ArrayList<String>();
long startTime;
long endTime;
// 1. 중간에 추가하는 경우
System.out.println("1. 중간에 추가하는 경우");
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list1.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("ArrayList 걸린시간 : " + (endTime - startTime) + " ns"); // ArrayList 걸린시간 : 5063083 ns
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list2.add(0, String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("LinkedList 걸린시간 : " + (endTime - startTime) + " ns"); // LinkedList 걸린시간 : 4488208 ns
System.out.println();
// 2. 끝에서 순차적으로 추가하는 경우
System.out.println("2. 끝에서 순차적으로 추가하는 경우");
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list1.add(String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("ArrayList 걸린시간 : " + (endTime - startTime) + " ns"); // ArrayList 걸린시간 : 507625 ns
startTime = System.nanoTime();
for(int i = 0; i < 10000; i++) {
list2.add(String.valueOf(i));
}
endTime = System.nanoTime();
System.out.println("LinkedList 걸린시간 : " + (endTime - startTime) + " ns"); // LinkedList 걸린시간 : 402750 ns
}
}
