본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.

• 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
  • IDE : IntelliJ IDEA (Ultimate Edition)
  • Java : JDK 21 (corretto-21)
  • Python : 3.9 (conda env)

자료구조 - Array 기반 List

0. 서론: 동적 배열이란?

• 고정 배열의 한계: 일반적인 배열은 크기가 고정되어 있어, 삽입/삭제가 비효율적입니다.
  • 이 문제를 해결하기 위한 자료구조가 동적 배열입니다.

• 동적 배열의 특성: 동적 배열은 크기를 자동으로 확장하며, 데이터의 삽입/삭제를 더 효율적으로 처리할 수 있습니다.
  • 예를 들어, Java의 ArrayList는 배열이 꽉 찼을 때 크기가 1.5배로 확장되며, Python의 List는 2배로 확장됩니다.
  • 두 구현 모두 자동으로 메모리를 확장하여, 고정 배열에 비해 유연한 크기 조정이 가능합니다.

1. Java ArrayList와 Python List의 개념

1.1 Java의 ArrayList

• 동작 원리: ArrayList는 내부적으로 배열을 사용하며, 배열이 가득 차면 더 큰 배열로 데이터를 복사하여 확장합니다.
• 초기 크기와 확장 방식: ArrayList는 초기 크기를 지정할 수도 있으며, 크기가 초과되면 1.5배로 확장됩니다.
  • 배열의 요소마다 고정된 메모리크기를 가지고 있어서 새로운 배열을 1.5배 늘려서 생성하고 복사하는 방식으로 동작합니다.
• 타입 지정: 제네릭(Generic)을 사용하여 타입 안전성을 보장합니다.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(10);  // 끝에 추가 (O(1))
        numbers.add(20);
        numbers.add(30);

        numbers.add(1, 15);  // 중간 삽입 (O(n))
        System.out.println(numbers);  // [10, 15, 20, 30]
        
        numbers.remove(2);  // 중간 삭제 (O(n))
        System.out.println(numbers);  // [10, 15, 30]
    }
}

1.2 Python의 List

• 동작 원리: Python의 List도 동적 배열처럼 작동하며, 메모리 크기가 부족할 경우 자동으로 확장됩니다.
• 확장 방식: 리스트 크기가 자동으로 조절되지만, 내부적으로는 2배로 확장됩니다.
  • 타입이 지정되어 있지 않기 때문에 각 요소마다 가지는 메모리 크기가 다를 수 있기 때문에, 메모리 용량을 늘리는 방식으로 확장이 이루어 집니다.
• 유연한 타입 지원: 다양한 데이터 타입을 혼합하여 저장할 수 있습니다.

numbers = [10, 20, 30]
numbers.insert(1, 15)  # 중간 삽입 (O(n))
print(numbers)  # [10, 15, 20, 30]

numbers.pop(2)  # 중간 삭제 (O(n))
print(numbers)  # [10, 15, 30]

2. 주요 연산 비교

2.1 요소 삽입 (Insertion)

• Java ArrayList: 끝에 삽입하는 연산은 O(1)이지만, 중간에 삽입하는 경우 O(n)이 소요됩니다.
• Python List: 마찬가지로 끝에 삽입할 때는 O(1), 중간 삽입은 O(n)의 시간 복잡도를 가집니다.

2.2 요소 삭제 (Deletion)

• Java ArrayList: 특정 위치에서의 삭제는 O(n)의 시간이 걸리며, 삭제 후 데이터를 이동해야 합니다.
• Python List: pop() 메서드를 사용하면 끝에서 삭제할 때 O(1), 중간에서 삭제할 때 O(n)이 소요됩니다.

2.3 요소 조회 (Access)

• Java ArrayList와 Python List 모두 인덱스를 통한 조회는 O(1)의 시간 복잡도를 가집니다.

3. ArrayList와 List의 장단점 비교

3.1 Java ArrayList 장단점

장점:

