LinkedList | Notion

import java.util.*;

LinkedList<Integer> list = new LinkedList<>();

내부 구조

Java의 LinkedList는 이중 연결 리스트(Doubly Linked List) 로 구현되어 있ek

각 노드는 값(data) 와 앞/뒤 노드의 참조(reference) 를 가지고 있음
삽입/삭제 시에는 노드 포인터만 바꾸면 되므로 ArrayList보다 삽입/삭제가 빠를 수 있음
반면, 접근 속도는 느리다 (인덱스 접근 시 앞에서부터 순회)

주요 메서드

add(E e);               // 끝에 추가
add(int index, E e);    // 특정 위치에 삽입
get(int index);         // 인덱스 접근 (비효율적)
remove(int index);      // 특정 위치 삭제
set(int index, E e);    // 특정 위치 값 변경

ArrayList와 비교

항목	ArrayList	LinkedList
구조	배열 기반	이중 연결 리스트
접근 속도	빠름 (`O(1)`)	느림 (`O(n)`)
삽입/삭제 (중간)	느림 (`O(n)`)	빠름 (`O(1)`)
메모리 사용	적음	더 큼 (포인터 필요)

중간 삽입/삭제가 많으면 LinkedList,

빈번한 조회가 필요하면 ArrayList 가 유리하다