Java/STUDY HALLE

[Java] 선형 자료구조

무토(MUTO) 2020. 12. 7. 01:57

0.선형 자료구조

https://goodgid.github.io/DS-Linear-and-NonLinear/

위의 그림과 같이 하나의 자료 뒤에 하나의 자료가 1:1관계로 존재하는 것을 선형 자료구조라고 한다.

선형자료구조에는 배열, 연결리스트, 스택, 큐, 덱 등이 있다.
이번 포스트에서는 연결리스트, 스택, 큐의 기본적인 로직을 직접 구현해보려고 한다.

1.연결리스트

1-1.연결리스트는 무엇일까?

https://medium.com/wasd/c-c-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-1-41a312399a8f

위의 그림과 같이 연결리스트는 하나의 노드가 다음 노드의 주소를 저장하는 방식으로 값을 저장하는 선형 자료구조이다.

따라서 값의 삽입, 삭제의 수행시간이 배열 기반의 자료구조보다 빠르고,
읽기의 수행시간이 배열기반의 자료구조보다 오래걸린다.

1-2. 연결리스트 구현

public class ListNode {

    int number;

    ListNode node;

    ListNode top;

    public ListNode() {

    }

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

    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        top = head;
        for (int i = 0; i < position; i++) {
            top = top.node;
        }
        if (top.node != null) {
            nodeToAdd.node = top.node;
        }
        top.node = nodeToAdd;
        return head;
    }

    public int getPositionNumber(ListNode head, int position) {
        top = head;
        top = top.node;
        for (int i = 0; i < position; i++) {
            top = top.node;
        }
        return top.number;
    }

    public ListNode remove(ListNode head, int positionToRemove) {
        top = head;
        ListNode remove;
        for (int i = 0; i < positionToRemove; i++) {
            top = top.node;
        }
        if (top.node.node == null) {
            remove = top.node;
            top.node = null;
        } else {
            remove = top.node;
            top.node = top.node.node;
        }
        return remove;
    }

    public boolean contains(ListNode head, ListNode nodeToCheck) {
        top = head;
        top = top.node;
        while (top != null) {
            if (top.number == nodeToCheck.number) {
                return true;
            }
            top = top.node;
        }
        return false;
    }

    public int size() {
        int count = 0;
        ListNode top = this;
        top = top.node;
        while (top != null) {
            top = top.node;
            count++;
        }
        return count;
    }

    public void setNode(ListNode node) {
        this.node = node;
    }

    public ListNode getNode() {
        return node;
    }

    public int getNumber() {
        return number;
    }
}

3.연결리스트 테스트

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

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

@DisplayName("LIST NODE 테스트")
class ListNodeTest {

    @Nested
    @DisplayName("ADD 테스트")
    class ListNodeAddTest {

        ListNode list;

        @BeforeEach
        void setList() {
            list = getListNode();
        }

        @Test
        @DisplayName("ADD_FIRST")
        void addFirst() {
            list.add(list,new ListNode(10),0);

            assertEquals(10,list.getPositionNumber(list,0));
            assertEquals(1,list.getPositionNumber(list,1));
            assertEquals(2,list.getPositionNumber(list,2));
            assertEquals(3,list.getPositionNumber(list,3));

            assertEquals(4,list.size());
        }

        @Test
        @DisplayName("ADD_MIDDLE")
        void addMiddle() {
            list.add(list,new ListNode(10),1);

            assertEquals(1,list.getPositionNumber(list,0));
            assertEquals(10,list.getPositionNumber(list,1));
            assertEquals(2,list.getPositionNumber(list,2));
            assertEquals(3,list.getPositionNumber(list,3));

            assertEquals(4,list.size());
        }

        @Test
        @DisplayName("ADD_LAST")
        void addLast() {
            list.add(list,new ListNode(10),3);

            assertEquals(1,list.getPositionNumber(list,0));
            assertEquals(2,list.getPositionNumber(list,1));
            assertEquals(3,list.getPositionNumber(list,2));
            assertEquals(10,list.getPositionNumber(list,3));

            assertEquals(4,list.size());
        }
    }

    @Nested
    @DisplayName("REMOVE 테스트")
    class ListNodeRemoveTest {

        ListNode list;