• 제네릭 타입을 통해 타입 안전성을 보장합니다.
• 빠른 조회와 삽입/삭제 성능을 보입니다.
• 메모리 관리: Java의 ArrayList는 JVM의 Garbage Collector가 불필요한 객체를 자동으로 메모리에서 제거해 주기 때문에, 메모리 관리는 자동으로 처리되지만 크기가 고정된 배열을 사용하기 때문에 중간 크기 조절 작업에서 비용이 발생할 수 있습니다.

단점:

• 크기가 꽉 차면 배열을 새로 만들어 데이터를 복사하는 작업이 필요합니다.
  • 이 과정에서 기존 메모리에서 새로운 메모리 공간으로 데이터를 복사하는 추가 작업이 필요합니다.

3.2 Python List 장단점

장점:

• 유연한 타입 지원 및 동적 크기 조절.
• 메모리 관리를 자동으로 처리합니다.
  • Python에서는 가비지 컬렉터라는 메모리 관리 시스템을 통해 불필요한 데이터를 자동으로 제거합니다.

단점:

• 여러 타입이 혼합될 수 있어 타입 안전성이 떨어질 수 있습니다.
  • Python List는 다양한 데이터 타입을 허용하기 때문에 잘못된 타입이 포함될 가능성이 있습니다.
  • 이로 인해 예기치 못한 오류가 발생할 수 있으며, 타입 검사를 명시적으로 하지 않으면 코드가 복잡해질 수 있습니다.

4. 실습 문제: 배열 기반 List를 이용한 간단한 문제 해결

문제: 주어진 리스트에서 중복을 제거하고, 정렬된 리스트를 반환하라.

• Java에서 HashSet은 중복을 제거하는 데 O(1) 시간 복잡도를 가집니다. 이후 ArrayList로 변환하여 정렬합니다.
• Python에서도 동일하게 set을 사용하여 중복을 제거한 후 list로 변환해 정렬합니다. 마찬가지로 O(1) 시간 복잡도로 중복 제거가 가능합니다.

Set에 관한 사항은 추후에 다른 포스팅에서 정리할 예정입니다.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(10);
        numbers.add(30);
        numbers.add(20);

        Set<Integer> uniqueNumbers = new HashSet<>(numbers);  // O(1) 시간 복잡도로 중복 제거
        List<Integer> sortedList = new ArrayList<>(uniqueNumbers);
        
        Collections.sort(uniqueNumbers);	// 중복 제거 후 정렬
        System.out.println(uniqueNumbers);  // [10, 20, 30]
    }
}

Python

numbers = [10, 20, 10, 30, 20]
unique_numbers = list(set(numbers)) # O(1) 시간 복잡도로 중복 제거
unique_numbers.sort()
print(unique_numbers)  # [10, 20, 30]

마무리

• Java의 ArrayList와 Python의 List는 모두 동적 배열 기반 자료구조로서, 크기 조절이 자유롭다는 공통점이 있습니다.

• 실제 사용 사례: 동적 배열은 데이터의 빈번한 삽입 및 삭제가 이루어지는 상황에서 매우 유용하게 사용됩니다.
  • 예를 들어, 실시간 데이터 처리나 대규모 데이터를 다루는 애플리케이션에서 동적 배열을 사용해 성능을 최적화할 수 있습니다.
  • 특히 대규모 데이터를 저장하고 연속적으로 읽고 쓰는 작업에서 동적 배열을 사용하면 고정 배열에 비해 메모리 효율이 높습니다.
• 메모리 관리: Java는 ArrayList에서 JVM의 Garbage Collector가 자동으로 메모리를 관리하며, Python은 가비지 컬렉터를 통해 동적으로 메모리 할당과 해제를 처리합니다.
• 타입 안전성: Java는 제네릭을 사용해 타입 안전성을 보장하지만, Python에서는 다양한 타입을 혼합하여 사용할 수 있어, 개발자가 명시적으로 타입 검사를 해야 하는 경우도 있습니다.

• 다음 포스팅에서는 LinkedList 자료구조를 살펴보고, 배열과 어떻게 다른지 비교할 예정입니다.