ArrayList와 LinkedList 정리

Java에서 순서가 있는 데이터 집합을 다룰 때 가장 많이 사용하는 인터페이스는 List입니다. 이 글에서는 List 인터페이스의 개념부터 주요 구현 클래스인 ArrayList, LinkedList, Vector까지 정리해보겠습니다.

---

📌 List 인터페이스란?

• Collection 인터페이스의 하위 인터페이스
• 중복된 요소를 저장할 수 있음
• 요소의 삽입 순서를 유지
• 인덱스를 사용하여 요소에 접근 가능
• 저장된 데이터의 양에 따라 자동으로 크기가 조절

---

📌 주요 메서드

메서드	설명
add(E e)	리스트 끝에 요소 추가
add(int index, E element)	특정 위치에 요소 삽입
remove(int index)	특정 인덱스의 요소 삭제
get(int index)	특정 인덱스의 요소 반환
set(int index, E element)	특정 인덱스의 요소 수정
indexOf(Object o)	주어진 요소가 처음 등장하는 인덱스 반환
subList(int fromIndex, int toIndex)	지정된 범위의 부분 리스트 반환

---

📌 주요 구현체

1. ArrayList

• 내부적으로 배열을 기반으로 구현
• 요소 접근 속도가 빠름 (O(1))
• 삽입/삭제는 느릴 수 있음 (중간 요소 이동 필요)

2. LinkedList

• 노드(Node) 기반으로 구현 (연결 리스트)
• 요소 삽입/삭제가 빠름 (특히 앞/뒤)
• 요소 접근은 느림 (O(N))

3. Vector

• ArrayList와 유사하지만, 동기화(synchronized) 지원
• 멀티스레드 환경에서 안전하지만 성능 저하 우려

---

📌 ArrayList

🔍 특징

• 내부적으로 동적 배열을 사용
• 처음에는 일정 크기로 시작, 꽉 차면 크기를 자동 확장
• 중복 요소 허용, 삽입 순서 유지

✅ 장점

• 빠른 접근 속도 → O(1)
• 자동 크기 확장
• 인덱스를 통한 직관적인 요소 접근

❌ 단점

• 중간 요소 삭제 시 모든 요소를 이동해야 함 → O(N)

💻 예제 코드

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add(1, "Orange"); // 인덱스 1에 삽입
        list.remove("Banana"); // Banana 삭제
        System.out.println(list.get(0)); // Apple
        System.out.println(list); // [Apple, Orange]
    }
}

---

📌 LinkedList

🔍 특징

• LinkedList는 자료구조인 연결 리스트(Linked List)를 기반으로 구현된 List의 구현체입니다.
• 각 요소는 노드(Node)로 구성되며, 데이터와 다음 노드에 대한 참조(링크)를 포함합니다.
• 순차적인 인덱스를 사용하는 배열과 달리, 메모리 공간이 연속적이지 않아도 되며, 삽입 및 삭제에 유리합니다.

✅ 장점

• 빠른 삽입/삭제
  리스트 앞이나 뒤에서의 삽입/삭제는 O(1)의 시간 복잡도를 가짐
• 동적 크기 조정
  배열처럼 크기를 미리 지정할 필요가 없음
• 양방향 연결 리스트
  앞뒤 요소 탐색이 모두 가능 (LinkedList는 Doubly Linked List)

❌ 단점

• 느린 요소 접근 속도
  인덱스를 사용해 접근할 경우, 처음부터 순차 탐색해야 하므로 O(N)
• 더 많은 메모리 사용
  각 노드가 데이터와 함께 이전/다음 노드 참조 정보를 함께 저장

💻 예제 코드

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Dog");
        list.add("Cat");
        list.addFirst("Tiger"); // 맨 앞에 삽입
        list.removeLast();      // 맨 뒤 요소 삭제
        System.out.println(list); // [Tiger, Dog]
    }
}

---