        @BeforeEach
        void setList() {
            list = getListNode();
        }

        @Test
        @DisplayName("REMOVE_FIRST")
        void test_add_first() {
            list.remove(list,0);

            assertEquals(2,list.getPositionNumber(list,0));
            assertEquals(3,list.getPositionNumber(list,1));

            assertEquals(2,list.size());
        }

        @Test
        @DisplayName("REMOVE_MIDDLE")
        void test_add_middle() {
            list.remove(list,1);

            assertEquals(1,list.getPositionNumber(list,0));
            assertEquals(3,list.getPositionNumber(list,1));

            assertEquals(2,list.size());
        }

        @Test
        @DisplayName("REMOVE_LAST")
        void test_add_last() {
            list.remove(list,2);

            assertEquals(1,list.getPositionNumber(list,0));
            assertEquals(2,list.getPositionNumber(list,1));

            assertEquals(2,list.size());
        }
    }

    @Nested
    @DisplayName("CONTAINS 테스트")
    class ListNodeContainsTest {

        ListNode list;

        @BeforeEach
        void setList() {
            list = getListNode();
        }

        @Test
        @DisplayName("CONTAINS_FIRST")
        void test_add_first() {
            assertTrue(list.contains(list, new ListNode(1)));
        }

        @Test
        @DisplayName("CONTAINS_MIDDLE")
        void test_add_middle() {
            assertTrue(list.contains(list, new ListNode(2)));
        }

        @Test
        @DisplayName("CONTAINS_LAST")
        void test_add_last() {
            assertTrue(list.contains(list, new ListNode(3)));
        }
    }

    private ListNode getListNode() {
        ListNode list = new ListNode();
        list.add(list, new ListNode(1), 0);
        list.add(list, new ListNode(2), 1);
        list.add(list, new ListNode(3), 2);
        return list;
    }

}

2.Stack

2-1. 스택은 무엇일까?

http://www.incodom.kr/%EC%8A%A4%ED%83%9D

위의 그림과 같이 스택은 한 방향에서만 삽입과 삭제가 이루어지는 선입후출 형태의 선형 자료구조이다.

컴퓨터의 시스템 실행이 이와같은 스택 형태의 구조로 이루어진다.

2-2-1. 스택 구현(배열)

배열 기반의 자료구조는 구현할 때 동적으로 용량을 체크하여 늘려주는 로직을 필요로 한다. 이 점을 감안하여 코드를 작성하도록 한다.

public class Stack {

    int[] arr;
    private int capacity;
    private int size;
    private int top;

    public Stack() {
        this.arr = new int[5];
        capacity = 5;
        top = -1;
    }

    public void push(int data) {
        top++;
        arr[top] = data;
        size++;
        checkSize();
    }

    public int pop() {
        size--;
        top--;
        return arr[top + 1];
    }

    public int peek() {
        return arr[top];
    }

    private void sizeUp() {
        int[] newArray = new int[2 * capacity];
        System.arraycopy(arr, 0, newArray, 0, capacity);
        capacity *= 2;
        arr = newArray;
    }

    private boolean isLeftOne() {
        return size == capacity - 1;
    }

    private void checkSize() {
        if (isLeftOne()) {
            sizeUp();
        }
    }

    public int getSize() {
        return size;
    }
}

2-2-2. 스택 테스트(배열)

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

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

class StackTest {

    Stack stack;

    @BeforeEach
    void init() {
        stack = new Stack();
        stack.push(1);
        stack.push(3);
        stack.push(2);
        stack.push(9);
        stack.push(7);
    }

    @Test
    void push() {
        assertEquals(5, stack.getSize());
        assertEquals(7, stack.peek());

        stack.push(10);

        assertEquals(6, stack.getSize());
        assertEquals(10, stack.peek());
    }

    @Test
    void pop() {
        assertEquals(5, stack.getSize());
        assertEquals(7, stack.peek());

        int pop = stack.pop();

        assertEquals(4, stack.getSize());
        assertEquals(7, pop);
    }

}

2-3-1. 스택 구현(ListNode)


import issue4.chapter2.ListNode;

public class ListNodeStack {

    ListNode head;

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

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

    public int pop() {
        return head.remove(head, 0).getNumber();
    }

