[Algorithms] 배열과 리스트

배열의 특징

1. 고정된 크기: 배열은 선언할 때 크기를 지정하며, 한번 크기를 지정하면 이후에 크기를 변경할 수 없다.

2. 빠른 접근 속도: 배열은 인덱스를 통해 직접 값에 접근할 수 있어 접근 속도가 빠르다.

3. 삽입과 삭제가 어렵다: 배열의 특정 위치에 값을 삽입하거나 삭제하려면 그 위치 이후의 모든 요소를 이동시켜야 한다.

4. 메모리 사용 효율적: 배열은 연속된 메모리 공간을 사용하여 포인터와 같은 추가적인 메모리 사용이 없어 효율적이다.

 

배열 예제: 배열에서 값을 삽입하고, 삭제하는 과정에서 배열의 크기가 고정되어 있기 때문에 인덱스를 사용하여 값을 직접 수정하고 이동시켜야 합니다.

public class ArrayExample {
    public static void main(String[] args) {
        int[] array = new int[5]; // 배열 크기 5로 선언
        array[0] = 10; // 인덱스를 사용해 값 삽입
        array[1] = 20;
        array[2] = 30;

        System.out.println("Array elements:");
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]); // 인덱스를 사용해 값 접근
        }

        // 배열에서 값 삭제(삭제된 위치 뒤의 값을 모두 이동)
        for (int i = 1; i < array.length - 1; i++) {
            array[i] = array[i + 1];
        }
        array[array.length - 1] = 0; // 마지막 값을 0으로 설정

        System.out.println("Array after deletion:");
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

 

리스트의 특징

1. 동적 크기: 리스트는 선언할 때 크기를 미리 지정할 필요가 없으며, 데이터의 삽입과 삭제가 발생할 때 크기를 유동적으로 조절할 수 있다.

2. 느린 접근 속도: 리스트는 포인터를 따라가며 순차적으로 요소에 접근해야 하기 때문에 접근 속도가 느리다.

3. 빠른 삽입과 삭제: 특정 위치에 데이터를 삽입하거나 삭제할 때, 포인터만 변경하면 되기 때문에 빠르게 수행할 수 있다.

4. 추가 메모리 필요: 각 요소가 다음 요소를 가리키는 포인터를 저장해야 하므로, 배열에 비해 메모리 사용이 비효율적이다.

 

리스트 예제: LinkedList를 사용해 리스트를 선언하였으며, 값의 삽입과 삭제가 포인터를 통해 효율적으로 처리됩니다.

import java.util.LinkedList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>(); // 리스트 선언

        list.add(10); // 값 삽입
        list.add(20);
        list.add(30);

        System.out.println("List elements:");
        for (int value : list) {
            System.out.println(value); // 순차적으로 접근
        }

        list.remove(1); // 인덱스 1 위치의 값 삭제

        System.out.println("List after deletion:");
        for (int value : list) {
            System.out.println(value);
        }
    }
}

 

배열과 리스트의 시간 복잡도:

• 배열: 접근 O(1), 삽입/삭제 O(n)
• 리스트: 접근 O(n), 삽입/삭제 O(1)

배열의 경우: 메모리가 연속적으로 할당되므로 캐시 적중률이 높고, 리스트보다 메모리 사용이 효율적일 수 있습니다.

리스트의 경우: 메모리가 비연속적으로 할당되므로 크기가 변할 가능성이 큰 데이터를 다루거나 빈번한 삽입/삭제가 필요한 경우 유리합니다.

 

 

 

끝.