[Java] 연결리스트(Linked List), Stack, Queue 구현

github.com/whiteship/live-study/issues/4

---

과제 2. LinkedList를 구현하세요.

• LinkedList에 대해 공부하세요.
• 정수를 저장하는 ListNode 클래스를 구현하세요.
• ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
• ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
• boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.

head는 노드를 가리키는 next 포인터 정보를 가진다.

각 노드들은 값을 저장하는 데이터와 다음 노드를 가리키는 next를 가진다.

 

next에는 주소 정보를 저장하여 다음 노드를 연결하고 있기 때문에 노드의 추가, 삭제 시 효율적으로 할 수 있다.

배열의 경우 요소의 추가, 삭제 시 빈 공간을 메워주기 위한 후속처리가 필요하다.

 

그러나 특정 인덱스에 있는 데이터 검색 시 배열은 인덱스 정보로 원하는 데이터에 바로 접근이 가능하지만 

연결리스트는 head부터 원하는 데이터로 도달할 때까지 인덱스 수 만큼의 노드를 탐색해야 하기 때문에 검색 시엔 비효율적이다.

 

class ListNode {

    int data;
    ListNode next;

    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }

    public ListNode(int data) {
        this.data = data;
        this.next = null;
    }

}

class LinkedList {

    private ListNode head;

    public LinkedList() {
        this.head = null;
    }

    ListNode add(ListNode nodeToAdd, int position) {
        if (head == null) {
            head = nodeToAdd;
        } else {
            ListNode node = head;
            for (int i = 0; i < position - 1; i++) {
                node = node.next;
            }
            nodeToAdd.next = node.next;
            node.next = nodeToAdd;
        }

        return head;
    }

    public ListNode remove(int positionToRemove) {
        if (head == null) {
            return head;
        }
        if (positionToRemove == 0) {
            head = head.next;
            return head;
        }

        ListNode node = head;
        for (int i = 0; i < positionToRemove - 1; i++) {
            if (node == null) {
                return head;
            }
            node = node.next;
        }
        node.next = node.next.next;

        return head;
    }

    boolean contains(ListNode nodeToCheck) {
        ListNode node = head;
        while (node != null) {
            if (node.data == nodeToCheck.data) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

}

---

과제 3. Stack을 구현하세요.

• int 배열을 사용해서 정수를 저장하는 Stack을 구현하세요.
• void push(int data)를 구현하세요.
• int pop()을 구현하세요.

class Stack {

    private int array[];
    private int top;
    private int size;

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

    void push(int data) {
        if (top == size - 1) {
            throw new RuntimeException("out of index");
        }
        array[++top] = data;
    }

    int pop() {
        if (top == -1) {
            throw new RuntimeException("out of index");
        }
        return array[top--];
    }
}

---

과제 4. 앞서 만든 ListNode를 사용해서 Stack을 구현하세요.

• ListNode head를 가지고 있는 ListNodeStack 클래스를 구현하세요.
• void push(int data)를 구현하세요.
• int pop()을 구현하세요.

class ListNodeStack {

    private ListNode head;

    public ListNodeStack() {
        this.head = null;
    }

    void push(int data) {
        ListNode newNode = new ListNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = newNode;
    }

    int pop() {
        if (head == null) {
            throw new RuntimeException("out of index");
        }
        ListNode before = null;
        ListNode node = head;
        while (node.next != null) {
            before = node;
            node = node.next;
        }
        int data = node.data;
        if (before == null) {
            head = null;
        } else {
            before.next = null;
        }
        return data;
    }
}

---

과제 5. Queue를 구현하세요.

• 배열을 사용해서 한번

class Queue {

    private Integer array[];
    private int front;
    private int back;
    private int size;

    public Queue(int size) {
        this.size = size;
        this.array = new Integer[size];
        this.front = -1;
        this.back = -1;
    }

    void push(int data) {
        back++;
        if (back >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        array[back] = data;
        if(front == -1) front = back;
    }

    int pop() {
        if (front >= size || front < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return array[front++];
    }
}

배열을 이용해서 큐를 구현할 경우 배열의 인덱스인 front, back는 항상 증가만 하기 때문에 pop해서 더 이상 사용하지 않는 front 인덱스 앞부분은 더 이상 사용하지 않는다. -> 메모리 낭비 

 

• ListNode를 사용해서 한번.

class ListNodeQueue {

    private ListNode head;

    public ListNodeQueue() {
        this.head = null;
    }

    void push(int data) {
        ListNode newNode = new ListNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = newNode;
    }

    int pop() {
        if (head == null) {
            throw new RuntimeException("out of index");
        }

        int data = head.data;
        head = head.next;
        return data;
    }
}