[Java] LinkedList, Stack, Queue
Web/Java

[Java] LinkedList, Stack, Queue

목차 (클릭시 해당 목차로 이동)

     

     

     

     

    요구사항

     

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

     

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

     

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

     

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


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

     

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

     

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

     

    • 배열을 사용해서 한번
    • ListNode를 사용해서 한번.

     

     

     

     

     

     

    2. LinkedList를 구현하세요.

     

     

    • HEAD는 추가하거나 삭제할 수 없다는 예외를 임의로 추가했습니다.
    • 예외처리 대신에 print를 했습니다.
    • 중간중간 노드가 제대로 들어갔는지 확인을 위해 print 메서드를 구현했습니다.

     

    package javastudy.ch4.assignment2;

public class ListNode {
    int node;
    ListNode nextNode = null;


    public ListNode() {
    }

    public ListNode(int node) {
        this.node = node;
    }

    public ListNode(int node, ListNode nextNode) {
        this.node = node;
        this.nextNode = nextNode;
    }

    public void add(ListNode head, ListNode nodeToAdd, int position) {
        if (position == 0) {
            System.out.println("HEAD는 추가할 수 없습니다.");
            return;
        }

        ListNode currentNode = head;
        ListNode preNode = currentNode;
        for (int i = 0; i < position; i++) {
            preNode = currentNode;
            currentNode = currentNode.nextNode;
        }

        preNode.nextNode = nodeToAdd;
        nodeToAdd.nextNode = currentNode;
    }

    public void remove(ListNode head, int positionToRemove) throws Throwable {
        if (positionToRemove == 0) {
            System.out.println("HEAD는 삭제할 수 없습니다.");
            return;
        }

        ListNode currentNode = head;
        ListNode preNode = currentNode;



        for (int i = 0; i < positionToRemove; i++) {
            if (currentNode == null) {
                System.out.println("지우려는 위치에 노드가 없습니다.");
                return;
            }

            preNode = currentNode;
            currentNode = currentNode.nextNode;
        }

        preNode.nextNode = currentNode.nextNode;
        currentNode = null;
    }

    public boolean contains(ListNode head, ListNode nodeToCheck) {
        ListNode currentNode = head;

        while (currentNode.nextNode != null) {
            if (currentNode == nodeToCheck) {
                return true;
            }
            currentNode = currentNode.nextNode;
        }

        if (currentNode == nodeToCheck) {
            return true;
        } else {
            return false;
        }
    }

    public void print(ListNode head) {
        ListNode currentNode = head;
        System.out.println("HEAD");

        while (currentNode.nextNode != null) {
            currentNode = currentNode.nextNode;
            if (currentNode != null) {
                System.out.println(currentNode.node);
            }
        }
    }
}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class ListNodeTest {
    @Test
    @DisplayName("ListNodeTest")
    public void nodeTest() throws Throwable {
        //given
        ListNode head = new ListNode();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        //when
        head.add(head, node1, 1);
        head.add(head, node2, 2);
        head.add(head, node3, 3);
        head.add(head, node4, 4);
        head.add(head, node5, 5);

        head.remove(head, 3);


        //then
        assertAll("assertAll",
                () -> assertTrue(head.contains(head, node1)),
                () -> assertTrue(head.contains(head, node2)),
                () -> assertFalse(head.contains(head, node3)),
                () -> assertTrue(head.contains(head, node4)),
                () -> assertTrue(head.contains(head, node5)));
    }

}

     

     

     

    3. Stack을 구현하세요. (배열을 이용해)

     

    배열은 vector가 아니기 때문에 배열의 크기를 초과해 push할 경우 배열의 크기를 늘려주어야 했습니다.

    그래서 기존 배열의 길이의 2배인 새로운 배열을 만들고 해당 배열에 기존배열의 데이터를 옮겨주었습니다.

     

    배열이 비어있을때 pop을 할 경우 -1을 리턴하고 "Stack이 비어있습니다"라는 문구를 출력합니다.

     

    package javastudy.ch4.assignment2;

public class Stack {
    private int[] stArr = new int[10];
    private int top = -1;

    public Stack() {
        initializer();
    }

    private void initializer() {
        for (int i = 0; i < stArr.length; i++) {
            stArr[i] = -1;
        }
    }

