STUDY HALLE - 4주차 추가 과제(2)

과제 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를 사용해서 한번.

---

LinkedList 구현하기

컬렉션 프레임워크

컬렉션 프레임워크 : 프로그램 구현에 필요한 자료구조와 알고리즘을 구현해 놓은 라이브러리

• java.util 패키지에 구현되어 있다.
• 개발에 소요되는 시간을 절약하고 최적화된 라이브러리를 사용할 수 있다.
• Collection 인터페이스와 Map 인터페이스로 구성되어 있다.
• Collection : 하나의 객체 관리를 위해 선언된 인터페이스
  • List : 순서가 있으며 중복을 허용하는 자료구조
  • Set : 순서가 정해져있지 않으며 중복을 허용하지 않는 자료구조
• Map : 쌍으로 이루어진 객체 관리를 위해 선언된 인터페이스
  • Map을 사용하는 객체는 key-value 쌍으로 되어있으며 Key는 중복될 수 없다.

List 인터페이스 :

• 객체를 순서에따라 저장하고 관리하는데 필요한 메서드가 선언된 인터페이스
• Collection의 하위 인터페이스
• 배열의 기능을 구현하기 위한 메서드가 선언됨
• ArrayList, Vector, LinkedList

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {

        LinkedList<String> myList = new LinkedList<String>();

        myList.add("A");
        myList.add("B");
        myList.add("C");

        System.out.println(myList);
        myList.add(1,"D");

        System.out.println(myList);

        for(int i=0;i<myList.size();i++) {
            String s = myList.get(i);
            System.out.println(s);
        }
    }
}

Set 인터페이스 :

• Collection 하위의 인터페이스
• 중복을 허용하지 않으며 순서가 없다.
• get(i) 메서드를 제공하지 않는다.(대신 Iterator 순회사용)
  • Iterator ir = new memberArrayList.iterator();
• 아이디, 주민번호, 사번 등 유일한 값이나 객체를 관리할 때 사용한다.
• HashSet, TreeSet

public class HashSetTest {
    public static void main(String[] args) {

        HashSet<String> set = new HashSet<String>();

        set.add("이순신");
        set.add("김유신");
        set.add("강감찬");
        set.add("이순신");

        System.out.println(set); //순서가 없음, 중복 불가

        Iterator<String> ir = set.iterator(); //모든 Collection 객체에서 사용가능하다.

        while(ir.hasNext()) {
            String str = ir.next(); //순회 선언시 Iterator<String>으로 선언하였기 때문에 반환값은 String이 된다.
            System.out.println(str);
        }

    }
}

ArrayList vs LinkedList

• 둘다 자료의 순차적 구조를 구현한 클래스이다.
• ArrayList는 물리적 순서와 논리적 순서가 동일하다. (검색용)
• LinkedList는 논리적으로는 순차적이지만 물리적으로는 순차적이지 않을 수 있다. (변경용)
  • LinkedList는 노드마다 다음 노드에 대한 Link를 가지고 있다.
  • 데이터 삽입 또는 삭제시 해당 노드만 제거하고 Link만 조정하면 되므로 ArrayList에 비해 빠르다.
  • 데이터 검색시 첫 노드부터 순차적으로 검색해야 하므로 ArrayList에 비해 느리다.

사진 출처 : https://codenuclear.com/difference-between-arraylist-and-linkedlist-arraylist-vs-linkedlist

LinkedList 구현하기

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

ListNode Class

public class ListNode {

    public ListNode() {
    }

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

    public int value; //노드의 data
    public ListNode nextNode; //다음 노드에 대한 링크

    public static ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        ListNode currentNode = head;
        int lastLoop = position - 1;

