ArrayList와 LinkedList의 주요 차이점

1. 구조적 차이

java

클릭하여 코드 펼치기

//ArrayList의 메모리 구조
[1][2][3][4][5] // 연속된 메모리

특징:
- 데이터가 메모리에 연속적으로 저장됨
- 예: 1이 1000번지, 2가 1004번지, 3이 1008번지...
- 각 데이터는 정해진 크기의 메모리 공간을 가짐
- 인덱스로 직접 접근 가능 (메모리 주소 = 시작주소 + (인덱스 × 데이터크기))
클릭하여 코드 복사

java

클릭하여 코드 펼치기

//LinkedList의 메모리 구조
[데이터1|다음주소] → [데이터2|다음주소] → [데이터3|다음주소]

실제 메모리:
[1|500번지] → [2|900번지] → [3|300번지] → [4|750번지]
(100번지)     (500번지)      (900번지)      (300번지)

특징:
- 각 노드가 데이터와 다음 노드의 주소를 저장
- 메모리 상 불연속적으로 저장 가능
- 다음 데이터를 찾기 위해 현재 노드의 포인터(주소) 사용
클릭하여 코드 복사

---

2. 성능 차이

java

클릭하여 코드 펼치기

//ArrayList
검색/접근: O(1) - 매우 빠름
삽입/삭제: O(n) - 느림 (데이터 이동 필요)

//LinkedList
검색/접근: O(n) - 느림 (순차 접근)
삽입/삭제: O(1) - 매우 빠름
클릭하여 코드 복사

• ArrayList와 LinkedList 모두 인덱스를 통해서 데이터에 접근하지만 음수 인덱스는 사용 불가
• 예외(IndexOutOfBoundsException)가 발생한다.
• Python은 음수 인덱스를 지원하지만(-1이 마지막 요소), Java의 List는 지원하지 않는다.

3. 시간 복잡도의 차이가 나는 이유

java

클릭하여 코드 펼치기

//ArrayList 검색
[A][B][C][D][E]  // 연속된 메모리
list.get(3);      // D를 찾을 때

// 시작주소 + (인덱스 × 데이터크기)로 바로 접근
// 예: 1000번지 + (3 × 4) = 1012번지 바로 접근
// O(1) 한번에 찾음!
클릭하여 코드 복사

java

클릭하여 코드 펼치기

//LinkedList 검색
[A]→[B]→[C]→[D]→[E]  // 포인터로 연결
list.get(3);          // D를 찾을 때

// 처음(head)부터 포인터 따라가기
1. A 확인 → B의 주소 확인
2. B 확인 → C의 주소 확인
3. C 확인 → D의 주소 확인
4. D 발견!
// O(n) 처음부터 하나씩 다 확인!
클릭하여 코드 복사

따라서 LinkedList는 원하는 데이터를 찾기 위해 항상 처음부터 포인터를 따라가야 하므로 시간이 더 오래 걸린다.

java

클릭하여 코드 펼치기

//ArrayList 삭제 과정
[1][2][3][4][5] // 초기 상태
// 2를 삭제하면
[1][3][4][5]    // 뒤의 모든 요소를 앞으로 이동
// 인덱스가 자동으로 조정됨
// 3,4,5가 한 칸씩 앞으로 이동해야 함 (이게 O(n)이 걸리는 이유)
클릭하여 코드 복사

java

클릭하여 코드 펼치기

//LinkedList 삭제 과정
[1]→[2]→[3]→[4]→[5] // 초기 상태
// 2를 삭제하면
[1]→[3]→[4]→[5]     // 링크만 변경
// 1의 포인터가 3을 가리키도록 변경만 하면 됨
// 실제 데이터 이동 없음 (이게 O(1)인 이유)
클릭하여 코드 복사

즉 실제 데이터 이동의 차이가 있다.

---

java

클릭하여 코드 펼치기

//3. 메모리 사용
ArrayList: 연속된 공간, 크기 변경 시 새로운 배열 생성
LinkedList: 새로운 노드만큼만 메모리 사용, 포인터 저장 공간 필요
클릭하여 코드 복사

• 포인터 : 다른 데이터가 저장된 메모리 주소
  • 이 주소를 통해 다음 데이터를 찾아갈 수 있음
  • LinkedList는 이 포인터로 데이터들을 연결
  • Java에서는 참조(Reference)라는 용어를 더 많이 사용하지만, 개념적으로는 포인터와 같습니다.

---

4. 적합한 사용 상황

java

클릭하여 코드 펼치기

ArrayList 사용이 좋을 때:
- 데이터 검색이 많은 경우
- 데이터 삽입/삭제가 적은 경우
- 인덱스로 접근이 많은 경우

LinkedList 사용이 좋을 때:
- 데이터 삽입/삭제가 많은 경우
- 데이터 크기가 동적으로 변하는 경우
- 메모리를 효율적으로 사용해야 하는 경우
클릭하여 코드 복사

---

5. 사용 예시

java

클릭하여 코드 펼치기

// ArrayList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");     // 끝에 추가
arrayList.get(0);       // 인덱스로 빠른 접근

// LinkedList
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("A");  // 앞에 추가
linkedList.addLast("B");   // 뒤에 추가
클릭하여 코드 복사

java

클릭하여 코드 펼치기

// ArrayList 내부 구조
class ArrayList {
    private Object[] elements; // 연속된 배열
    private int size;

    public Object get(int index) {
        return elements[index]; // 직접 접근
    }
}
클릭하여 코드 복사

java

클릭하여 코드 펼치기

// LinkedList 내부 구조
class LinkedList {
    class Node {
        Object data;    // 실제 데이터
        Node next;      // 다음 노드 주소
    }
    private Node head;  // 첫 노드

    public Object get(int index) {
        Node current = head;
        for(int i = 0; i < index; i++) {
            current = current.next; // 순차적 접근
        }
        return current.data;
    }
}
클릭하여 코드 복사