    public void push(int data) {
        if (top == stArr.length-1) { // 배열이 꽉찼다면 배열의 크기를 두배로 늘림
            int[] newStArr = new int[stArr.length * 2];
            for (int i = 0; i < stArr.length * 2; i++) {
                if (i < stArr.length) {
                    newStArr[i] = stArr[i];
                } else {
                    newStArr[i] = -1;
                }

            }
            stArr = newStArr;
        }

        top += 1;
        stArr[top] = data;

    }

    public int pop() {
        if (top == -1) {
            System.out.println("Stack이 비어있습니다");
            return -1;
        }

        int res = stArr[top];
        stArr[top] = -1;
        top -= 1;
        return res;
    }

    public void print() {
        String data = "";
        for (int i = 0; i < stArr.length; i++) {
            data += (stArr[i] + ", ");
        }

        System.out.println("data = " + data);
        System.out.println("top = " + top);

    }
}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class StackTest {

    @Test
    @DisplayName("StackTest")
    public void stackTest() throws Exception {
        //given
        Stack st = new Stack();

        for (int i = 0; i < 15; i++) {
            st.push(i);
        }

        //when


        //then
        for (int i = 14; i >= -1; i--) {
            assertEquals(i, st.pop());
        }
    }

}

     

     

     

     

     

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

     

    배열로 Stack을 구현했을때와 달리 길이를 신경쓰지 않아주어도 되는 장점이 있습니다.

    하지만 push나 pop을 할 경우 끝을 찾아가기위해 항상 리스트를 끝까지 탐색해야 하는 단점이 있었습니다.

     

    package javastudy.ch4.assignment2;

public class ListNodeStack {
    private ListNode head;

    public ListNodeStack() {
        this.head = new ListNode();
    }

    public void push(int data) {
        ListNode currentNode = head;

        while (currentNode.nextNode != null) {
            currentNode = currentNode.nextNode;
        }

        ListNode newNode = new ListNode(data);
        currentNode.nextNode = newNode;
    }

    public int pop() throws Throwable {
        int res = -1;
        ListNode currentNode = head;
        ListNode preNode = currentNode;

        while (currentNode.nextNode != null) {
            preNode = currentNode;
            currentNode = currentNode.nextNode;
        }

        if (currentNode == head) {
            System.out.println("HEAD는 pop할 수 없습니다.");
            return res;
        }

        res = currentNode.node;
        preNode.nextNode = null;

        return res;
    }

    public void print() {
        ListNode currentNode = head;
        System.out.println("HEAD");

        while (currentNode.nextNode != null) {
            currentNode = currentNode.nextNode;
            if (currentNode != null) {
                System.out.println(currentNode.node);
            }
        }
    }
}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class ListNodeStackTest {

    @Test
    @DisplayName("ListNodeStackTest")
    public void test() throws Throwable {
        //given

        ListNodeStack st = new ListNodeStack();


        for (int i = 1; i < 15; i++) {
            st.push(i);
        }
        //when


        //then
        for (int i = 14; i > -1; i--) {
            if (i == 0) {
                assertEquals(-1, st.pop());
            } else {
                assertEquals(i, st.pop());
            }
        }
    }

}

     

     

     

     

    5. Queue를 구현하세요.

     

     

    배열 이용

     

    배열을 이용해 Queue를 구현하면 Stack때와 마찬가지로 배열의 크기를 초과하는 push가 들어왔을경우 배열의 크기를 늘려주어야했습니다.

     

    또한, pop을 할때 왼쪽부터 데이터를 반환하기 때문에 pop이 여러번 일어날 경우 왼쪽부분에서 데이터의 낭비가 발생했습니다.

     

    package javastudy.ch4.assignment2;

import java.util.Arrays;

public class ArrayQueue {
    private int[] array = new int[10];
    private int left;
    private int right;

    public ArrayQueue() {
        initializer();
        this.left = 0;
        this.right = -1;
    }

    private void initializer() {
        Arrays.fill(array, -1);
    }

    public void append(int data) {
        if (right == array.length-1) { // 배열이 꽉찼다면 배열의 크기를 두배로 늘림
            int[] newStArr = new int[array.length * 2];
            for (int i = 0; i < array.length * 2; i++) {
                if (left <= i && i <= right) {
                    newStArr[i] = array[i];
                } else {
                    newStArr[i] = -1;
                }

            }
            array = newStArr;
        }

        right += 1;
        array[right] = data;

    }