        if ( position == 0 ) {
            nodeToAdd.nextNode = currentNode;
        } else { 
            for ( int i=0; i<position; i++ ) {
                if ( currentNode.nextNode != null && i < lastLoop ) {
                    currentNode = currentNode.nextNode;
                } else if ( i == lastLoop ) {
                    if ( currentNode.nextNode != null ) {
                        nodeToAdd.nextNode = currentNode.nextNode;
                    }
                    currentNode.nextNode = nodeToAdd;
                } else {
                    throw new RuntimeException("position "+position+" out of index.");
                }
            }
        }
        return nodeToAdd;
    }

    public static ListNode remove(ListNode head, int positionToRemove) {
        ListNode currentNode = head;
        int lastLoop = positionToRemove - 1;
        ListNode nodeToRemove = null;

        if ( positionToRemove == 0 ) {
            nodeToRemove = head;
            head.nextNode = null;
        } else {
            for ( int i=0; i<positionToRemove; i++ ) {
                if ( currentNode.nextNode != null && i < lastLoop ) {
                    currentNode = currentNode.nextNode;
                } else if ( i == lastLoop ) {
                    nodeToRemove = currentNode.nextNode;
                    currentNode.nextNode = currentNode.nextNode.nextNode;
                } else {
                    throw new RuntimeException("position "+positionToRemove+" out of index.");
                }
            }
        }
        return nodeToRemove;
    }

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

        while ( currentNode != nodeTocheck ) {
            if ( currentNode.nextNode != null ) {
                currentNode = currentNode.nextNode;
            } else {
                break;
            }
        }
        if ( currentNode == nodeTocheck ) {
            return true;
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

ListNode Test

import org.junit.jupiter.api.Test;

import static me.rockintuna.demospringdata.ListNode.*;
import static org.assertj.core.api.Assertions.assertThat;

class ListNodeTest {

    @Test
    public void addTest() {
        ListNode listNode1 = new ListNode(30);
        ListNode listNode2 = new ListNode(60);
        ListNode listNode3 = new ListNode(90);
        ListNode listNode4 = new ListNode(120);

        add(listNode1, listNode2, 1);
        add(listNode1, listNode3, 2);
        add(listNode1, listNode4, 3);

        assertThat(listNode1.value).isEqualTo(30);
        assertThat(listNode1.nextNode.value).isEqualTo(60);
        assertThat(listNode1.nextNode.nextNode.value).isEqualTo(90);
        assertThat(listNode1.nextNode.nextNode.nextNode.value).isEqualTo(120);

        ListNode removedNode = remove(listNode1, 1);

        assertThat(removedNode.value).isEqualTo(60);

        assertThat(listNode1.value).isEqualTo(30);
        assertThat(listNode1.nextNode.value).isEqualTo(90);
        assertThat(listNode1.nextNode.nextNode.value).isEqualTo(120);

        assertThat(contains(listNode1, listNode3)).isTrue();
        assertThat(contains(listNode1, removedNode)).isFalse();
    }
}

---

Stack 구현하기

LIFO (Last In, Fist Out)
관련 용어 : pop, push, top

Stack 클래스 구현

public class MyStack {
    public int[] arrayStack;

    public void push(int data) {
        if ( arrayStack == null ) {
            arrayStack = new int[1];
            arrayStack[0] = data;
        } else {
            int length = arrayStack.length;
            int[] newArrayStack = new int[length+1];
            for (int i=0; i<length; i++) {
                newArrayStack[i] = arrayStack[i];
            }
            arrayStack = newArrayStack;
            arrayStack[length] = data;
        }
    }

    public int pop() {
        if ( arrayStack == null ) {
            throw new RuntimeException("스택이 비어있습니다.");
        } else {
            int length = arrayStack.length;
            int data =  arrayStack[length-1];
            int[] newArrayStack = new int[length-1];
            for (int i=0; i<length-1; i++) {
                newArrayStack[i] = arrayStack[i];
            }
            arrayStack = newArrayStack;
            return data;
        }
    }
}

테스트

class MyStackTest {

    @Test
    public void test() {
        MyStack myStack = new MyStack();
        assertThat(myStack.arrayStack).isNull();

        myStack.push(1);
        assertThat(myStack.arrayStack[0]).isEqualTo(1);
        myStack.push(3);
        assertThat(myStack.arrayStack[1]).isEqualTo(3);
        myStack.push(100);
        assertThat(myStack.arrayStack[2]).isEqualTo(100);

        assertThat(myStack.pop()).isEqualTo(100);
        assertThat(myStack.pop()).isEqualTo(3);
        assertThat(myStack.pop()).isEqualTo(1);

        assertThrows(RuntimeException.class, () -> myStack.pop());
    }
}

---

ListNode를 사용해서 Stack 구현하기

ListNodeStack 클래스 구현

public class ListNodeStack {
    ListNode node;

    void push(int data) {
        if ( node == null ) {
            node = new ListNode(data);
        } else {
            int position = getLastPosition();
            add(node, new ListNode(data), position+1);
        }
    }

    int pop() {
        if ( node == null ) {
            throw new RuntimeException("스택이 비어있습니다.");
        } else {
            int position = getLastPosition();
            ListNode removed = remove(node, position);
            if ( position == 0 ) {
                node = null;
            }
            return removed.value;
        }
    }

    int getLastPosition() {
        ListNode currentNode = node;
        int position = 0;
        while ( currentNode.nextNode != null ) {
            currentNode = currentNode.nextNode;
            position++;
        }
        return position;
    }
}

테스트

class ListNodeStackTest {

    @Test
    public void test() {
        ListNodeStack stack = new ListNodeStack();
        assertThat(stack.node).isNull();
        stack.push(1);
        assertThat(stack.node.value).isEqualTo(1);
        stack.push(3);
        assertThat(stack.node.nextNode.value).isEqualTo(3);
        stack.push(100);
        assertThat(stack.node.nextNode.nextNode.value).isEqualTo(100);

        assertThat(stack.pop()).isEqualTo(100);
        assertThat(stack.pop()).isEqualTo(3);
        assertThat(stack.pop()).isEqualTo(1);
        assertThat(stack.node).isNull();

        assertThrows(RuntimeException.class, () -> stack.pop());
    }
}

---

Queue 구현하기

FIFO (First In, First Out)
관련용어 : front, rear, enqueue, dequeue

• void enqueue(int data)
  큐 마지막(rear)에 데이터를 삽입

• int dequeue()
  큐의 첫 번째 위치(front)의 데이터를 반환하고 큐에서 삭제

• boolean isEmpty()
  큐가 empty 상태인지 확인

• void clear()
  큐에 저장된 모든 데이터를 삭제하고 큐를 초기화

• int peek()
  큐의 첫 번째 위치에 있는 데이터를 추출, 삭제는 하지 않는다.

배열로 구현

public class MyQueue {
    public int[] arrayQueue;

    public void enqueue(int data) {
        if ( isEmpty() ) {
            arrayQueue = new int[1];
            arrayQueue[0] = data;
        } else {
            int length = arrayQueue.length;
            int[] newArrayQueue = new int[length+1];
            for (int i=0; i<length; i++) {
                newArrayQueue[i] = arrayQueue[i];
            }
            arrayQueue = newArrayQueue;
            arrayQueue[length] = data;
        }
    }

    public int dequeue() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            int length = arrayQueue.length;
            int data = arrayQueue[0];
            int[] newArrayQueue = new int[length-1];
            for (int i=0; i<length-1; i++) {
                newArrayQueue[i] = arrayQueue[i+1];
            }
            arrayQueue = newArrayQueue;
            return data;
        }
    }

    public boolean isEmpty() {
        if ( arrayQueue == null ) {
            return true;
        } else {
            return false;
        }
    }

    public void clear() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            arrayQueue = null;
        }
    }

    public int peek() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            return arrayQueue[0];
        }
    }
}

