자바 중급 2편 - List(1)

• List 자료구조
  • 순서가 있고, 중복을 허용하는 자료구조
  • 전에 배운 ArrayList와 LinkedList는 내부 구현만 다를 뿐 같은 기능을 제공한다. 하지만 내부구현이 다르기 때문에
    성능은 달라질 수 있다.

 

 

 

✅ MyList를 인터페이스로 구현해 MyArrayList와 MyLinkedList가 상속받게 구현

 

MyList 인터페이스

package com.example.collection.list;

public interface MyList<E> {

    int size();


    void add(int index, E e);

    E get(int index);

    E set(int index, E e);

    E remove(int index);

    int indexOf(E e);

}

 

MyArrayList 클래스

package com.example.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];
    }

    public int size() {
        return size;
    }



    public void add(E e) {

        // 코드 추가
        if (size == elementData.length) {

            grow();

        }

        elementData[size++] = e;

    }

    // 코드 추가
    @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];
        }


    }



    // 코드 추가
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity =oldCapacity * 2;

        // 배열을 새로만들고, 기존 배열을 새로운 배열에 복사


        elementData = Arrays.copyOf(elementData, newCapacity);
    }


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

    public E set(int index, Object e) {

        E oldValue = get(index);

        elementData[index] = e;

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

    public String toString() {

        return Arrays.toString(Arrays.copyOf(elementData, size)) + " size = " + size + ", capacity = " + elementData.length;

    }


}

 

MyLinkedList 클래스

 

package com.example.collection.list;

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

    private Node<E> first;
    private int size;


    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 e) {

        Node<E> x = getNode(index);

        E oldValue = x.item;
        x.item = e;

        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;

    }

    private Node<E> getNode(int index) {

        Node<E> x = first;

        for (int i = 0; i < index; i++) {
            x = x.next;
        }

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

        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {

            if (x.item.equals(e)) {
                return index;
            }

            index++;

        }

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





    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "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() {
//        return "Node{" +
//                "item=" + item +
//                ", next=" + next +
//                '}';
//    }


        // {A -> B -> C}
        @Override
        public String toString() {

            StringBuilder sb = new StringBuilder();

            Node<E> x = this;

            sb.append("[");
            while (x != null) {

                sb.append(x.item);
                if  (x.next != null) {
                    sb.append(" -> ");
                }
                x = x.next;
            }

            sb.append("]");

            return sb.toString();

        }
    }
}

 

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

• IF) MyArrayList를 활용해서 많은 데이터를 처리하는 BatchProcessor 개발 중
• 개발 완료 후 데이터를 앞에서 추가하는 상황이 많다고 가정
• 이런 경우 MyLinkedList가 더욱 효율적이다
  • MyArrayList : O(n)
  • MyLinkedList : O(1)

 

예시 코드)

package com.example.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));


    }
}

 

package com.example.collection.list;

public class BatchProcessorMain {


    public static void main(String[] args) {

        BatchProcessor batchProcessor1 = new BatchProcessor(new MyLinkedList<>());

        batchProcessor1.logic(1_000_000);

        BatchProcessor batchProcessor2 = new BatchProcessor(new MyArrayList<>());
        batchProcessor2.logic(50000);


    }
}

 

• 어떤 MyList list의 구현체를 선택할지는 실행 시점에 생성자를 통해 결정
• MyLinkedList, MyArrayList 인스턴스 둘 다 들어올 수 있다.
• BatchProcessor의 외부에서 의존관계가 결정되어서 BatchProcessor인스턴스에 들어오는 것 같다.
• 의존관계가 외부에서 주입되는 것 같다고 해서 의존관계 주입(Dependency Injection)이라 한다.

 

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