[Java] 김영한의 자바 중급 2편 #5 - List

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

자료 구조에 다형성과 OCP 원칙이 어떻게 적용되는지 확인해본다.

 

List : 순서가 있고, 중복을 허용하는 자료 구조

→ MyArrayList와 MyLinkedList의 공통 기능을 인터페이스로 뽑아서 추상화를 한다면 다형성을 활용한 다양한 이득을 얻을 수 있다.

 

 

 

MyList

package collection.list;

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, MyLinkedList에서 구현해야 한다.

• size
• add
• get
• set
• remove
• indexOf

 

MyLinkedList

package collection.list;

public class MyLinkedList<E> implements MyList<E> {
    private Node<E> first;

    private int size = 0;

    @Override
    public void add(E e) {
        Node<E> newNode = new Node<>(e);
        if (first == null) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node<E> getLastNode() {
        Node<E> x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    @Override
    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

    @Override
    public E set(int index, E element) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    @Override
    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removedItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removedItem;
    }

    @Override
    public E get(int index) {
        Node<E> node = getNode(index);
        return node.item;
    }

    private Node<E> getNode(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    @Override
    public int indexOf(E o) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
        return -1;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV3{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    private static class Node<E> {
        E item;
        Node<E> next;
        public Node(E item) {
            this.item = item;
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node<E> temp = this;
            sb.append("[");
            while (temp != null) {
                sb.append(temp.item);
                if (temp.next != null) {
                    sb.append("->");
                }
                temp = temp.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

MyArrayList

package collection.list;

import java.util.Arrays;

public class MyArrayList<E> implements MyList<E> {
    private static final int DEFAULT_CAPACITY = 5;

    private Object[] elementData;

    private int size = 0;

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(E e) {
        if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++;
    }

    @Override
    public void add(int index, E e) {
        if (size == elementData.length) {
            grow();
        }
        shiftRightFrom(index);
        elementData[index] = e;
        size++;
    }

    //요소의 마지막부터 index까지 오른쪽으로 밀기
    private void shiftRightFrom(int index) {
        for (int i = size; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public E set(int index, E element) {
        E oldValue = get(index);
        elementData[index] = element;
        return oldValue;
    }

    @Override
    public E remove(int index) {
        E oldValue = get(index);
        shiftLeftFrom(index);
        size--;
        elementData[size] = null;
        return oldValue;
    }

    //요소의 index부터 마지막까지 왼쪽으로 밀기
    private void shiftLeftFrom(int index) {
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }

    @Override
    public int indexOf(E o) {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                return i;
            }
        }
        return -1;
    }

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size=" +
                size + ", capacity=" + elementData.length;
    }
}

 

 

 

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

MyArrayList를 활용해서 데이터를 처리하는 BatchProcessor 클래스를 개발했다고 가정한다.

프로그램은 잘 돌아가지만 개발해보고 나니 데이터를 맨 앞에 추가하는 일이 많은 상황이라고 가정해본다.

데이터를 앞에서 추가하거나 삭제하는 일이 많다면 MyArrayList보다는 MyLinkedList를 사용하는 것이 훨씬 효율적이다.

구체적인 MyArrayList에 의존하는 BatchProcessor 예시 : O(n)

package collection.list;

public class BatchProcessor {

    private final MyArrayList<Integer> list = new MyArrayList<>();

    public void logic(int size) {
        for (int i = 0; i < size; i++) {
            // 맨 앞에 데이터를 추가한다.
            list.add(0, i);
        }
    }

}

구체적인 MyLinkedList에 의존하는 BatchProcessor 예시 : O(1)

package collection.list;

public class BatchProcessor {

		// private final MyArrayList<Integer> list = new MyArrayList<>();
    private final MyLinkedList<Integer> list = new MyLinkedList<>();

    public void logic(int size) {
        for (int i = 0; i < size; i++) {
            // 맨 앞에 데이터를 추가한다.
            list.add(0, i);
        }
    }

}

추상적인 MyList에 의존하는 BatchProcessor 예시

package collection.list;

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); //앞에 추가
        }
    }
}

// Main 메서드
main() {
	new BatchProcessor(new MyArrayList()); //MyArrayList를 사용하고 싶을 때
	new BatchProcessor(new MyLinkedList()); //MyLinkedList를 사용하고 싶을 때
}

• BatchProcessor를 생성하는 시점에 생성자를 통해 원하는 리스트 전략을 선택해서 전달할 수 있다.
• 이렇게 하면 MyList를 사용하는 클라이언트 코드인 BatchProcessor를 전혀 변경하지 않고 원하는 리스트 전략을 런타임에 지정할 수 있다.
  • 다형성과 추상화를 활용하여 BatchProcessor 코드를 전혀 변경하지 않고 리스트 전략을 선택 가능

2.1. 실제 코드 작성

BatchProcessor

package collection.list;

public class BatchProcessor {
    private final MyList<Integer> list;
    
    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }
    
    public void logic(int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i); //앞에 추가
        }
        long endTime = System.currentTimeMillis();
        System.out.println("크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
    }
}