    public int peek() {
        head.setNode(head.getNode());
        return head.getNode().getNumber();
    }

    public int getSize() {
        return head.size();
    }
}

2-3-2. 스택 테스트(ListNode)

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

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

class ListNodeStackTest {

    ListNodeStack stack;

    @BeforeEach
    void init() {
        stack = new ListNodeStack();
        stack.push(1);
        stack.push(3);
        stack.push(2);
        stack.push(9);
        stack.push(7);
    }

    @Test
    void push() {
        assertEquals(5, stack.getSize());
        assertEquals(7, stack.peek());

        stack.push(10);

        assertEquals(6, stack.getSize());
        assertEquals(10, stack.peek());
    }

    @Test
    void pop() {
        assertEquals(5, stack.getSize());
        assertEquals(7, stack.peek());

        int pop = stack.pop();

        assertEquals(4, stack.getSize());
        assertEquals(7, pop);
    }

}

3.Queue

3-1. 큐는 무엇일까?

위의 그림과 같이 한쪽에서는 삽입만 이루어지고 반대방향에서는 삭제만 이루어지는 형태의 자료구조를 큐라고 한다.

우리의 프로그램이 프로세스를 스케쥴링할때 사용하는 자료구조가 바로 큐이다.

3-2-1. 큐 구현(배열)

이것도 배열 기반의 자료구조이므로 구현할 때 동적으로 용량을 체크하여 늘려주는 로직을 작성 해야한다. 이 점을 감안하는것을 잊지말자.

public class ArrayQueue {

    int[] arr;
    private int capacity;
    private int size;
    private int tail;

    public ArrayQueue() {
        this.arr = new int[5];
        capacity = 5;
        tail = -1;
    }

    public void offer(int data) {
        tail++;
        arr[tail] = data;
        size++;
        checkSize();
    }

    public int poll() {
        int tmp = arr[0];
        fillEmptyPlace();
        size--;
        tail--;
        return tmp;
    }

    private void fillEmptyPlace() {
        if (arr.length - 1 >= 0) {
            System.arraycopy(arr, 1, arr, 0, arr.length - 1);
        }
    }

    public int peek() {
        return arr[0];
    }

    private void sizeUp() {
        int[] newArray = new int[2 * capacity];
        System.arraycopy(arr, 0, newArray, 0, capacity);
        capacity *= 2;
        arr = newArray;
    }

    private boolean isLeftOne() {
        return size == capacity - 1;
    }

    private void checkSize() {
        if (isLeftOne()) {
            sizeUp();
        }
    }

    public int getSize() {
        return size;
    }
}

3-2-2. 큐 테스트(배열)

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

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

class ArrayQueueTest {
    ArrayQueue queue;

    @BeforeEach
    void init() {
        queue = new ArrayQueue();
        queue.offer(1);
        queue.offer(3);
        queue.offer(2);
        queue.offer(9);
        queue.offer(7);
    }

    @Test
    void offer() {
        assertEquals(5, queue.getSize());
        assertEquals(1, queue.peek());

        queue.offer(10);

        assertEquals(6, queue.getSize());
        assertEquals(1, queue.peek());
    }

    @Test
    void poll() {
        assertEquals(5, queue.getSize());
        assertEquals(1, queue.peek());

        int poll = queue.poll();

        assertEquals(4, queue.getSize());
        assertEquals(1, poll);
        assertEquals(3, queue.peek());
    }

}

3-3-1. 큐 구현(ListNode)

import issue4.chapter2.ListNode;

public class ListNodeQueue {

    ListNode head;

    public ListNodeQueue() {
        head = new ListNode();
    }

    public void offer(int data) {
        head.add(head, new ListNode(data), head.size());
    }

    public int poll() {
        return head.remove(head, 0).getNumber();
    }

    public int peek() {
        return head.getPositionNumber(head, 0);
    }

    public int getSize() {
        return head.size();
    }

}

3-3-2. 큐 테스트(ListNode)

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

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

class ListNodeQueueTest {

    ListNodeQueue queue;

    @BeforeEach
    void init() {
        queue = new ListNodeQueue();
        queue.offer(1);
        queue.offer(3);
        queue.offer(2);
        queue.offer(9);
        queue.offer(7);
    }

