[JAVA] List

추상화와 다형성

ArrayList와 LinkedList 실습내용을 기반으로 공통 기능을 인터페이스로 뽑아서 추상화하면 다형성을 활용한 다양한 이득을 얻을 수 있다.

같은 기능을 제공하는 메서드를 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 e);

    E remove(int index);

    int indexOf(E o);
}

public class MyLinkedList<E> implements MyList<E> {

    private MyNode<E> head; // 연결 리스트의 첫 번째 노드를 가리키는 참조 (시작점)
    private int size;

    //입력받은 순서의 노드를 가져옴
    @Override
    public E get(int index) {
        MyNode<E> x = getNode(index);
        return x.data;
    }

    //입력받은 순서와 데이터를 삽입
    @Override
    public E set(int index, E e) {
        MyNode<E> x = getNode(index);
        E oldValue = x.data;
        x.data = e;
        return oldValue;
    }

    //index번째 노드 삭제
    @Override
    public E remove(int index) {
        MyNode<E> x = getNode(index); //삭제할 노드 가져옴
        E oldValue = x.data; //그 노드의 data를 oldValue에 저장
        if(index == 0) { //삭제노드가 첫번째면
            head = head.next; //head를 다음 노드로 이동시킴
        } else {
            MyNode<E> prev = getNode(index - 1); //이전 노드를 가져와
            prev.next = x.next; //이전 노드가 삭제 대상의 다음 노드를 가리키게 만듦
        }
        x.next = null; //삭제 노드의 next 참조를 끊어 메모리 누수 방지
        size--; //리스트 크기 감소
        return oldValue; //삭제된 노드의 데이터 반환
    }

    //맨 끝에 새로운 노드를 추가
    @Override
    public void add(E e) {
        MyNode<E> newNode = new MyNode<>(e); //1. 입력받은 e로 새 노드 생성 (item = e, next = null)
        if(head == null) { //2. 리스트가 비어있으면
            head = newNode; //3. 새 노드가 첫 노드가 됨
        } else {
            MyNode<E> lastNode = getLastNode(); //4. 마지막 노드를 lastNode에 저장
            lastNode.next = newNode; // 5. 그 뒤에 새 노드를 연결
        }
        size++;
    }

    //index 위치에 새로운 노드 추가
    @Override
    public void add(int index, E e) {
        MyNode<E> newNode = new MyNode<>(e); //새 노드 생성
        if(index == 0) {
            newNode.next = head;
            head = newNode; //새 노드가 첫 노드가 됨
        } else {
            MyNode<E> prev = getNode(index -1); //새 노드를 넣을 직전 노드를 찾음
            newNode.next = prev.next; //새 노드의 next는 기존 prev 뒤의 노드로 연결
            prev.next = newNode;
        }
        size++;
    }

    //마지막 노드를 찾기
    public MyNode<E> getLastNode() {
        MyNode<E> x = head; //리스트의 첫 번째 노드인 head를 x에 저장
        while(x.next != null) { //x가 마지막이 아닐때까지 반복
            x = x.next;
        }
        return x; //x는 마지막 노드 반환
    }

