[JAVA] 61. LinkedList

1. Linked List

• ArrayList의 단점
• 배열 중간에서 원소의 삽입, 삭제가 어려움
• 이를 해결할 수 있는 Linked List

• 각 원소를 링크로 연결

• 첫 원소가 다음 원소의 주소 Key를 들고 있음
• index로 원소를 찾을 때는 Full Scan 필요 : 탐색 불리

package ex18;

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("MILK");
        list.add("BREAD");
        list.add("BUTTER");

        // 인덱스 1에 APPLE 삽입
        list.add(1, "APPLE");

        // 인덱스 2의 원소를 GRAPE로 대체
        list.set(2, "GRAPE");

        // 인덱스 3의 원소 삭제
        list.remove(3);

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i) + " ");
        }
    }
}

2. ArrayList vs LinkedList

• ArrayList는 인덱스를 가지고 원소에 접근하거나, 동시에 많은 원소를 이동시킬 때 유리
• 내부 원소를 삭제하거나 옮길 때 원소 개수에 비례하여 시간 소요 : 불리

• LinkedList는 처음에 원소의 추가나 내부 원소 삭제가 빈번할 경우 유리
• 인덱스 접근 시 원소 개수에 비례하여 시간 소요 : 불리

• 일반적으로는 ArrayList가 속도가 빠르나, 직접 구현 후 속도를 측정해보는 것이 좋음

• ArrayList는 확장되기 전 ArrayList가 저장할 수 있는 초기 용량을 튜닝할 수 있음
• LinkedList는 튜닝 매개변수는 없지만 여러 메서드를 가짐
• addFirst(), getFirst(), removeFirst(), addLast(), getLast(), removeLast() 등