Main

package collection.list;

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);
    }
}

// MyArrayList 결과
크기: 50000, 계산 시간: 1300ms

// MyLinkedList 결과
크기: 50000, 계산 시간: 7ms

• BatchProcessor의 외부(Main 구문)에서 의존관계가 결정되어서 BatchProcessor 인스턴스에 들어오는 것 같음. 마치 의존관계가 외부에서 주입되는 것 같다고 해서 이것을 의존관계 주입이라고 한다.
• 참고로 생성자를 통해 의존관계를 주입했기 때문에 생성자 의존관계 주입이라고 한다. → 의존관계 주입(Dependency Injection)

 

 

 

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

의존관계는 크게 컴파일 타임 의존관계와 런타임 의존관계로 나눌 수 있다.

• 컴파일 타임 : 코드 컴파일 시점을 뜻한다.
• 런타임 : 프로그램 실행 시점을 뜻한다.

3.1. 컴파일 타임 의존관계

 

• 컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스에 모든 의존관계가 나타난다.
  • 클래스에서 바로 보이는 의존 관계이며 실행하지 않는 소스 코드에 정적으로 나타나는 의존관계
• BatchProcessor 클래스를 보면 MyList 인터페이스만 사용하며 MyArrayList나 MyLinkedList 같은 정보는 보이지 않는다.

 

3.2. 런타임 의존관계

 

• 실제 프로그램이 작동할 때 보이는 의존관계이다. 주로 생성된 인스턴스와 그것을 참조하는 의존관계이다.
• 쉽게 이야기해서 프로그램이 실행될 때 인스턴스 간에 의존관계로 보면 된다.
• 런타임 의존관계는 프로그램 실행 중 계속 변할 수 있다.

예시

MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor processor = new BatchProcessor(list);
processor.logic(50_000);

• BatchProcessor 인스턴스의 MyList list는 생성자를 통해 MyArrayList(x001) 인스턴스를 참조한다.
  • BatchProcessor 인스턴스에 MyArrayList(x001) 의존관계를 주입한다.
• 따라서 이후 logic()을 호출하면 MyArrayList 인스턴스를 사용하게 된다.

 

정리

• MyList 인터페이스 도입으로 같은 리스트 자료구조를 그대로 사용하면서 원하는 구현을 변경할 수 있게 되었다.
• BatchProcessor에서 처음부터 MyArrayList를 사용하도록 컴파일 타임 의존관계를 지정했다면 이후에 MyLinkedList로 수정하기 위해서는 BatchProcessor 코드를 변경해야 한다
• BatchProcessor 클래스는 추상적인 MyList에 의존한다. 따라서 런타임에 MyList의 구현체를 얼마든지 변경할 수 있다.
• 이렇게 생성자를 통해 런타임 의존관계를 주입하는 것이 생성자 의존주입 관계 또는 줄여서 생성자 주입이라고 한다.
• 클라이언트 클래스(BatchrProcessor)는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존 관계 주입을 통해 구현체를 주입받아 사용함으로써 이런 장점을 얻을 수 있게 된다.

 

전략 패턴 : 디자인 패턴 중 가장 중요한 패턴 중 하나를 꼽으라고 하면 전략 패턴을 뽑을 수 있다. 전략 패턴은 알고리즘을 클라이언트 코드 변경 없이 쉽게 교체할 수 있다.

 

MyList 인터페이스가 바로 전략을 정의하는 인터페이스가 되고 각각의 구현체인 MyArrayList, MyLinkedList가 전략의 구체적인 구현이 된다.

 

그리고 전략을 클라이언트 코드(BatchProcessor)의 변경 없이 손쉽게 교체할 수 있게 된다.

 

 

 

4. 직접 구현한 리스트의 성능 비교

4.1. 코드

package collection.list;

public class MyListPerformanceTest {
    public static void main(String[] args) {
        int size = 50_000;

        System.out.println("==MyArrayList 추가==");
        addFirst(new MyArrayList<>(), size);
        addMid(new MyArrayList<>(), size);
        MyArrayList<Integer> arrayList = new MyArrayList<>(size);
        addLast(arrayList, size);

        System.out.println("==MyLinkedList 추가==");
        addFirst(new MyLinkedList<>(), size);
        addMid(new MyLinkedList<>(), size);
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        addLast(linkedList, size);

        int loop = 10000;
        System.out.println("==MyArrayList 조회==");
        getIndex(arrayList, loop, 0);
        getIndex(arrayList, loop, size / 2);
        getIndex(arrayList, loop, size - 1);

        System.out.println("==MyLinkedList 조회==");
        getIndex(linkedList, loop, 0);
        getIndex(linkedList, loop, size / 2);
        getIndex(linkedList, loop, size - 1);

        System.out.println("==MyArrayList 검색==");
        search(arrayList, loop, 0);
        search(arrayList, loop, size / 2);
        search(arrayList, loop, size - 1);
        
        System.out.println("==MyLinkedList 검색==");
        search(linkedList, loop, 0);
        search(linkedList, loop, size / 2);
        search(linkedList, loop, size - 1);
    }

