배열과 리스트 feat.큐,덱

배열

 

 

리스트

 

 

vector는 Collection이전의 클래스. 속도가 비교적 느림. 또한 코테는 싱글스레드이기에 코테에서는 맞지않다. 

 

 

ArrayList 와 LinkedList

 

 

 

 

ArrayList

 

add는 O(N)이지만 평균적으로는 O(1)이다 Capacity가 전부 찼을경우에만 O(N)인데 1.5배씩 크게 만들기 때문에 크기가 커질수록 grow가 적어진다. 더군다나 크기가 작을 때 grow는 O(상수)급이기에 크게 신경 ㄴㄴ 

결론: 최악 O(N)이지만 O(1)로 여겨도 크게 문제 없다. 코테에서는 신경쓰기

 

 

 

 

import java.util.Arrays;

public class MyArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private int size = 0;
    private Object[] data;

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

    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public void add(E element) {
        if (size == data.length)
            growCapacity();
        data[size++] = element;
    }

    private void growCapacity() {
        int newCapacity = data.length + (data.length >> 1);
        data = Arrays.copyOf(data, newCapacity);
    }

    public E get(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        return (E)data[idx];
    }

    public void set(int idx, E element) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        data[idx] = element;
    }

    public void insert(int idx, E element) {
        if (size == data.length) growCapacity();
        int copyLength = size - idx;
        System.arraycopy(data, idx, data, idx + 1, copyLength);
        data[idx] = element;
        size++;
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        int copyLength = data.length - idx - 1;
        System.arraycopy(data, idx + 1, data, idx, copyLength);
        size--;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for(int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(data[i].toString());
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main (String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>(4);
        // ArrayList는 initial capacity를 지정할 수 있습니다.
        // 지정하지 않는다면 default capacity만큼의 배열이 생성됩니다.

        // ArrayList의 add: O(1)
        list.add(1);            // [1]
        list.add(2);            // [1, 2]
        list.add(3);            // [1, 2, 3]
        list.add(4);            // [1, 2, 3, 4]
        // 현재 capacity를 넘게되면 내부적으로 증가시킨 배열로 값을 이동합니다.
        list.add(5);            // [1, 2, 3, 4, 5]

        // ArrayList의 특정 위치값에 대한 set: O(1)
        list.set(2, -1);        // [1, 2, -1, 4, 5]

        // ArrayList의 위치를 지정하는 insert: O(N)
        list.insert(3, 10);     // [1, 2, -1, 10, 4, 5]
        System.out.println(list);

        for (int i = 0; i < list.size(); i++) {
            // ArrayList의 특정 위치값에 대한 get: O(1)
            int num = list.get(i);
            System.out.printf("%d-th num: %d\n", i, num);
        }

        // ArrayList의 특정 위치값에 대한 remove: O(N)
        list.remove(1);             // [1, -1, 10, 4, 5]
        int size = list.size();     // 5
        System.out.printf("Size: %d, %s\n", size, list);
    }
}

 

LinkedList

 

 

 

 

add

 

 

get

 

 

insert

 

 

 

 

remove

 

 

 

 

java.util.List

 

 

public class MySingleLinkedList<E> {
    private int size = 0;
    private Node<E> firstNode = null;
    private Node<E> lastNode = null;

    public static class Node<E> {
        E item;
        Node<E> next;
        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element, firstNode);
        if (size == 0) lastNode = newNode;
        firstNode = newNode;
        size++;
    }

    public void add(E element) {
        Node<E> newNode = new Node<>(element, null);
        if (size == 0) firstNode = newNode;
        else lastNode.next = newNode;
        lastNode = newNode;
        size++;
    }

    public Node<E> getNode(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        Node<E> currentNode = firstNode;
        for (int i = 0; i < idx; i++)
            currentNode = currentNode.next;
        return currentNode;
    }

    public E get(int idx) {
        return getNode(idx).item;
    }

    public void set(int idx, E element) {
        Node<E> targetNode = getNode(idx);
        targetNode.item = element;
    }

    public void insert(Node<E> prevNode, E element) {
        Node<E> newNode = new Node<>(element, prevNode.next);
        prevNode.next = newNode;
        if (newNode.next == null)
            lastNode = newNode;
        size++;
    }

    public void insert(int idx, E element) {
        if (idx < 0 || idx > size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) addFirst(element);
        else if (idx == size) add((element));
        else insert(getNode(idx - 1), element);
    }

    public void removeFirst() {
        if (firstNode != null) {
            firstNode = firstNode.next;
            if (firstNode == null)
                lastNode = null;
            size--;
        }
    }

    public void removeNext(Node<E> prevNode) {
        if (prevNode.next != null) {
            prevNode.next = prevNode.next.next;
            if (prevNode.next == null)
                lastNode = prevNode;
            size--;
        }
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) removeFirst();
        else removeNext(getNode(idx - 1));
    }

    public Node<E> getFirstNode() {
        return firstNode;
    }

    public Node<E> getLastNode() {
        return lastNode;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> currentNode = firstNode;
        sb.append('[');
        for(int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(currentNode.item.toString());
            currentNode = currentNode.next;
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main (String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();

        // LinkedList의 add: O(1)
        list.add(1);            // [1]
        list.add(2);            // [1, 2]
        list.add(3);            // [1, 2, 3]

        // LinkedList의 특정 위치값에 대한 add: O(N)
        list.insert(0, 4);      // [4, 1, 2, 3]
        list.insert(3, 5);      // [4, 1, 2, 5, 3]

        // LinkedList의 특정 위치값에 대한 set: O(N)
        list.set(2, -1);        // [4, 1, -1, 5, 3]
        System.out.println(list);

        // LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
        // 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
        // ListIterator와는 달리 실제 Node를 가리킵니다.
        Node<Integer> currentNode = list.getFirstNode();

        // 2칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        int currentIndex = 0;   // index: 0, value: 4
        for (int i = 0; i < 2; i++) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        // index: 2, value: -1
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // LinkedList의 특정 위치값에 대한 get: O(N)
        System.out.printf("index: %d, value: %d\n", 4, list.get(4));

        // LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
        list.removeNext(currentNode);
        System.out.println(list);   // [4, 1, -1, 3]

        // LinkedList의 특정 위치값에 대한 remove: O(N)
        list.remove(3);             // [4, 1, -1];
        int size = list.size();     // 3
        System.out.printf("Size: %d, %s", size, list);
    }
}

 

public class MyDoubleLinkedList<E> {
    private int size = 0;
    private Node<E> firstNode = null;
    private Node<E> lastNode = null;

    public static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;
        Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.item = element;
            this.next = next;
        }
    }

    private void addFirst(E element) {
        Node<E> newNode = new Node<>(null, element, firstNode);
        if (size == 0) lastNode = newNode;
        else firstNode.prev = newNode;
        firstNode = newNode;
        size++;
    }

    public void add(E element) {
        Node<E> newNode = new Node<>(lastNode, element, null);
        if (size == 0) firstNode = newNode;
        else lastNode.next = newNode;
        lastNode = newNode;
        size++;
    }

    public Node<E> getNode(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        Node<E> currentNode = firstNode;
        for (int i = 0; i < idx; i++)
            currentNode = currentNode.next;
        return currentNode;
    }

    public E get(int idx) {
        return getNode(idx).item;
    }

    public void set(int idx, E element) {
        Node<E> targetNode = getNode(idx);
        targetNode.item = element;
    }

    public void insert(Node<E> prevNode, E element) {
        Node<E> newNode = new Node(prevNode, element, prevNode.next);
        if (newNode.next != null) newNode.next.prev = newNode;
        prevNode.next = newNode;
        if (newNode.next == null)
            lastNode = newNode;
        size++;
    }

    public void insert(int idx, E element) {
        if (idx < 0 || idx > size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        if (idx == 0) addFirst(element);
        else if (idx == size) add(element);
        else insert(getNode(idx - 1), element);
    }

    public void remove(Node<E> targetNode) {
        if (targetNode.prev != null)
            targetNode.prev.next = targetNode.next;
        else firstNode = targetNode.next;

        if (targetNode.next != null)
            targetNode.next.prev = targetNode.prev;
        else lastNode = targetNode.prev;

        targetNode.item = null;
        targetNode.prev = targetNode.next = null;
        size--;
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= size)
            throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
        remove(getNode(idx));
    }

    public Node<E> getFirstNode() {
        return firstNode;
    }

    public Node<E> getLastNode() {
        return lastNode;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> currentNode = firstNode;
        sb.append('[');
        for(int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(currentNode.item.toString());
            currentNode = currentNode.next;
        }
        sb.append(']');
        return sb.toString();
    }

    public static void main (String[] args) {
        MyDoubleLinkedList<Integer> list = new MyDoubleLinkedList<>();

        // LinkedList의 add: O(1)
        list.add(1);            // [1]
        list.add(2);            // [1, 2]
        list.add(3);            // [1, 2, 3]

        // LinkedList의 특정 위치값에 대한 add: O(N)
        list.insert(0, 4);      // [4, 1, 2, 3]
        list.insert(3, 5);      // [4, 1, 2, 5, 3]

        // LinkedList의 특정 위치값에 대한 set: O(N)
        list.set(2, -1);        // [4, 1, -1, 5, 3]
        System.out.println(list);

        // LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
        // 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
        // ListIterator와는 달리 실제 Node를 가리킵니다.
        Node<Integer> currentNode = list.getFirstNode();

        // 3칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        int currentIndex = 0;   // index: 0, value: 4
        for (int i = 0; i < 3; i++) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        // index: 3, value: 5
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // 계속 같은 변수를 사용해 2칸 앞 원소로 이동 후 현재 노드 정보를 출력하는 예제입니다.
        for (int i = 0; i < 2; i++) {
            currentNode = currentNode.prev;
            currentIndex--;
        }
        // index: 1, value: 1
        System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);

        // LinkedList의 특정 위치값에 대한 get: O(N)
        System.out.printf("index: %d, value: %d\n", 2, list.get(2));

        // LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
        list.remove(currentNode);
        System.out.println(list);   // [4, -1, 5, 3]

        // LinkedList의 특정 위치값에 대한 remove: O(N)
        list.remove(3);             // [4, -1, 5];
        int size = list.size();     // 3
        System.out.printf("Size: %d, %s", size, list);
    }
}

