자바로 자료구조 구현하기

ArrayList

public class ArrayList<T> {
    private int capacity = 100;
    private Object[] arr = new Object[capacity];
    private int size = 0;

    void add(Object o) {
        if (this.size >= this.arr.length) {
            Object[] newArr = new Object[this.size * 2];
            System.arraycopy(this.arr, 0, newArr, 0, this.arr.length);
            this.arr = newArr;
        }
        arr[this.size] = o;
        this.size++;
    }

    void remove(int idx) {
        System.arraycopy(this.arr, idx + 1, this.arr, idx, this.arr.length - idx - 1);
        this.size--;
    }

    T get(int idx) {
        if (idx >= this.size) return null;
        return (T) this.arr[idx];
    }

    boolean contains(Object o) {
        for (Object el : arr) {
            if (el.equals(o)) return true;
        }
        return false;
    }

    boolean isEmpty() {
        return this.size == 0;
    }

    int size() {
        return this.size;
    }

    Iterator iterator(){
        return new Iterator();
    }

    class Iterator {
        private int nextIdx = 0;

        boolean hasNext(){
            return this.nextIdx < size;
        }

        T next(){
            T item = get(nextIdx);
            nextIdx++;
            return item;
        }
    }
}

Map

Set

 

Stack

public class Stack<T> {
    private Node<T> top;

    public void push(T item) {
        Node<T> t = new Node<T>(item);
        t.next = top;
        top = t;
    }

    public T pop() {
        if (top == null) {
            throw new EmptyStackException();
        }

        T item = top.data;
        top = top.next;
        return item;
    }

    public T peek(){
        if (top == null) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty(){
        return top == null;
    }

    class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }
}

 

Queue

public class Queue<T> {
    private Node<T> first;
    private Node<T> last;

    public void enqueue(T item) {
        Node<T> t = new Node<T>(item);

        if (last != null) {
            last.next = t;
        }
        last = t;
        if (first == null) {
            first = last;
        }
    }

    public T dequeue() {
        if (first == null) {
            throw new NoSuchElementException();
        }

        T data = first.data;
        first = first.next;

        if (first == null) {
            last = null;
        }

        return data;
    }

    public T front() {
        if (first == null) {
            throw new NoSuchElementException();
        }
        return first.data;
    }

    public boolean isEmpty() {
        return first == null;
    }

    class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }
}

선입선출의 구조이므로 시작 데이터와 끝 데이터를 가지고 있어야함

시작 데이터 - 출력할 때 시작 지점

끝 데이터 - 데이터 삽입시 위치

deque(double ended queue) 시작 부분에서도 데이터 삽입 되게 만들면 됨

PriorityQueue

 

 

asdf