Java Study 2-2주차

1. LinkedList 구현

package data_structure;  
  
public class MakeLinkedList {  
    public static void main(String[] args) {  
        LinkedList<Integer> list = new LinkedList<>();  
        list.add(1,0);  
        list.add(2,1);  
        list.add(3,2);  
        System.out.println(list.get(0));  
        System.out.println(list.get(1));  
        list.remove(1);  
        System.out.println(list.get(0));  
        if(list.contains(3)){  
            System.out.println("having");  
        }  
        else{  
            System.out.println("not have");  
        }  
    }  
}  
  
class ListNode<E> {  
    public E data;  
    public ListNode<E> next;  
  
    ListNode(E data) {  
        this.data = data;  
        this.next = null;  
    }  
}  
  
class LinkedList<E> {  
    ListNode<E> head;  
    ListNode<E> tail;  
    int size;  
  
    public LinkedList() {  
        this.head = null;  
        this.tail = null;  
    }  
  
    public void addFirst(E data){  
        head = new ListNode<>(data);  
        tail = head.next;  
        size++;  
    }  
  
    public void add(E data, int index) {  
        if (index > size + 1) {  
            throw new IndexOutOfBoundsException();  
        }  
        if(head == null){  
            addFirst(data);  
            return;        }  
  
        ListNode<E> LHead = head;  
        for (int i = 0; i < index-1; i++) {  
            LHead = LHead.next;  
        }  
        ListNode<E> preNode = LHead;  
        ListNode<E> nextNode = LHead.next;  
        ListNode<E> newNode = new ListNode<>(data);  
        preNode.next = newNode;  
        newNode.next = nextNode;  
        size++;  
  
        if(newNode.next == null){  
            tail = newNode;  
        }  
    }  
  
    public void removeFirst(){  
        head = head.next;  
        size--;  
    }  
  
    public void remove(int index){  
        if (index > size + 1) {  
            throw new IndexOutOfBoundsException();  
        }  
        if(index == 0){  
            removeFirst();  
            return;        }  
        ListNode<E> LHead = head;  
        for (int i = 0; i < index-1; i++) {  
            LHead = LHead.next;  
        }  
        ListNode<E> preNode = LHead;  
        ListNode<E> nowNode = LHead.next;  
        ListNode<E> nextNode = nowNode.next;  
  
        preNode.next = nextNode;  
        nowNode.next = null;  
        size--;  
    }  
  
    public boolean contains(E data){  
        ListNode<E> LHead = head;  
        for (int i = 0; i < size; i++) {  
            if(LHead.data.equals(data)){  
                return true;  
            }  
            LHead = LHead.next;  
        }  
        return false;  
    }  
  
    public E get(int index){  
        ListNode<E> LHead = head;  
        for (int i = 0; i < index; i++) {  
            LHead = LHead.next;  
        }  
        return LHead.data;  
    }  
}

2-1. 배열로 Stack 구현

package data_structure;  
  
public class MakearrayStack {  
    public static void main(String[] args) {  
        Stack<Integer> stack = new Stack<>(5);  
        stack.push(5);  
        stack.push(10);  
        stack.push(15);  
        System.out.println(stack.pop());  
    }  
}  
  
class Stack<E>{  
    int size;  
    E[] data;  
    int nowSize;  
    public Stack(int size){  
        this.size = size;  
        data = (E[]) new Object[size];  
        nowSize = 0;  
    }  
  
    public void push(E data){  
        if(nowSize == size){  
            System.out.println("넣는거 불가능");  
            return;        }  
        this.data[nowSize++] = data;  
    }  
  
    public E pop(){  
        nowSize--;  
        E popData = this.data[nowSize];  
        this.data[nowSize] = null;  
        return popData;  
    }  
}

2-2. LinkedList로 Stack 구현

package data_structure;  
  
public class MakeListNodeStack {  
    public static void main(String[] args) {  
        ListStack<Integer> stack = new ListStack<>();  
        stack.push(1);  
        stack.push(2);  
        stack.push(3);  
        System.out.println(stack.pop());  
        System.out.println(stack.pop());  
        System.out.println(stack.pop());  
    }  
}  
  
