# 자료구조 만들어보기

## 배열 리스트 (Array List)

1. MyList 클래스를 생성한다.
2. 배열을 사용하여 리스트를 구현한다.
3. add() 메소드를 사용하여 요소를 추가한다.
4. get() 메소드를 사용하여 요소를 조회한다.
5. size() 메소드를 사용하여 리스트의 크기를 조회한다.
6. remove() 메소드를 사용하여 요소를 삭제한다.

### 배열 리스트 (Array List) 코드

public class MyArrayList {
    private int[] array;
    private int size;

    public MyArrayList() {
        array = new int[10];
        size = 0;
    }

    public void add(int value) {
        if (size >= array.length) {
            int[] newArray = new int[array.length * 2];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        array[size++] = value;
    }

    public int get(int index) {
        return array[index];
    }

    public int size() {
        return size;
    }

    public void remove(int index) {
        System.arraycopy(array, index + 1, array, index, size - index - 1);
        size--;
    }
}

public class Main {
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();

        list.add(10);
        list.add(20);
        list.add(30);

        System.out.println(list.size());

        System.out.println("---------");
        
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("---------");

        list.remove(1);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

## 연결 리스트 (Linked List)

1. 데이터와 다음 노드를 저장할 Node 클래스를 생성한다.
2. add() 메소드를 사용하여 요소를 추가한다.
3. get() 메소드를 사용하여 요소를 조회한다.
4. size() 메소드를 사용하여 리스트의 크기를 조회한다.
5. remove() 메소드를 사용하여 요소를 삭제한다.

### 연결 리스트 (Linked List) 코드

public class MyLinkedList {
    public static class Node {
        int data;
        Node next;

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

    private Node head;
    private int size;

    public void add(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
        size++;
    }

    public int get(int index) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }

    public int size() {
        return size;
    }

    public void remove(int index) {
        if (index == 0) {
            head = head.next;
        } else {
            Node node = head;
            for (int i = 0; i < index - 1; i++) {
                node = node.next;
            }
            node.next = node.next.next;
        }
        size--;
    }
}

public class Main {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();

        list.add(10);
        list.add(20);
        list.add(30);

        System.out.println(list.size());

        System.out.println("---------");

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("---------");

        list.remove(1);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

## 스택 (Stack)

1. MyStack 클래스를 생성한다.
2. 배열을 사용하여 스택을 구현한다.
3. push() 메소드를 사용하여 요소를 추가한다.
4. pop() 메소드를 사용하여 요소를 제거한다.
5. peek() 메소드를 사용하여 요소를 조회한다.
6. size() 메소드를 사용하여 스택의 크기를 조회한다.

### 스택 (Stack) 코드

public class MyStack {
    private int[] array;
    private int size;

    public MyStack() {
        array = new int[10];
        size = 0;
    }

    public void push(int value) {
        if (size >= array.length) {
            int[] newArray = new int[array.length * 2];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        array[size++] = value;
    }

    public int pop() {
        return array[--size];
    }

    public int peek() {
        return array[size - 1];
    }

    public int size() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println(stack.size());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }
}

## 큐 (Queue)

1. MyQueue 클래스를 생성한다.
2. 배열을 사용하여 큐를 구현한다.
3. add() 메소드를 사용하여 요소를 추가한다.
4. poll() 메소드를 사용하여 요소를 제거한다.
5. peek() 메소드를 사용하여 요소를 조회한다.
6. size() 메소드를 사용하여 큐의 크기를 조회한다.

### 큐 (Queue) 코드

public class MyQueue {
    private int[] array;
    private int size;
    private int front;
    private int rear;

    public MyQueue() {
        array = new int[10];
        size = 0;
        front = 0;
        rear = 0;
    }

    public void add(int value) {
        if (size >= array.length) {
            int[] newArray = new int[array.length * 2];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        array[rear] = value;
        rear = (rear + 1) % array.length;
        size++;
    }

    public int poll() {
        int value = array[front];
        front = (front + 1) % array.length;
        size--;
        return value;
    }

    public int peek() {
        return array[front];
    }

    public int size() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();

        queue.add(10);
        queue.add(20);
        queue.add(30);

        System.out.println(queue.size());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.peek());
    }
}

## 데크 (Deque, Double-Ended Queue)

1. MyDeque 클래스를 생성한다.
2. 배열을 사용하여 데크를 구현한다.
3. addFirst() 메소드를 사용하여 요소를 앞쪽에 추가한다.
4. addLast() 메소드를 사용하여 요소를 뒤쪽에 추가한다.
5. pollFirst() 메소드를 사용하여 요소를 앞쪽에서 제거한다.
6. pollLast() 메소드를 사용하여 요소를 뒤쪽에서 제거한다.
7. peekFirst() 메소드를 사용하여 요소를 앞쪽에서 조회한다.
8. peekLast() 메소드를 사용하여 요소를 뒤쪽에서 조회한다.
9. size() 메소드를 사용하여 데크의 크기를 조회한다.

### 데크 (Deque, Double-Ended Queue) 코드

public class MyDeque {
    private int[] array;
    private int size;
    private int front;
    private int rear;

    public MyDeque() {
        array = new int[10];
        size = 0;
        front = 0;
        rear = 0;
    }