시간 복잡도 정리

 

 

 

 

사용 예시

ArrayList

import java.util.*;

class Main
{
    public static void main (String[] args) {
        List<Integer> list = new ArrayList<>(4);
        // ArrayList는 initial capacity를 지정할 수 있습니다.
        // 지정하지 않는다면 default capacity만큼의 배열이 생성됩니다.

        // ArrayList의 add: O(1)
        list.add(1);        // [1]
        list.add(2);        // [1, 2]
        list.add(3);        // [1, 2, 3]
        list.add(4);        // [1, 2, 3, 4]
        // 현재 capacity를 넘게되면 내부적으로 증가시킨 배열로 값을 이동합니다.
        list.add(5);        // [1, 2, 3, 4, 5]

        // ArrayList의 특정 위치값에 대한 set: O(1)
        list.set(2, -1);    // [1, 2, -1, 4, 5]

        // ArrayList의 위치를 지정하는 add(insert): O(N)
        list.add(3, 10);    // [1, 2, -1, 10, 4, 5]
        System.out.println(list);

        for (int i = 0; i < list.size(); i++) {
            // ArrayList의 특정 위치값에 대한 get: O(1)
            // 특성상 Iterator보다 index접근이 자주 사용되는 편입니다.
            int num = list.get(i);
            System.out.printf("%d-th num: %d\n", i, num);
        }

        // ArrayList의 중간 원소 삭제: O(N)
        list.remove(1);             // [1, -1, 10, 4, 5]
        int size = list.size();     // 5
        System.out.printf("Size: %d\n", size);

        // Collections의 sort, binarySearch 등을 사용할 수 있습니다.
        Collections.sort(list);
        System.out.println(list);   // [-1, 1, 4, 5, 10]
    }
}

 

