Linked List

• Integer Ver.

public class MyLinkedList {
    public class Node {
        private Integer item;
        private Node next;

        public Node(Integer item) {
            this.item = item;
        }
    }
    private Node head = null;
    // add, delete, printall
    public void add(Integer item) {
        Node node = this.head;
        Node prev = this.head;
        if (head != null) {
            while(node != null) {
                if(node.item > item) {
                    if(prev == node) {
                        Node newNode = new Node(item);
                        newNode.next = head;
                        head = newNode;
                        return;
                    } else {
                        Node newNode = new Node(item);
                        newNode.next = prev.next;
                        prev.next = newNode;
                        return;
                    }
                }
                prev = node;
                node = node.next;
            }
            prev.next = new Node(item);
        } else {
            head = new Node(item);
        }
    }

    public boolean delete(Integer item) {
        if(this.head != null) {
            Node node = this.head;
            if(node.item == item) {
                this.head = this.head.next;
                return true;
            } else {
                while(node.next != null) {
                    if(node.next.item == item) {
                        node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                return false;
            }
        } else {
            return false;
        }
    }

    public void printAll() {
        Node node = this.head;
        if(head != null) {
            System.out.println(node.item);
            while(node.next != null) {
                node = node.next;
                System.out.println(node.item);
            }
        } else {
            System.out.println("No items.");
        }
    }

    public static void main(String[] args){
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.add(5);
        myLinkedList.add(3);
        myLinkedList.add(6);
        myLinkedList.add(2);
        myLinkedList.add(1);
        myLinkedList.add(4);
        myLinkedList.add(7);

        myLinkedList.printAll();

        myLinkedList.delete(5);
        myLinkedList.delete(2);
        myLinkedList.delete(7);
        myLinkedList.delete(1);
        myLinkedList.printAll();
    }

}

• Generic Ver.

public class MyLinkedList<T> {
    public class Node<T> {
        T item;
        Node<T> next = null;

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

    private Node<T> head = null;

    public void add(T item) {
        if(this.head == null) {
            this.head = new Node<T>(item);
        } else {
            Node<T> node = head;
            while(node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(item);
        }
    }

    public Node<T> search(T item){
        if(this.head == null) {
            return null;
        } else {
            Node<T> node = head;
            while(node != null) {
                if(node.item == item) {
                    return node;
                }
                node = node.next;
            }
        }
        return null;
    }

    public void addInside(T item, T isItem) {
        Node<T> searchedNode = this.search(isItem);

        if(searchedNode == null) {
            this.add(item);
        } else {
            Node<T> nextNode = searchedNode.next;
            searchedNode.next = new Node<T>(item);
            searchedNode.next.next = nextNode;
        }
    }

    public boolean delete(T isItem) {
        if(this.head == null) return false;
        else {
            Node<T> node = head;
            if(node.item == isItem) {
                this.head = this.head.next;
                return true;
            } else {
                while(node.next != null) {
                    if(node.next.item == isItem) {
                        node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                return false;
            }
        }
    }

    public void printAll() {
        if(this.head != null) {
            Node<T> node = head;
            System.out.println(node.item);
            while(node.next != null) {
                node = node.next;
                System.out.println(node.item);
            }
        } else {
            System.out.println("No item");
        }
    }

    public static void main(String[] args) {
        MyLinkedList<Integer> myLinkedList = new MyLinkedList<>();
        myLinkedList.add(1);
        myLinkedList.add(2);
        myLinkedList.add(3);
        myLinkedList.add(4);
        myLinkedList.add(5);

        myLinkedList.printAll();
        myLinkedList.delete(1);
        myLinkedList.delete(3);
        myLinkedList.delete(20);
        myLinkedList.printAll();
    }
}

Stack

public class MyStack {
    private int top;
    private int size;
    private int[] stack;

    public MyStack(int size) {
        this.size = size;
        this.top = -1;
        stack = new int[size];
    }

    public void push(int item) {
        stack[++top]= item;
    }
    public int pop(){
        int item = stack[top];
        stack[top--] = 0;
        return item;
    }

    public static void main(String[] args){
        MyStack myStack = new MyStack(6);
        myStack.push(5);
        myStack.push(4);
        myStack.push(3);
        myStack.push(2);
        myStack.push(1);
        myStack.pop();
        myStack.pop();
    }
}

Queue

public class MyQueue {
    int Max = 1000;
    int front;
    int rear;
    int[] queue;

    public MyQueue() {
        front = rear = 0;
        queue = new int[Max];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        if (rear == Max) {
            return true;
        } else {
            return false;
        }
    }

    public int size() {
        return rear - front;
    }

    public void push(int item) {
        if (isFull()) {
            System.out.println("queue is full.");
            return;
        }
        queue[rear++] = item;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("queue is empty.");
            return -1;
        }
        int item = queue[front];
        queue[front++] = 0;
        return item;
    }

    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(3);
        myQueue.push(2);
        myQueue.push(1);
        System.out.println(myQueue.size());
        myQueue.pop();
        myQueue.pop();
        myQueue.pop();
        myQueue.push(3);
        myQueue.push(2);
        myQueue.push(1);
        myQueue.push(3);
        myQueue.push(2);
        myQueue.push(1);
    }
}

Hash

// Hash Table : key에 data를 매핑할 수 있는 구조
// chaining 기법 사용.
public class MyHash {
    public class Slot {
        String value;
        String key;
        Slot next;
        Slot(String key, String value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    public Slot[] hashTable;

    public MyHash(Integer size) {
        hashTable = new Slot[size];
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0) % hashTable.length);
    }

    public boolean saveData(String key, String value) {
        Integer address = hashFunc(key);
        if (hashTable[address] != null) {
            Slot findSlot = hashTable[address]; // head
            Slot prevSlot = hashTable[address];
            while(findSlot != null) {
                if(findSlot.key == key) return true;
                else {
                    prevSlot = findSlot;
                    findSlot = findSlot.next;
                }
            }
            prevSlot.next = new Slot(key, value);
        } else {
            hashTable[address] = new Slot(key, value);
        }
        return true;
    }

    public String getData(String key) {
        Integer address = hashFunc(key);
        if ( hashTable[address] != null) {
            Slot findSlot = this.hashTable[address];
            while (findSlot != null) {
                if (findSlot.key == key) {
                    return findSlot.value;
                } else {
                    findSlot = findSlot.next;
                }
            }
            return null;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee","01022223333");
        mainObject.saveData("fun-coding", "01033334444");
        mainObject.saveData("David", "01044445555");
        mainObject.saveData("Dave","01055556666");
        System.out.println(mainObject.getData("DaveLee"));
        System.out.println(mainObject.getData("Dave"));
    }
}
*/

// Linear probing
// Hash Table : key에 data를 매핑할 수 있는 구조
public class MyHash {
    public class Slot {
        String value;
        String key;
        Slot(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public Slot[] hashTable;

    public MyHash(Integer size) {
        hashTable = new Slot[size];
    }

    public int hashFunc(String key) {
        return (int)(key.charAt(0) % hashTable.length);
    }

    public boolean saveData(String key, String value) {
        Integer address = hashFunc(key);
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) {
                this.hashTable[address].value = value;
                return true;
            } else {
                Integer currAddress = address + 1;
                while(this.hashTable[currAddress] != null) {
                    if(this.hashTable[currAddress].key == key) {
                        this.hashTable[currAddress].value = value;
                        return true;
                    } else {
                        currAddress++;
                        if(currAddress == this.hashTable.length) {
                            return false;
                        }
                    }
                }
                hashTable[currAddress] = new Slot(key, value);
                return true;
            }
        } else {
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }

    public String getData(String key) {
        Integer address = hashFunc(key);
        if(this.hashTable[address] != null) {
            if(this.hashTable[address].key == key) return this.hashTable[address].value;
            Integer currAddress = address + 1;
            while(this.hashTable[currAddress] != null) {
                if(this.hashTable[currAddress].key == key) {
                    return this.hashTable[address].value;
                } else {
                    currAddress++;
                    if(currAddress == this.hashTable.length) {
                        return null;
                    }
                }
            }
            return null;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        MyHash mainObject = new MyHash(20);
        mainObject.saveData("DaveLee","01022223333");
        mainObject.saveData("fun-coding", "01033334444");
        mainObject.saveData("David", "01044445555");
        mainObject.saveData("Dave","01055556666");
        System.out.println(mainObject.getData("DaveLee"));
        System.out.println(mainObject.getData("fun-coding"));
    }
}

public class MyHash {

    public static void main(String[] args) {
        HashMap<Integer, String> map1 = new HashMap();
        map1.put(1, "사과");
        map1.put(2, "바나나");
        map1.put(3, "포도");
        System.out.println(map1.get(2));
    }
}