테스트

class MyQueueTest {

    @Test
    public void test() {
        MyQueue myQueue = new MyQueue();
        assertThat(myQueue.isEmpty()).isTrue();

        myQueue.enqueue(1);
        assertThat(myQueue.arrayQueue[0]).isEqualTo(1);
        myQueue.enqueue(3);
        assertThat(myQueue.arrayQueue[1]).isEqualTo(3);
        myQueue.enqueue(100);
        assertThat(myQueue.arrayQueue[2]).isEqualTo(100);

        assertThat(myQueue.dequeue()).isEqualTo(1);
        assertThat(myQueue.dequeue()).isEqualTo(3);
        assertThat(myQueue.peek()).isEqualTo(100);

        myQueue.clear();
        assertThrows(RuntimeException.class, () -> myQueue.dequeue());
    }
}

ListNode로 구현

public class ListNodeQueue {
    public ListNode front;

    public void enqueue(int data) {
        if ( isEmpty() ) {
            front = new ListNode(data);
        } else {
            int position = getLastPosition();
            add(front, new ListNode(data), position+1);
        }
    }

    public int dequeue() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            ListNode newFront = front.nextNode;
            ListNode removed = remove(front, 0);
            front = newFront;
            return removed.value;
        }
    }

    public boolean isEmpty() {
        if ( front == null ) {
            return true;
        } else {
            return false;
        }
    }

    public void clear() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            front = null;
        }
    }

    public int peek() {
        if ( isEmpty() ) {
            throw new RuntimeException("큐가 비어있습니다.");
        } else {
            return front.value;
        }
    }

    int getLastPosition() {
        ListNode currentNode = front;
        int position = 0;
        while ( currentNode.nextNode != null ) {
            currentNode = currentNode.nextNode;
            position++;
        }
        return position;
    }

}

테스트

class ListNodeQueueTest {
    @Test
    public void test() {
        ListNodeQueue myQueue = new ListNodeQueue();
        assertThat(myQueue.isEmpty()).isTrue();

        myQueue.enqueue(1);
        assertThat(myQueue.front.value).isEqualTo(1);
        myQueue.enqueue(3);
        assertThat(myQueue.front.nextNode.value).isEqualTo(3);
        myQueue.enqueue(100);
        assertThat(myQueue.front.nextNode.nextNode.value).isEqualTo(100);

        assertThat(myQueue.dequeue()).isEqualTo(1);
        assertThat(myQueue.dequeue()).isEqualTo(3);
        assertThat(myQueue.peek()).isEqualTo(100);

        myQueue.clear();
        assertThrows(RuntimeException.class, () -> myQueue.dequeue());
    }
}