[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부터 5까지 구현해보도록 하겠습니다.

 

과제 2

ListNode 클래스

 

package com.company;

public class ListNode {

    private int value;
    private ListNode next;

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

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

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

}

 

LinkedList Interface

 

package com.company;

public interface LinkedList {
    public ListNode add(ListNode head, ListNode nodeToAdd, int position);

    public ListNode remove(ListNode head, int positionToRemove);

    boolean contains(ListNode head, ListNode nodeTocheck);
}

 

LinkedListImpl 클래스

 

package com.company;

public class LinkedListImpl implements LinkedList {

    private final ListNode listNode;

    public LinkedListImpl(ListNode listNode) {
        this.listNode = listNode;
    }

    @Override
    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        if(position<0){
            return null;
        }

        ListNode target = head;
        ListNode addNode = nodeToAdd;

        for(int i =0; i < position-1; i++){
            target = target.getNext();
            if(target == null){
                return head;
            }
        }

        while(addNode.getNext()!=null){
            addNode = addNode.getNext();
        }

        addNode.setNext(target.getNext());
        target.setNext(nodeToAdd);
        return head;
    }

    @Override
    public ListNode remove(ListNode head, int positionToRemove) {
        ListNode target = head;

        for(int i = 0; i < positionToRemove-1;i++){
            target = target.getNext();

            if(target == null){
                return head;
            }
        }

        ListNode removeNode = target.getNext();

        if(removeNode != null){
            target.setNext(removeNode.getNext());
        }

        return head;
    }

    @Override
    public boolean contains(ListNode head, ListNode nodeTocheck) {
        if(head == null){
            return false;
        }

        ListNode target = head;

        while(target!=null){
            System.out.println(target.getValue());
            if(target.getValue() == nodeTocheck.getValue())return true;
            target = target.getNext();
        }
        return false;
    }

    public void printList(ListNode head) {
        while (head != null) {
            System.out.println(head.getValue());
            head = head.getNext();
        }
    }

}

 

도메인하고 서비스를 분리하듯이 한 번 나눠서 작성해봤습니다. 이때까지만 해도 저는 ListNode와 LinkedList로 나눴을 때 과제 4,5번까지 귀찮아질 줄은 생각도 못했습니다.

 

테스트 코드

 

package com.company;


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

class LinkedListImplTest {

    @org.junit.jupiter.api.Test
    void testall() {
        ListNode head = new ListNode(1);

        LinkedListImpl linkedList = new LinkedListImpl(head);

        linkedList.add(head,new ListNode(2),1);
        linkedList.add(head,new ListNode(8),1);

        linkedList.remove(head,1);

        assertTrue(linkedList.contains(head,new ListNode(1)));
        assertFalse(linkedList.contains(head,new ListNode(8)));
        assertTrue(linkedList.contains(head,new ListNode(2)));

        linkedList.printList(head);
    }


}

 

과제3,4번

배열을 이용한 stack

package com.company;

public class ArrayStack {
    private int[] datas;
    private int size;
    private int pointer;

    public ArrayStack(int size){
        this.pointer = 0;
        this.size = size;
        this.datas = new int[size];
    }

    public void push(int data){
        if(pointer>=size){
            System.out.println("용량 초과");
            return;
        }
        this.datas[this.pointer++] = data;
    }

    public int pop(){
        return datas[--pointer];
    }

}

 

배열을 이용한 경우 size를 초과할 경우 유동적으로 늘리기 힘듭니다. 기왕 하려면 사이즈가 큰 배열을 하나 새로 생성하고 그곳으로 기존 배열에 있던 값들을 copy 해주어야 하는데 일단은 기능 위주로만 작성했습니다. 어차피 연결 리스트로 stack을 작성하면 size문제도 해결되니까요.

 

테스트 코드

 

package com.company;

import org.junit.jupiter.api.Test;

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

class ArrayStackTest {

    @Test
    void ArrayStackTest() {
        ArrayStack arrayStack = new ArrayStack(5);

        for(int i =0;i<5;i++){
            arrayStack.push(i);
        }

        assertEquals(4,arrayStack.pop());
    }

}

 

연결 리스트를 이용한 stack

 

package com.company;

public class ListStack {
    private ListNode head;

    private LinkedListImpl linkedList;

    public ListStack(int data){
        this.head = new ListNode(data);
        this.linkedList = new LinkedListImpl(this.head);
    }

