자료구조	내부 구조	삽입/삭제 속도	접근 속도	특징
ArrayList	배열 기반	끝에 추가가 빠름. 중간 삽입이나 삭제가 늦음	인덱스로 빠르게 접근이 가능	일반 리스트용(랜덤 access 시 최적)
LinkedList	노드 연결 구조	앞뒤 삽입이나 삭제가 빠르다	인덱스 접근이 늦다(순차 탐색)	양방향 연결 리스트
ArrayDeque	원형 배열 기반	앞/뒤 삽입/삭제가 모두 빠르다	인덱스 접근이 안된다.	stack이나 queue에 특화

1. queue

Queue<Integer> q = new LinkedList<>();

Queue<Integer> q = new LinkedList<>(); // O
Queue<Integer> q = new ArrayDeque<>(); // O
Queue<Integer> q = new ArrayList<>(); // ❌ 컴파일 에러

2. ArrayDeque는 언제 쓰는지?

Queue<Integer> q = new ArrayDeque<>(); // 빠르다
Deque<Integer> dq = new ArrayDeque<>(); //  앞뒤로 넣고 빼는 deque도 가능하다