List

1.  리스트 추상화1 - 인터페이스 도입

 

다형성, OCP가 자료 구조에 어떻게 적용될까?

 

 

예를 들어, 그림과 같이

MyArrayList 와 MyLinkedList 의 공통 기능 -> MyList 인터페이스로 뽑아서 추상화하면 다형성을 활용한 다양한 이점이 있다.

 

MyList 코드

public interface MyList<E> {
    int size();
    void add(E e);
    void add(int index, E e);
    E get(int index);
    E set(int index, E element);
    E remove(int index);
    int indexOf(E o);
}

 MyArrayList 코드

public class MyArrayList<E> implements MyList<E> {
//...
}

MyLinkedList 코드

public class MyLinkedList<E> implements MyList<E> {
//...
}

 

2. 리스트 추상화2 - 의존관계 주입

 

예를 들어, BatchProcessor 클래스가 구체적인 MyLinkedList나 MyArrayList에 직접 의존하면

MyLinkedList -> MyArrayList로 변경할 때 BatchProcessor의 코드도 함께 수정해야 한다. 

해결  -> 추상적인 MyList 인터페이스에 의존

 

정리 -> 생성자 의존성 주입

다형성과 추상화를 활용하면 BatchProcessor 코드의 변경 없이

BatchProcessor 를 생성하는 시점에 생성자를 통해 원하는 리스트 전략(알고리즘)을 지정할 수 있다.

 

ex) 추상적인 MyList에 의존하는 BatchProcessor

public class BatchProcessor {
    private final MyList<Integer> list;
    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }
    public void logic(int size) {
        for (int i = 0; i < size; i++) {
            list.add(0, i); //앞에 추가
        }
    }
}

public class BatchProcessorMain {
    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>();
//MyLinkedList<Integer> list = new MyLinkedList<>();
        BatchProcessor processor = new BatchProcessor(list);
        processor.logic(50_000);
    }
}

 

3. 리스트 추상화3 - 컴파일 타임, 런타임 의존관계

 

 

클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존 관계 주입을 통해 구현체를 주입받아 사용함

-> 클라이언트 코드의 변경 없이, 구현 알고리즘인 MyList 인터페이스의 구현을 자유롭게 확장할 수 있다.

-> 이것을 전략 패턴이라 하고, 이는 OCP 원칙을 지킨다.

 

4. 직접 구현한 배열 리스트 vs 연결 리스트

 

직접 만든 배열 리스트와 연결 리스트의 시간 복잡도와 실제 성능 비교 표

기능	배열 리스트	연결 리스트
앞에 추가(삭제)	O(n) - 1369ms	O(1) - 2ms
평균 추가(삭제)	O(n) - 651ms	O(n) - 1112ms
뒤에 추가(삭제)	O(1) - 2ms	O(n) - 2195ms
인덱스 조회	O(1) - 1ms	O(n) - 438ms
검색	O(n) - 115ms	O(n) - 492ms

정리

대부분의 경우 배열 리스트가 성능상 유리하므로, 주로 배열 리스트를 기본으로 사용한다.

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있는 경우에만 연결 리스트를 고려하자.

 

5.  자바가 제공하는 배열 리스트 vs 연결 리스트

Collection 인터페이스에는 List, Set, Queue와 같은 하위 인터페이스가 존재한다.

 

List 인터페이스의 주요 메서드

메서드	설명
add(E e)	요소 추가
remove(int index)	요소 제거
get(int index)	요소 가져오기
set(int index, E element)	요소 변경
size()	요소 개수 확인
isEmpty()	리스트가 비어있는지 확인

 

자바 ArrayList

• 배열을 사용하여 데이터를 관리
• 기본 CAPACITY는 10이다.
• CAPACITY를 넘어가면 배열을 50% 증가시킨다.
• 메모리 고속 복사 연산을 사용해, 중가 위치에 데이터를 추가해도 비교적 빠르게 수행할 수 있다.

메모리 고속 복사 연산

 