    @Test
    void offer() {
        assertEquals(5, queue.getSize());
        assertEquals(1, queue.peek());

        queue.offer(10);

        assertEquals(6, queue.getSize());
        assertEquals(1, queue.peek());
    }

    @Test
    void poll() {
        assertEquals(5, queue.getSize());
        assertEquals(1, queue.peek());

        int poll = queue.poll();

        assertEquals(4, queue.getSize());
        assertEquals(1, poll);
        assertEquals(3, queue.peek());
    }

}

저작자표시 비영리 변경금지

'Java > STUDY HALLE' 카테고리의 다른 글

[Java] 상속 (0)	2020.12.22
[Java] 클래스 (0)	2020.12.16
[Java] GitHub Library 사용법 (0)	2020.12.06
[Java] JUnit5 (0)	2020.12.05
[Java] 제어문 (0)	2020.12.05

현재글[Java] 선형 자료구조

MUTO 와 함께 개발을

무식하게 공부하자. 토 나올 때 까지.

java8, 더블 디스패치, study halle, 자바, 실패록, Java, junit5, spring, 오브젝트, 조영호, java error, 연결리스트, 선형자료구조, nutee, comparator, KAFKA, whiteship, jvm, 객체지향, Java Exception,

Today :
Yesterday :

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

MUTO 와 함께 개발을

[Java] 선형 자료구조

0.선형 자료구조

위의 그림과 같이 하나의 자료 뒤에 하나의 자료가 1:1관계로 존재하는 것을 선형 자료구조라고 한다.

1.연결리스트

1-1.연결리스트는 무엇일까?

위의 그림과 같이 연결리스트는 하나의 노드가 다음 노드의 주소를 저장하는 방식으로 값을 저장하는 선형 자료구조이다.

1-2. 연결리스트 구현

3.연결리스트 테스트

2.Stack

2-1. 스택은 무엇일까?

위의 그림과 같이 스택은 한 방향에서만 삽입과 삭제가 이루어지는 선입후출 형태의 선형 자료구조이다.

2-2-1. 스택 구현(배열)

2-2-2. 스택 테스트(배열)

2-3-1. 스택 구현(ListNode)

2-3-2. 스택 테스트(ListNode)

3.Queue

3-1. 큐는 무엇일까?

위의 그림과 같이 한쪽에서는 삽입만 이루어지고 반대방향에서는 삭제만 이루어지는 형태의 자료구조를 큐라고 한다.

3-2-1. 큐 구현(배열)

3-2-2. 큐 테스트(배열)

3-3-1. 큐 구현(ListNode)

3-3-2. 큐 테스트(ListNode)

'Java > STUDY HALLE' 카테고리의 다른 글

'Java/STUDY HALLE'의 다른글

티스토리툴바

[Java] 선형 자료구조

0.선형 자료구조

위의 그림과 같이 하나의 자료 뒤에 하나의 자료가 1:1관계로 존재하는 것을 선형 자료구조라고 한다.

1.연결리스트

1-1.연결리스트는 무엇일까?

위의 그림과 같이 연결리스트는 하나의 노드가 다음 노드의 주소를 저장하는 방식으로 값을 저장하는 선형 자료구조이다.

1-2. 연결리스트 구현

3.연결리스트 테스트

2.Stack

2-1. 스택은 무엇일까?

위의 그림과 같이 스택은 한 방향에서만 삽입과 삭제가 이루어지는 선입후출 형태의 선형 자료구조이다.

2-2-1. 스택 구현(배열)

2-2-2. 스택 테스트(배열)

2-3-1. 스택 구현(ListNode)

2-3-2. 스택 테스트(ListNode)

3.Queue

3-1. 큐는 무엇일까?

위의 그림과 같이 한쪽에서는 삽입만 이루어지고 반대방향에서는 삭제만 이루어지는 형태의 자료구조를 큐라고 한다.

3-2-1. 큐 구현(배열)

3-2-2. 큐 테스트(배열)

3-3-1. 큐 구현(ListNode)

3-3-2. 큐 테스트(ListNode)

'Java > STUDY HALLE' 카테고리의 다른 글

'Java/STUDY HALLE'의 다른글

관련글

티스토리툴바