    private static void addFirst(MyList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("앞에 추가 - 크기 : " + size + ", 계산 시간 : " + (endTime - startTime) + "ms");
    }

    private static void addMid(MyList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i / 2, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
    }

    private static void addLast(MyList<Integer> list, int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
    }

    private static void getIndex(MyList<Integer> list, int loop, int index) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.get(index);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("index: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
    }

    private static void search(MyList<Integer> list, int loop, int findValue) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < loop; i++) {
            list.indexOf(findValue);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("findValue: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
    }
}

// result
==MyArrayList 추가==
앞에 추가 - 크기 : 50000, 계산 시간 : 1209ms
평균 추가 - 크기: 50000, 계산 시간: 566ms
뒤에 추가 - 크기: 50000, 계산 시간: 2ms

==MyLinkedList 추가==
앞에 추가 - 크기 : 50000, 계산 시간 : 9ms
평균 추가 - 크기: 50000, 계산 시간: 825ms
뒤에 추가 - 크기: 50000, 계산 시간: 1262ms

==MyArrayList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms
index: 25000, 반복: 10000, 계산 시간: 0ms
index: 49999, 반복: 10000, 계산 시간: 0ms

==MyLinkedList 조회==
index: 0, 반복: 10000, 계산 시간: 0ms
index: 25000, 반복: 10000, 계산 시간: 264ms
index: 49999, 반복: 10000, 계산 시간: 514ms

==MyArrayList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 78ms
findValue: 49999, 반복: 10000, 계산 시간: 152ms

==MyLinkedList 검색==
findValue: 0, 반복: 10000, 계산 시간: 1ms
findValue: 25000, 반복: 10000, 계산 시간: 283ms
findValue: 49999, 반복: 10000, 계산 시간: 565ms

 

 

대략적인 성능 차이는 아래처럼 발생한다.

 

 

5. 자바 리스트

 

 

Collection 인터페이스는 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다.

 

이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다.

 

Collection 인터페이스는 List, Set, Queue와 같은 다양한 하위 인터페이스와 함께 사용되며 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있게 된다.

 

List 인터페이스는 객체들의 순서가 있고 같은 객체의 중복 저장을 허용한다. 배열과 비슷하지만 크기가 동적으로 변하는 컬렉션을 다룰 때 유연하게 사용할 수 있다.

 

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

• add(E e)
• add(int index, E element)
• allAdd(Collection<? extends E> c)
• get(int index)
• set(int index, E element)
• remove(int index)
• remove(Object o)
• clear()
• indexOf(Object o)
• lastIndexOf(Object o)
• contains(Object o)
• sort(Comparator<? super E> c)
• subList(int fromIndex, int toIndex)
• size()
• isEmpty()
• iterator()
• toArray()
• toArray(T[] a)

 

5.2. Java ArrayList 특징

• 내부적으로 배열을 사용해서 데이터를 관리한다.
• 기본 CAPACITY는 10이지만 CAPACITY가 넘어가면 50% 증가시킨다. (10 → 15 → 22 → 33 → ..)
• 메모리 고속 복사 연산을 사용한다.
  • System.arraycopy()를 사용하여 추가할 위치 이후의 모든 요소를 한 칸씩 뒤로 빠르게 이동시킨다.

 

5.3. Java LinkedList 특징

• 이중 연결 리스트 구조
• 첫 번째 노드와 마지막 노드의 참조를 모두 가지고 있다.

 

 

6. 문제 풀이

6.1. 배열을 리스트로 변경하기

package collection.list.test.ex1;

import java.util.ArrayList;

public class ListEx1 {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(90);
        arrayList.add(80);
        arrayList.add(70);
        arrayList.add(60);
        arrayList.add(50);

        int total = 0;
        for (int i = 0; i < arrayList.size(); i++) {
            total += arrayList.get(i);
        }

        double average = (double) total / arrayList.size();

        System.out.println("점수 총합: " + total);
        System.out.println("점수 평균: " + average);
    }
}

 

6.2. 리스트의 입력과 출력

package collection.list.test.ex1;

import java.util.ArrayList;
import java.util.Scanner;

public class ListEx2 {
    public static void main(String[] args) {
        System.out.println("n개의 정수를 입력하세요 (종료 0)");

        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> numbers = new ArrayList<>();

        while (true) {
            Integer input = scanner.nextInt();
            if (input.equals(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(", ");
            }
        }
    }
}