25.02.11 TIL Array, LinkedList

1. 배열(Array)란?

배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.
각 요소는 인덱스(index)를 사용해 O(1) 시간 복잡도로 접근할 수 있습니다.

배열의 특징

• 빠른 조회: 인덱스를 사용하여 O(1) 시간 복잡도로 접근 가능
• 고정된 크기: 선언 시 크기가 정해지며, 변경 불가능
• 메모리 연속성: 데이터가 연속된 메모리에 저장됨

배열의 장점과 단점

장점	단점
빠른 데이터 접근 (O(1))	크기 변경 불가능 (초기 선언 필요)
메모리 접근 효율성 높음	삽입/삭제가 느림 (O(n))
캐시 히트율 높음	중간 삽입 시 데이터 이동 필요

배열 예제 (Java)

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        
        // 값 접근
        System.out.println(arr[2]); // 30

        // 배열 순회
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

2. 연결 리스트(LinkedList)란?

연결 리스트는 각 노드(Node)가 데이터와 다음 노드의 주소(참조)를 포함하는 자료구조입니다.

연결 리스트의 특징

• 동적 크기 조절 가능: 필요할 때마다 노드를 추가할 수 있음
• 삽입/삭제가 빠름: O(1) (맨 앞/맨 뒤) or O(n) (중간)
• 순차 접근 필요: 특정 요소를 찾으려면 O(n) 시간이 소요됨

연결 리스트의 장점과 단점

장점	단점
크기 변경이 자유로움	조회 속도가 느림 (O(n))
삽입/삭제가 빠름	메모리 사용량 증가 (포인터 필요)
연속된 메모리 공간이 필요 없음	캐시 효율이 낮음

연결 리스트 예제 (Java - LinkedList)

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // 요소 추가
        list.add(10);
        list.add(20);
        list.add(30);

        // 값 접근 (O(n))
        System.out.println(list.get(1)); // 20

        // 요소 삭제
        list.removeFirst(); // 첫 번째 요소 삭제

        // 리스트 출력
        for (int num : list) {
            System.out.print(num + " ");
        }
    }
}

---

3. 배열 vs 연결 리스트 비교

비교 항목	배열 (Array)	연결 리스트 (LinkedList)
메모리 구조	연속된 메모리 사용	불연속적인 메모리 사용
데이터 접근 속도	O(1) (인덱스 접근)	O(n) (순차 접근)
삽입/삭제 속도	O(n) (중간 삽입/삭제 시 이동 필요)	O(1) (노드 추가/삭제)
메모리 효율성	추가적인 포인터 필요 없음	포인터(참조)로 인해 메모리 사용 증가
크기 조정	고정 크기 (변경 불가)	동적 크기 조절 가능

---

4. 언제 배열과 연결 리스트를 사용할까?

- 배열이 유리한 경우

• 데이터 조회가 빈번한 경우 (빠른 O(1) 접근)
• 크기가 고정된 데이터 저장이 필요한 경우
• 메모리 효율이 중요한 경우

- 연결 리스트가 유리한 경우

• 삽입/삭제가 빈번한 경우 (O(1) 삽입/삭제)
• 데이터 크기를 미리 알 수 없는 경우 (동적 할당)
• 중간 삽입/삭제가 많은 경우

---

5. 느낀 점

배열과 연결 리스트는 서로 장단점이 명확하다는 것을 다시 한 번 느꼈습니다.
개인적으로 Java에서 ArrayList는 배열 기반, LinkedList는 연결 리스트 기반으로 구현되어 있어 데이터 조회가 많으면 ArrayList, 삽입/삭제가 많으면 LinkedList를 선택하는 것이 합리적이라는 점을 배웠습니다.
배열의 캐시 적중률(Cache Hit Ratio)이 높아 성능이 더 유리할 수 있음도 중요한 포인트였습니다.