    public void addFirst(int value) {
        if (size >= array.length) {
            int[] newArray = new int[array.length * 2];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        front = (front - 1 + array.length) % array.length;
        array[front] = value;
        size++;
    }

    public void addLast(int value) {
        if (size >= array.length) {
            int[] newArray = new int[array.length * 2];
            System.arraycopy(array, 0, newArray, 0, array.length);
            array = newArray;
        }
        array[rear] = value;
        rear = (rear + 1) % array.length;
        size++;
    }

    public int pollFirst() {
        int value = array[front];
        front = (front + 1) % array.length;
        size--;
        return value;
    }

    public int pollLast() {
        rear = (rear - 1 + array.length) % array.length;
        int value = array[rear];
        size--;
        return value;
    }

    public int peekFirst() {
        return array[front];
    }

    public int peekLast() {
        return array[(rear - 1 + array.length) % array.length];
    }

    public int size() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {
        MyDeque deque = new MyDeque();

        deque.addFirst(10);
        deque.addLast(20);
        deque.addLast(30);

        System.out.println(deque.size());
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollLast());
        System.out.println(deque.peekFirst());
    }
}

## 이진 트리 (Binary Tree)

1. 데이터와 왼쪽 자식 노드, 오른쪽 자식 노드를 저장할 Node 클래스를 생성한다.
2. insert() 메소드를 사용하여 요소를 추가한다.
3. contains() 메소드를 사용하여 요소를 조회한다.
4. delete() 메소드를 사용하여 요소를 삭제한다.

### 이진 트리 (Binary Tree) 코드

public class MyBinaryTree {
    public static class Node {
        int data;
        Node left;
        Node right;

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

    private Node root;

    public void insert(int value) {
        root = insert(root, value);
    }

    private Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.data) {
            node.left = insert(node.left, value);
        } else if (value > node.data) {
            node.right = insert(node.right, value);
        }

        return node;
    }

    public boolean contains(int value) {
        return contains(root, value);
    }

    private boolean contains(Node node, int value) {
        if (node == null) {
            return false;
        }

        if (value < node.data) {
            return contains(node.left, value);
        } else if (value > node.data) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    public void delete(int value) {
        root = delete(root, value);
    }

    private Node delete(Node node, int value) {
        if (node == null) {
            return null;
        }

        if (value < node.data) {
            node.left = delete(node.left, value);
        } else if (value > node.data) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.data = findMin(node.right).data;
            node.right = delete(node.right, node.data);
        }

        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        MyBinaryTree tree = new MyBinaryTree();

        tree.insert(10);
        tree.insert(20);
        tree.insert(30);

        System.out.println(tree.contains(20));
        tree.delete(20);
        System.out.println(tree.contains(20));
    }
}

## 트리 셋 (Tree Set)

1. 앞서 만든 이진 트리를 사용하여 트리 셋을 구현한다.
2. add() 메소드를 사용하여 요소를 추가한다.
3. contains() 메소드를 사용하여 요소를 조회한다.
4. remove() 메소드를 사용하여 요소를 삭제한다.

### 트리 셋 (Tree Set) 코드

public class MyTreeSet {
    public static class Node {
        int data;
        Node left;
        Node right;

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

    private Node root;

    public void add(int value) {
        root = add(root, value);
    }

    private Node add(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.data) {
            node.left = add(node.left, value);
        } else if (value > node.data) {
            node.right = add(node.right, value);
        }

        return node;
    }

    public boolean contains(int value) {
        return contains(root, value);
    }

    private boolean contains(Node node, int value) {
        if (node == null) {
            return false;
        }

        if (value < node.data) {
            return contains(node.left, value);
        } else if (value > node.data) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    public void remove(int value) {
        root = remove(root, value);
    }

    private Node remove(Node node, int value) {
        if (node == null) {
            return null;
        }

        if (value < node.data) {
            node.left = remove(node.left, value);
        } else if (value > node.data) {
            node.right = remove(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.data = findMin(node.right).data;
            node.right = remove(node.right, node.data);
        }

        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        MyTreeSet set = new MyTreeSet();

        set.add(10);
        set.add(20);
        set.add(30);

        System.out.println(set.contains(20));
        set.remove(20);
        System.out.println(set.contains(20));
    }
}

## 트리 맵 (Tree Map)

1. 앞서 만든 이진 트리를 사용하여 트리 셋을 구현한다.
2. put() 메소드를 사용하여 요소를 추가한다.
3. get() 메소드를 사용하여 요소를 조회한다.
4. remove() 메소드를 사용하여 요소를 삭제한다.

### 트리 맵 (Tree Map) 코드

public class MyTreeMap {
    public static class Node {
        int key;
        int value;
        Node left;
        Node right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node root;

    public void put(int key, int value) {
        root = put(root, key, value);
    }

    private Node put(Node node, int key, int value) {
        if (node == null) {
            return new Node(key, value);
        }

        if (key < node.key) {
            node.left = put(node.left, key, value);
        } else if (key > node.key) {
            node.right = put(node.right, key, value);
        } else {
            node.value = value;
        }

        return node;
    }

    public Integer get(int key) {
        return get(root, key);
    }

    private Integer get(Node node, int key) {
        if (node == null) {
            return null;
        }

        if (key < node.key) {
            return get(node.left, key);
        } else if (key > node.key) {
            return get(node.right, key);
        } else {
            return node.value;
        }
    }

    public void remove(int key) {
        root = remove(root, key);
    }

    private Node remove(Node node, int key) {
        if (node == null) {
            return null;
        }

        if (key < node.key) {
            node.left = remove(node.left, key);
        } else if (key > node.key) {
            node.right = remove(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            Node min = findMin(node.right);
            node.key = min.key;
            node.value = min.value;
            node.right = remove(node.right, node.key);
        }

        return node;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        MyTreeMap map = new MyTreeMap();

        map.put(10, 100);
        map.put(20, 200);
        map.put(30, 300);

        System.out.println(map.get(20));
        map.remove(20);
        System.out.println(map.get(20));
    }
}