    public void push(int data){
        ListNode node = new ListNode(data);
        this.linkedList.add(node,this.head,0);
        this.head = node;
    }

    public int pop(){
        int result = this.head.getValue();
        this.head = this.head.getNext();
        return result;
    }

}

 

테스트 코드

 

package com.company;

import org.junit.jupiter.api.Test;

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

class ListStackTest {

    @Test
    void stackTest(){
        ListStack listStack = new ListStack(0);

        listStack.push(1);
        listStack.push(4);

        assertEquals(4,listStack.pop());
    }


}

 

과제 5번

배열 Queue

원형 큐가 아닌 일반적인 형태의 Queue를 구현했습니다.

 

package com.company;

public class ArrayQueue {
    private int[] datas;
    private int size;
    private int front;
    private int rear;

    public ArrayQueue(int size){
        this.front = 0;
        this.rear = 0;
        this.size = size;
        this.datas = new int[size];
    }

    public boolean isFull(){
        if(rear > size-1){
            return true;
        }
        else{
            return false;
        }
    }

    public void push(int data){
        if(isFull()){
            System.out.println("용량 초과");
            return;
        }
        this.datas[this.rear++] = data;
    }

    public int pop(){
        if(front == rear){
            System.out.println("데이터 없음");
            return -1;
        }
        return datas[front++];
    }

    public int peek(){
        if(front == rear){
            System.out.println("데이터 없음");
            return -1;
        }
        return datas[front];
    }
}

 

테스트 코드

package com.company;

import org.junit.jupiter.api.Test;

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

class ArrayQueueTest {
    @Test
    void ArrayQueueTest() {
        ArrayQueue arrayQueue = new ArrayQueue(5);

        for(int i =0;i<5;i++){
            arrayQueue.push(i);
        }

        assertEquals(0,arrayQueue.pop());
        assertEquals(1,arrayQueue.pop());
        assertEquals(2,arrayQueue.peek());
        assertEquals(2,arrayQueue.peek());

        arrayQueue.push(10);
        //용량 초과
    }
}

 

연결리스트 Queue

 

package com.company;

public class ListQueue {
    private ListNode head;

    private LinkedListImpl linkedList;

    private int front;
    private int rear;

    public ListQueue(){
        this.head = new ListNode();
        this.linkedList = new LinkedListImpl(this.head);
        this.front = 0;
        this.rear = 0;
    }

    public ListQueue(int data){
        this.head = new ListNode(data);
        this.linkedList = new LinkedListImpl(this.head);
        this.front = 0;
        this.rear = 0;
    }

    public void push(int data){
        ListNode node = new ListNode(data);
        this.linkedList.add(this.head,node,++rear);
        System.out.println(this.head.getValue());
    }

    public int pop(){
        if(front == rear){
            System.out.println("데이터 없음");
            return -1;
        }

        int result = this.head.getValue();
        this.head = this.head.getNext();
        front++;
        System.out.println(this.head.getValue());
        return result;
    }
    public int peek(){
        if(front == rear){
            System.out.println("데이터 없음");
            return -1;
        }

        int result = this.head.getValue();
        //this.head = this.head.getNext();
        return result;
    }
}

 

pop 메서드를 보니 front 변수가 없었어도 되겠다는 생각이 드네요. 

테스트 코드

 

package com.company;

import org.junit.jupiter.api.Test;

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

class ListQueueTest {

    @Test
    void queueTest(){
        ListQueue listQueue = new ListQueue(0);

        listQueue.push(1);
        listQueue.push(4);

        assertEquals(0,listQueue.pop());

        listQueue.push(3);

        assertEquals(1,listQueue.pop());

    }

}

 

 

후기

 

연결리스트 분리를 꼭 했어야만 했는지 의문이 듭니다. 나중을 위해 미리 좋은 코드 습관을 들이고 싶어서 했던 행동이었으니 좋은 경험이 되었다고 자기 합리화를 해봅니다. 또 눈치채신 분이 계실지는 모르겠지만 저번과는 다른 assertion을 사용했습니다. 지난번에는 assertj의 assertions를 사용했다면 이번에는 juni5에서 제공하는 함수들로 사용했어요. 초보자답게 간단한 함수 3개만 사용해봤는데 나쁘지 않네요.

 

그리고 이런 자료구조 직접 구현해보는 건 오랜만이라 그런지 재밌었습니다.