    //index 번째 있는 노드 찾기
    private MyNode<E> getNode(int index) {
        MyNode<E> x = head;
        for(int i= 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    @Override
    public int indexOf(E e) {
        int index = 0;
        for(MyNode<E> x = head; x != null; x = x.next) {
            if (e.equals(x.data)) {
                return index;
            }
            index++;
        }
        return -1;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        MyNode x = head;
        while(x != null) {
            sb.append(x.data);
            if(x.next != null) {
                sb.append(", ");
            }
            x = x.next;
        }
        sb.append("]");
        sb.append(" size = " + size);
        return sb.toString();
    }

    private static class MyNode<E> {
        E data;
        MyNode<E> next;

        public MyNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return String.valueOf(data);
        }
    }

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

    private Object[] elementData;
    private int size = 0;

    public MyArrayList() {
        //기본생성자를 쓰면 배열 길이 = 5
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initialCapacity) {
        //생성할때 크기를 다르게 만들고 싶으면 이 생성자 사용
        elementData = new Object[initialCapacity];
    }

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

    //리스트에 데이터를 추가 데이터 추가하면 size +1
    @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
    public E remove(int index) {
        E oldValue  = get(index);
        shiftLeftFrom(index);

        size--;
        elementData[size] =  null;
        return oldValue;
    }

    private void shiftLeftFrom(int index) {
        for (int i = index; i < size -1; i++) {
            elementData[i] = elementData[i + 1];
        }
    }

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2; //길이가 2배
        //배열을 새로 만들고 기존 배열을 새로운 배열로 복사
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    @SuppressWarnings("unchecked")  //경고 제거
    @Override
    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 int indexOf(E o) {
        for(int i = 0; i < size; i++) {
            if(o.equals(elementData[i])) {
                return i; //데이터 있으면 위치 반환
            }
        }
        return -1; //없는 경우 -1 반환
    }

    @Override
    public String toString() {
        //[1,2,3,null,null] //size = 3
        //[1,2,3] // size = 3
        return Arrays.toString(Arrays.copyOf(elementData, size)) + //size 크기의 배열을 새로 만든다
                " size = " + size + " ," + "capacity = " + elementData.length; //배열의 사이즈만큼 카피 후 출력 null 빼줌
    }

public class BatchProcessorMain {
  public static void main(String[] args) {
      /**
       * 여기서 MyArrayList, MyLinkedList 어떤걸 사용할 지 결정
       * 앞에 넣는건 링크드 리스트가 더 빠름
       */
      MyArrayList<Integer> list = new MyArrayList<>();
      //MyLinkedList<Integer> list = new MyLinkedList<>();

      Batchprocessor processor = new Batchprocessor(list);
      processor.logic(50_000);
  }
}

다형성에 대해 - https://9osari.netlify.app/posts/다형성_2/

의존관계 주입(Dependency Injection) 적용

MyArrayList 를 사용하다 느려서 MyLinkedList 를 사용하도록 코드를 변경해야 한다면. BatchProcessorMain 의 내부코드를 변경해야만 한다.

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

• 구체적인 MyArrayList(클래스) 에 의존한다 표현.

추상적인 MyList에 의존하는 BatchProcessorMain

private final MyList<Integer> list;

//결정을 나중으로 미룸.
public Batchprocessor(MyList<Integer> list) {
    this.list = list;
}

• 생성자를 통해 어떤걸 쓸 지 결정을 뒤로 미룬다.
• MyList는 부모라 자식의 기능을 알고 있다! 즉 추상적!

new Batchprocessor(new MyArrayList<>()); //MyArrayList를 사용할때
new Batchprocessor(new MyLinkedList<>()); //MyLinkedList를 사용할때

• Batchprocessor 를 생성하는 시점에 생성자를 통해 원하는 리스트 전략(알고리즘)을 선택해 전달하면 된다.
• 즉 MyList를 사용하는 클라이언트 코드인 Batchprocessor를 변경하지 않고 원하는 리스트 전략을 런타임에 지정할 수 있다.
• MyList = 전략 인터페이스
• MyArrayList, MyLinkedList = 전략 구현체
• BatchProcessor = 클라이언트
  
  

다형성과 추상화를 활용하면 Batchprocessor 코드를 전혀 변경하지 않고 리스트 전략(알고리즘)을 MyArrayList 에서 MyLinkedList 로 변경할 수 있다. 즉 전략 교체 가능, OCP 원칙 충족

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

• 어떠한 MyList list 의 구현체를 선택할 지는 실행 시점에 생성자를 통해 결정된다.
• 생성사를 통해 MyList 구현체가 전달된다.
• MyArrayList 인스턴스가 들어오거나, MyLinkedList 인스턴스가 들어올 수 있다. 이것은 Batchprocessor 외부에서 의존관계가 결정되어 Batchprocessor 인스턴스에 들어오는 것 같다. 마치 의존관계가 외부에서 주입되는 것 같다 해서 이것을 의존관계 주입(DI)이라 한다.
• 생성자를 통해 의존관계를 주입했기 때문에 생성자 의존관계 주입 이라 한다.

컴파일 타임 의존관계

• 컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스의 모든 의존관계가 나타난다.
• Batchprocessor 클래스는 MyList 인터페이스에서만 사용한다. 즉 Batchprocessor는 MyList 인터페이스에만 의존한다.

런타임 의존관계

• 런타임 의존관계는 실제 프로그램이 작동할 때 보이는 의존관계다. 생성된 인스턴스와 그걸 참조하는 의존관계이다.
• 프로그램이 실행될 때 인스턴스 간에 의존관계
• 프로그램 실행 중에 계속 변할 수 있다.

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

Batchprocessor processor = new Batchprocessor(list);
processor.logic(50_000);

• Batchprocessor 인스턴스의 MyList list 는 생성자를 통해 MyArrayList(x001)인스턴스를 참조
• Batchprocessor 인스턴스에 MyArrayList(x001) 의존관계 주입
• 호출 시 MyArrayList 인스턴스 사용
• MyLinkedList(x002) 인스턴스를 참조할 경우 마찬가지.

Batchprocessor 클래스는 구체적은 MyArrayList 또는 MyLinkedList 에 의존하는 것이 아니라 추상적인 MyList 에 의존. 따라서 런타임에 MyList 구현체를 선택할 수 있다. Batchprocessor에서 사용하는 리스트의 의존관계를 클래스에서 미리 결정하지 않고 런타임에 객체를 생성하는 시점으로 미룬다. 따라서, 런타임에 MyList 구현체를 변경해도 Batchprocessor 의 코드는 수정하지 않아도 된다.

이렇게 생성자를 통해 런타임 의존관계를 주입하는 것을 생성자 의존관계 주입 또는 줄여서 생성자 주입이라 한다.

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

제네릭도 타입을 나중으로 미루듯이 재사용성을 늘리려면 나중으로 미뤄야한다.

성능 비교

기능	MyArrayList	MyLinkedList
앞 추가	O(n)	O(1)
중간 추가	O(n)	O(n)
뒤 추가	O(1)	O(n)
조회	O(1)	O(n)
검색	O(n)	O(n)

• 자바 ArrayList는 grow 시 System.arraycopy()로 메모리 고속 복사 → 빠름
• 대부분 실무에선 ArrayList 사용, 특수한 경우만 LinkedList 고려

List

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

자바의 컬렉션 프레임워크가 제공하는 가장 대표적인 자료 구조

ArrayList

java.util.ArrayList

• 배열을 사용해 데이터 관리
• 기본 CAPACITY = 10 기본값을 넘어가면 50% 증가
• 메모리 고속 복사 연산을 사용(System.arraycopy)

LinkedList

java.util.LinkedList

• 이중 연결 리스트 구조
• 첫 번째 노드와 마지막 노드 둘다 참조
• node.next → 다음 노드 / node.prev → 이전 노드
• 역방향 조회 가능

ArrayList vs LinkedList

• 대부분의 경우 배열 리스트가 성능상 유리
• 실무에서는 주로 배열 리스트를 기본으로 사용
• 만약 데이터를 앞쪽에 자주 추가하거나 삭제하면 연결리스트 사용을 고려하자

출처: 김영한의 실전 자바 - 중급 2편