자바 LinkedList

• 이중 연결 리스트 구조 -> 다음 노드 뿐 아니라, 이전 노드로도 이동 가능
• 첫 번째 노드와 마지막 노드 둘 다 참조

 

 

정리(4. 직접 구현한 배열 리스트 vs 연결 리스트 의 내용과 같음)

대부분의 경우 배열 리스트가 성능상 유리하므로, 주로 배열 리스트를 기본으로 사용한다.

만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있는 경우에만 연결 리스트를 고려하자.

 

6.  문제 풀이

문제1 - 배열 -> 리스트 변경

ArrayEx1 는 배열을 사용한다. 이 코드를 배열 대신에 리스트를 사용하도록 변경하자.

다음 코드와 실행 결과를 참고해서 리스트를 사용하는 ListEx1 클래스를 만들어라.

public class ArrayEx1 {
    public static void main(String[] args) {
        int[] students = {90, 80, 70, 60, 50};
        int total = 0;
        for (int i = 0; i < students.length; i++) {
            total += students[i];
        }
        double average = (double) total / students.length;
        System.out.println("점수 총합: " + total);
        System.out.println("점수 평균: " + average);
    }
}

 

정답

import java.util.ArrayList;
import java.util.List;
public class ListEx1 {
    public static void main(String[] args) {
        List<Integer> students = new ArrayList<>();
        students.add(90);
        students.add(80);
        students.add(70);
        students.add(60);
        students.add(50);
        int total = 0;
        for (int i = 0; i < students.size(); i++) {
            total += students.get(i);
        }
        double average = (double) total / students.size();
        System.out.println("점수 총합: " + total);
        System.out.println("점수 평균: " + average);
    }
}

 

문제2 - 리스트의 입력과 출력

사용자에게 n 개의 정수를 입력받아서 List 에 저장하고, 입력 순서대로 출력하자.

0 을 입력하면 입력을 종료하고 결과를 출력한다.출력시 출력 포멧은 1, 2, 3, 4, 5와 같이 , 쉼표를 사용해서 구분하고,

마지막에는 쉼표를 넣지 않아야 한다.

 

실행 결과

n개의 정수를 입력하세요 (종료 0)
1
2
3
4
5
0
출력
1, 2, 3, 4, 5

 

정답

import java.util.ArrayList;
import java.util.Scanner;
public class ListEx2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();
        System.out.println("n개의 정수를 입력하세요 (종료 0)");
        while (true) {
            int input = scanner.nextInt();
            if (input == 0) {
                break;
            }
            numbers.add(input);
        }
        System.out.println("출력");
        for (int i = 0; i < numbers.size(); i++) {
            System.out.print(numbers.get(i));
            if (i < numbers.size() - 1) {
                System.out.print(", ");
            }
        }
    }
}

문제3 - 합계와 평균

사용자에게 n개의 정수를 입력받아서 List에 보관하고, 보관한 정수의 합계와 평균을 계산하는 프로그램을 작성하자.

 

실행 결과

n개의 정수를 입력하세요 (종료 0)
1
2
3
4
5
0
입력한 정수의 합계: 15
입력한 정수의 평균: 3.0

 

정답

import java.util.ArrayList;
import java.util.Scanner;
public class ListEx3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();
        System.out.println("n개의 정수를 입력하세요 (종료 0)");
        while (true) {
            int input = scanner.nextInt();
            if (input == 0) {
                break;
            }
            numbers.add(input);
        }
        int sum = 0;
        for (Integer number : numbers) {
            sum += number;
        }
        double average = (double) sum / numbers.size();
        System.out.println("입력한 정수의 합계: " + sum);
        System.out.println("입력한 정수의 평균: " + average);
    }
}

 

문제4 - 리스트를 사용한 쇼핑 카트

ShoppingCartMain 코드가 작동하도록 ShoppingCart 클래스를 완성해라.

ShoppingCart는 내부에 리스트를 사용해야 한다.