    public int pop() {
        if (right - left < 0) {
            System.out.println("Queue가 비어있습니다.");
            return -1;
        }

        int res = array[left];
        array[left] = -1;
        left += 1;
        return res;
    }

    public void print() {
        if (right - left < 0) {
            System.out.println("Queue가 비어있습니다.");
            return;
        }

        for (int i = left; i < right + 1; i++) {
            System.out.println(array[i]);
        }
    }
}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class ArrayQueueTest {

    @Test
    @DisplayName("ArrayQueueTest")
    public void test() throws Exception {
        //given
        ArrayQueue queue = new ArrayQueue();

        for (int i = 0; i < 15; i++) {
            queue.append(i);
        }

//        queue.print();

        //when

        //then
        for (int i = 0; i < 16; i++) {
            if (i == 15) {
                assertEquals(-1, queue.pop());
            } else {
                assertEquals(i, queue.pop());
            }
        }

        queue.print();

    }

}

     

     

     

     

    ListNode 이용

     

    이번엔 항상 데이터의 끝을 탐색해야하는 리소스를 줄이기 위해 ptr이라는 reference 변수를 선언해 사용했습니다.

    ptr은 항상 맨 끝의 리스트를 가리키고 있으므로 append할때 ptr의 nextNode로 연결해준 뒤 ptr은 추가된 Node를 가리키도록 했습니다.

     

     

    package javastudy.ch4.assignment2;

public class ListNodeQueue {
    private ListNode head;
    private ListNode ptr;

    public ListNodeQueue() {
        head = new ListNode();
        this.ptr = head;
    }

    public void append(int data) {
        ListNode newNode = new ListNode(data);
        ptr.nextNode = newNode;
        ptr = newNode;
    }

    public int pop() throws Throwable {
        if (head == ptr) {
            System.out.println("Queue가 비어있습니다.");
            return -1;
        }

        int res = head.nextNode.node;

        if (head.nextNode == ptr) {
            ptr = head;
        }

        head.remove(head, 1);
        return res;
    }

    public void print() {
        ListNode currentNode = head;
        System.out.println("HEAD");

        while (currentNode.nextNode != null) {
            currentNode = currentNode.nextNode;
            System.out.println(currentNode.node);
        }
    }

}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class ListNodeQueueTest {

    @Test
    public void ListNodeQueueTest() throws Throwable {
        //given
        ListNodeQueue queue = new ListNodeQueue();

        for (int i = 0; i < 15; i++) {
            queue.append(i);
        }
        //when
        queue.print();

        //then
        for (int i = 0; i < 16; i++) {
            if (i == 15) {
                assertEquals(-1, queue.pop());
            } else {
                assertEquals(i, queue.pop());
            }
        }

        for (int i = 0; i < 15; i++) {
            queue.append(i);
        }

        for (int i = 0; i < 16; i++) {
            if (i == 15) {
                assertEquals(-1, queue.pop());
            } else {
                assertEquals(i, queue.pop());
            }
        }

        queue.print();
    }

}
    package javastudy.ch4.assignment2;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class ListNodeQueueTest {

    @Test
    public void ListNodeQueueTest() throws Throwable {
        //given
        ListNodeQueue queue = new ListNodeQueue();

        for (int i = 0; i < 15; i++) {
            queue.append(i);
        }
        //when
//        queue.print();

        //then
        for (int i = 0; i < 16; i++) {
            if (i == 15) {
                assertEquals(-1, queue.pop());
            } else {
                assertEquals(i, queue.pop());
            }
        }

        for (int i = 0; i < 15; i++) {
            queue.append(i);
        }

        for (int i = 0; i < 16; i++) {
            if (i == 15) {
                assertEquals(-1, queue.pop());
            } else {
                assertEquals(i, queue.pop());
            }
        }

//        queue.print();
    }

}

     

     

     

     

    https://github.com/dongho108/java-study/tree/master/src/main/java/javastudy/ch4/assignment2

     

    'Web > Java' 카테고리의 다른 글

    [Java] Node와 BinaryTree 구현  (2) 2021.07.08
    [Java] 클래스  (0) 2021.07.08
    [Java] GitHub API를 이용한 대시보드 만들기  (2) 2021.07.05
    [Java] JUnit5  (0) 2021.07.05
    [Java] 제어문  (0) 2021.07.05

      티스토리툴바