[Java] ArrayList, LinkedList 차이

1. List의 자료구조

배열처럼 같은 자료형의 묶음 자료구조

1. 기본 자료형 타입은 저장할 수 없고, Wrapper class만 담을 수 있다.
2. 크기가 고정되어 있지 않고, 동적으로 할당된다.
3. 중간에 있는 값을 빼내면 앞으로 당겨진다.(메모리 낭비 없음)
4. 타입 안정성을 보장하는 generic을 쓸 수 있다.

ArrayList

1. 배열과 유사하다.
2. 내부적으로는 데이터를 배열에서 관리한다.
3. 많은 양의 데이터를 추가/삭제 하는 경우 느리다.
4. index로 접근하므로 검색 속도가 빠르다.

LinkedList

1. 기차처럼 Node로 연결되어 있으며 각 노드는 다음 노드가 무엇인지 가리킨다.

---

2. ArrayList를 사용할 때

인덱스로 접근할 수 있으므로 주로 값을 읽거나, 데이터 추가/수정/삭제가 거의 없는 경우

List<String> menu = new ArrayList<>();
  menu.add("Coffee");
  menu.add("Tea");
  menu.add("Juice");

String selected = menu.get(1);

List<String> days = Arrays.asList("일", "월", "화", "수", "목", "금", "토");

---

3. LinkedList를 사용할 때

데이터 추가/삭제가 빈번한 경우

LinkedList는 중간에 끼워 넣거나 제거할 때, 값 이동이 없고 참조만 바꾸면 되기 때문에 빠르게 가능.

LinkedList<String> queue = new LinkedList<>();
  queue.add("고객1");
  queue.add("고객2");
  queue.addFirst("VIP고객"); // 맨 앞에 추가
  queue.removeLast(); // 맨 뒤 제거

---

4. 중간에 값을 넣을 경우

LinkedList 중간에 값을 넣을 경우

LinkedList<String> list = new LinkedList<>();
  list.add("A");
  list.add("C");

  System.out.println(list); // [A, C]

  list.add(1, "B");

  System.out.println(list); // [A, B, C]

노드를 순회하여 index = 1 위치를 찾은 후, 노드 사이에 새 노드를 넣고 참조(포인터)를 조정.

ArrayList 중간에 값을 넣을 경우

ArrayList<String> list = new ArrayList<>();
  list.add("A");
  list.add("C");

  System.out.println(list); // [A, C]

  list.add(1, "B");

  System.out.println(list); // [A, B, C]

코드는 LinkedList와 똑같지만, 내부적으로는 인덱스 1에 “B”를 넣기 위해 기존의 “C”를 한 칸 뒤로 이동시키고 “B”를 그자리에 넣는다.

---

5. 이러나 저러나 결국 같은 거 아닌가?

결국 두 클래스 모두 중간에 값을 삽입하면, 겉으로는 인덱스를 뒤로 밀고 삽입하는 건데 같은 거 아닐까 싶었다.

하지만 진짜 중요한 포인트는 밀리는 “방식”이 완전히 다르기 때문에, 처리 성능이 다르다는 것이었다.

구분	ArrayList	LinkedList
중간 삽입 시	뒤에 있는 값들 실제로 이동	뒤에 있는 값들은 그대로 있고 참조만 변경
값이 밀리나?	밀림 (실제 데이터 위치 이동)	밀리는 것처럼 보임 (데이터는 안 움직임)
실제 성능 영향	크다 (O(n))	작다 (찾기만 느리고, 삽입 자체는 O(1))