[자료구조] ArrayList와 LinkedList의 차이 (Java)

 

ArrayList와 LinkedList는 둘 다 Java에서 제공하는 List 인터페이스를 구현한 클래스이다.

하지만 내부 구조와 동작 방식이 달라 특정 상황에서 성능 차이가 난다.

---

1. 내부 구조

ArrayList

• 내부적으로 동적 배열을 사용한다.
• 요소는 연속된 메모리 공간에 저장된다.
• 크기가 부족하면 자동으로 배열 크기를 늘려 새로운 메모리 공간에 복사한다.
• 장단점
  - 장점
     - 임의 접근(get, set)이 빠르다.(O(1))
     - 데이터가 적고 삽입/삭제 작업이 적을 경우 효율적이다.
     - 메모리 사용량이 적다(포인터가 없기 때문에)
  - 단점
     - 배열 크기를 늘리는 작업(재할당)이 발생하면 비용이 든다.
     - 중간 또는 앞에서 요소를 삽입/삭제할 때 모든 이후 요소를 이동해야 하므로 비용이 크다.
• ArrayList를 사용하는 경우
  - 데이터 접근이 빈번하고, 중간 삽입/삭제가 적은 경우
  - 예: 인덱스를 통해 빠르게 값을 검색해야 하는 경우

 

LinkedList

• 내부적으로 이중 연결 리스트를 사용한다.
• 각 요소는 노드(Node)로 저장되며, 각 노드는 다음 노드와 이전 노드의 참고를 가진다.
• 요소는 메모리의 비연속적인 공간에 저장된다.
• 장단점
  - 장점
     - 삽입/삭제 작업이 많을 ㄸ때 효율적이다.(특히 리스트이 앞부분)
     - 크기가 동적으로 변하므로 초기 용량 설정이 필요 없다.
  - 단점
     - 임의 접근이 느리다.(O(n))
     - 각 노드가 추가적인 포인터(다음 및 이전 노드 참조)를 저장하므로 메모리 사용량이 많다.
• LinkedList를 사용하는 경우
  - 삽입/삭제 작업이 빈번하고, 중간 데이터 접근이 적은 경우
  - 예: 큐나 스택 구현, 데이터 스트림 처리

---

2. 작업별 시간 복잡도

작업	ArrayList	LinkedList
검색(get)	O(1)	O(n)
삽입(add) (끝에)	O(1) (보통)	O(1)
삽입(add) (중간)	O(n)	O(n)
삭제(remove) (끝에)	O(1)	O(1)
삭제(remove) (중간)	O(n)	O(n)
삭제(remove) (앞에)	O(n)	O(1)

---

3. 예제

ArrayList

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1); // 끝에 삽입 O(1)
arrayList.add(0, 2); // 중간 삽입 O(n)
System.out.println(arrayList.get(1)); // 인덱스 검색 O(1)

 

 

LinkedList

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1); // 끝에 삽입 O(1)
linkedList.addFirst(2); // 앞에 삽입 O(1)
linkedList.removeFirst(); // 앞에서 제거 O(1)

 

---

결론

ArrayList는 데이터 접근 속도가 중요하고, 데이터가 많지 않거나 삽입/삭제 작업이 적은 경우 적합하다.

LinkedList는 삽입/삭제 작업이 빈번하거나, 큐와 같은 구조를 구현할 때 적합하다.