ArrayList와 LinkedList는 둘 다 List 인터페이스를 구현하지만, 내부 구조와 성능 특성이 다르다.

내부 구조

• ArrayList

  • 내부적으로 배열(Object[])을 사용.
  • 인덱스를 통한 접근이 빠름 (랜덤 액세스 가능).
  • 크기가 가득 차면 더 큰 배열을 새로 만들고 복사해야 함 (성능 저하 가능).

• LinkedList

  • 내부적으로 이중 연결 리스트 (Doubly Linked List) 를 사용.
  • 각 요소가 앞 노드(prev), 뒤 노드(next) 를 참조.
  • 삽입/삭제가 빠름 (특히 중간에서).

주요 연산 성능 (빅오 표기법)

연산	ArrayList	LinkedList
인덱스로 접근 (get, set)	O(1) → 배열이라 바로 접근	O(n) → 앞/뒤부터 순차 탐색
끝에 추가 (add)	O(1) (가끔 O(n), 배열 늘릴 때)	O(1)
중간 삽입/삭제	O(n) → 뒤 요소들 전부 이동 필요	O(1) (노드 연결만 변경)
검색 (contains)	O(n)	O(n)

ArrayList

[0] [1] [2] [3] [4]
 A   B   C   D   E

• C 삭제 시 → D, E를 앞으로 밀어야 함. (O(n))

LinkedList

A <-> B <-> C <-> D <-> E

• C 삭제 시 → B.next = D, D.prev = B로 연결만 바꿔주면 됨 (O(1))

사용 예시

• ArrayList
  조회가 많고, 중간 삽입/삭제가 거의 없는 경우 (예: 데이터 조회용 목록, 캐시)

• LinkedList
  삽입/삭제가 자주 발생하는 경우 (예: 큐, 스택, 데이터 버퍼)