class Node<E> {  
    public E data;  
    public Node<E> next;  
  
    Node(E data) {  
        this.data = data;  
        this.next = null;  
    }  
}  
  
class ListStack<E> {  
    Node<E> head;  
    Node<E> tail;  
    int size;  
  
    public ListStack() {  
        this.head = null;  
        this.tail = null;  
    }  
    public void addFirst(E data){  
        head = new Node<>(data);  
        tail = head.next;  
        size++;  
    }  
    public void push(E data){  
        if(size == 0){  
            addFirst(data);  
            return;        }  
        Node<E> LHead = head;  
        for (int i = 0; i < size-1; i++) {  
            LHead = head.next;  
        }  
        Node<E> preNode = LHead;  
        Node<E> nextNode = LHead.next;  
        Node<E> newNode = new Node<>(data);  
        preNode.next = newNode;  
        newNode.next = nextNode;  
        size++;  
        tail = newNode;  
    }  
    public E removeFirst(){  
        E popData = head.data;  
        head = head.next;  
        size--;  
        return popData;  
    }  
    public E pop(){  
        if(size == 1){  
            E popData = removeFirst();  
            return popData;  
        }  
        Node<E> LHead = head;  
        for (int i = 0; i < size-2; i++) {  
            LHead = LHead.next;  
        }  
        Node<E> preNode = LHead;  
        Node<E> nowNode = LHead.next;  
  
        E popData = nowNode.data;  
        preNode.next = null;  
        tail = preNode;  
        size--;  
        return popData;  
    }  
  
  
}

3-1. 배열로 Queue 구현

package data_structure;  
  
  
public class MakearrayQueue {  
    public static void main(String[] args) {  
        arrayQueue<Integer> q = new arrayQueue<>(5);  
        q.add(1);  
        q.add(2);  
        q.add(3);  
        System.out.println(q.poll());  
        System.out.println(q.poll());  
    }  
}  
  
class arrayQueue<E>{  
    int size;  
    E[] data;  
    int nowSize;  
    public arrayQueue(int size){  
        this.size = size;  
        data = (E[]) new Object[size];  
        nowSize = 0;  
    }  
  
    public void add(E data){  
        if(nowSize == size){  
            System.out.println("넣는거 불가능");  
            return;        }  
        this.data[nowSize++] = data;  
    }  
  
    public E poll(){  
        nowSize--;  
        E popData = this.data[0];  
        this.data[0] = null;  
        for (int i = 0; i < nowSize; i++) {  
            this.data[i] = this.data[i+1];  
        }  
        this.data[nowSize] = null;  
        return popData;  
    }  
}

3-2 LinkedList Queue 구현

package data_structure;  
  
public class MakeLinkedQueue {  
    public static void main(String[] args) {  
        ListQueue<Integer> q = new ListQueue<>();  
        q.add(1);  
        q.add(2);  
        q.add(3);  
        System.out.println(q.poll());  
        System.out.println(q.poll());  
        System.out.println(q.poll());  
    }  
}  
  
  
class ListQueue<E> {  
    Node<E> head;  
    Node<E> tail;  
    int size;  
  
    public ListQueue() {  
        this.head = null;  
        this.tail = null;  
    }  
    public void addFirst(E data){  
        head = new Node<>(data);  
        tail = head.next;  
        size++;  
    }  
    public void add(E data){  
        if(size == 0){  
            addFirst(data);  
            return;        }  
        Node<E> LHead = head;  
        for (int i = 0; i < size-1; i++) {  
            LHead = head.next;  
        }  
        Node<E> preNode = LHead;  
        Node<E> nextNode = LHead.next;  
        Node<E> newNode = new Node<>(data);  
        preNode.next = newNode;  
        newNode.next = nextNode;  
        size++;  
        tail = newNode;  
    }  
    public E removeFirst(){  
        E popData = head.data;  
        head = head.next;  
        size--;  
        return popData;  
    }  
    public E poll(){  
        E popData = removeFirst();  
        return popData;  
  
    }  
  
}