LinkedList

import java.util.*;

class Main
{
    public static void main (String[] args) {
        List<Integer> list = new LinkedList<>();
        // 굳이 다형성을 사용할 필요가 없다면 아래와 같이 인스턴스를 만들어
        // LinkedList의 추가적인 메서드인 addFirst/Last 등을 사용할 수 있습니다.
        // LinkedList<Integer> list = new LinkedList<>();

        // LinkedList의 add: O(1)
        list.add(1);                // [1]
        list.add(2);                // [1, 2]
        list.add(3);                // [1, 2, 3]
        list.add(4);                // [1, 2, 3, 4]

        // LinkedList의 위치를 지정하는 add(insert): O(N)
        list.add(0, 5);             // [5, 1, 2, 3, 4]
        list.add(list.size(), 6);   // [5, 1, 2, 3, 4, 6]
        list.add(3, 7);             // [5, 1, 2, 7, 3, 4, 6]

        // LinkedList의 특정 위치값에 대한 set: O(N)
        list.set(2, -1);            // [5, 1, -1, 7, 3, 4, 6]
        System.out.println(list);

        // LinkedList의 특정 위치값에 대한 get: O(N)
        System.out.printf("index: %d, value: %d\n", 4, list.get(4));

        // LinkedList의 원소에 순차적으로 접근한다면 Iterator를 사용하는 것이 더 효율적입니다.
        // ListIterator는 내부적으로 next 노드를 가리키고 있어 이를 통해 앞/뒤로 이동할 수 있습니다.
        ListIterator<Integer> it = list.listIterator();
        // ListIterator 생성 시 아래와 같이 [0:list.size()] 범위에서 시작 위치를 지정할 수도 있습니다.
        // ListIterator<Integer> it = list.listIterator(3);

        // ListIterator를 3칸 뒤로 이동 후 상태를 확인하는 예제입니다.
        // 현재 Iterator: [^5, 1, -1, 7, 3, 4, 6]
        for (int i = 0; i < 3; i++)
            if (it.hasNext())
                it.next();
        // 현재 Iterator: [5, 1, -1,^ 7, 3, 4, 6]

        // ListIterator의 prev/next를 확인해 생각한 위치가 맞는지 확인할 수 있습니다.
        // ListIterator는 prev/next에 대한 단순 접근자를 제공하지 않기 때문에
        // previous(), next()를 통해 실제 이동 후 반환 된 값을 사용해야 합니다.
        int itIndex = it.nextIndex();           //  3 , [5, 1, -1,^ 7, 3, 4, 6]
        int prevValue = it.previous();          // -1 , [5, 1,^ -1, 7, 3, 4, 6]
        it.next();                              // 원복, [5, 1, -1,^ 7, 3, 4, 6]
        int nextValue = it.next();              //  7 , [5, 1, -1, 7,^ 3, 4, 6]
        it.previous();                          // 원복, [5, 1, -1,^ 7, 3, 4, 6]
        System.out.printf("position %d iterator's prev: %d, next: %d\n", itIndex, prevValue, nextValue);

        // ListIterator.set()은 iterator가 수행한 previous()와 next() 중 마지막으로 반환한 노드를 대상으로 합니다.
        // 마지막으로 반환된 노드는 previous()로 반환되었던 3번 노드(7)입니다.
        // LinkedList의 ListIterator를 통한 특정 노드 set: O(1)
        it.set(10);                             // [5, 1, -1,^ 10, 3, 4, 6]
        it.set(20);                             // [5, 1, -1,^ 20, 3, 4, 6]
        System.out.println(list);

        // ListIterator.remove() 역시 set()과 같이 마지막 반환되었던 노드를 대상으로 합니다.
        // 여전히 마지막으로 반환된 노드는 previous()로 지나온 3번 노드(20)입니다.
        // LinkedList의 ListIterator를 통한 특정 노드 remove: O(1)
        it.remove();                            // [5, 1, -1,^ 3, 4, 6]

        // 마지막으로 반환된 노드가 삭제되었으므로 다시 previous/next로 iterator를 이동하기 전에
        // it.set()이나 it.remove()를 사용하면 IllegalStateException이 발생합니다.
        // it.remove();                         // IllegalStateException
        it.next();                              // [5, 1, -1, 3,^ 4, 6]
        it.next();                              // [5, 1, -1, 3, 4,^ 6]

        // 마지막으로 next()를 통해 4번 노드(4)을 반환했으므로 set/remove는 해당 노드를 대상으로 동작합니다.
        it.remove();                            // [5, 1, -1, 3,^ 6]
        System.out.println(list);

        // ListIterator를 통한 이동 중에 노드를 삽입하고 싶다면 add()를 사용할 수 있습니다.
        // next 노드의 앞에 전달받은 값의 새로운 노드를 연결하며, 이때 set/remove를 위한 마지막 반환 노드 정보는 유실됩니다.
        // LinkedList의 ListIterator를 통한 노드 삽입 insert: O(1)
        it.previous();                          // [5, 1, -1,^ 3, 6]
        it.add(100);                            // [5, 1, -1,^ 100, 3, 6]
        // it.remove(), it.set()                // IllegalStateException
        System.out.println(list);

        // LinkedList의 특정 위치값에 대한 remove: O(N)
        list.remove(5);                         // [5, 1, -1, 100, 3]
        int size = list.size();                 // 5
        System.out.printf("Size: %d, %s\n", size, list);

        // Collections의 sort, binarySearch 등을 사용할 수 있습니다.
        // LinkedList의 get 복잡도로 인해 binarySearch와 같은 메서드는 비효율적일 수 있습니다.
        Collections.sort(list);                 // [-1, 1, 3, 5, 100]
        System.out.println(list);
    }
}

 

 

 

Queue & Deque (LinkedList)

import java.util.*;

class Main
{
    public static void main (String[] args) {
        // FIFO 특성을 지닌 큐의 가장 기본적인 구현체인 LinkedList를 사용합니다.
        Queue<Integer> q = new LinkedList<>();

        // 큐의 가장 뒤에 원소 추가: O(1)
        // 큐에 공간이 부족할 때 Exception이 발생하는 add와 false를 반환하는 offer가 제공됩니다.
        q.offer(1);                 // [1]
        q.offer(2);                 // [1, 2]
        q.add(3);                   // [1, 2, 3]
        q.add(4);                   // [1, 2, 3, 4]

        // 큐의 가장 앞 원소 삭제: O(1)
        // 큐가 비었을 때 Exception이 발생하는 remove와 null을 반환하는 poll이 제공됩니다.
        q.poll();                   // [2, 3, 4]
        q.remove();                 // [3, 4]

        // 큐의 가장 앞 원소 조회: O(1)
        // 큐가 비었을 때 Exception이 발생하는 element와 null을 반환하는 peek이 제공됩니다.
        System.out.println(q.peek());       // 3
        System.out.println(q.element());    // 3
    }
}

import java.util.*;

class Main
{
    public static void main (String[] args) {
        Deque<Integer> q = new LinkedList<>();

        // 덱의 가장 앞/뒤에 원소 추가: O(1)
        // 덱에 공간이 부족할 때 Exception이 발생하는 add와 false를 반환하는 offer가 제공됩니다.
        q.offerFirst(1);                    // [1]
        q.addFirst(2);                      // [2, 1]
        q.offerLast(3);                     // [2, 1, 3]
        q.addLast(4);                       // [2, 1, 3, 4]

        // 덱의 가장 앞/뒤 원소 삭제: O(1)
        // 덱이 비었을 때 Exception이 발생하는 remove와 null을 반환하는 poll이 제공됩니다.
        q.pollFirst();                      // [1, 3, 4]
        q.removeLast();                     // [1, 3]

        // 덱의 가장 앞/뒤 원소 조회: O(1)
        // 덱이 비었을 때 Exception이 발생하는 get과 null을 반환하는 peek이 제공됩니다.
        System.out.println(q.peekFirst());  // 1
        System.out.println(q.getLast());    // 3
    }
}