자바강의 - [6주차] 자바와 자료구조 (1)

자바강의 - [6주차] 자바와 자료구조 (1)

---

Array(배열)

Array의 특징

• 동일한 데이터 타입을 순서에 따라 관리하는 자료구조
• 정해진 크기가 있음
• 요소의 추가와 제거시 다른 요소들의 이동이 필요
• 배열의 i번째 요소를 찾는 인덱스 연산이 빠름
• jdk 클래스 : ArrayList, Vector

Array 구현하기

public class MyArray {

    int[] intArr; // int array
    int count;  // 개수

    public int ARRAY_SISE;
    public static final int ERROR_NUM = -999999999;

    public MyArray() {
        count = 0;
        ARRAY_SISE = 10;
        intArr = new int[ARRAY_SISE];
    }

    public MyArray(int size) {
        count = 0;
        ARRAY_SISE = size;
        intArr = new int[size];
    }

    public void addElement(int num) {
        if (count >= ARRAY_SISE) {
            throw new Exception("array size보다 큼");
        }
        intArr[count++] = num;
    }

    public void insertElement(int position, int num) {
        if (count >= ARRAY_SISE) {
            throw new Exception("array size보다 큼");
        }

        if (position < 0 || position > count) {
            throw new Exception("position의 값이 잘못되었음");
        }

        for (int i = count - 1; i >= position; i--) {
            intArr[++i] = intArr[i];
        }

        intArr[position] = num;
        count++;
    }

    public int removeElement(int position) {
        int ret = ERROR_NUM;

        if (isEmpty()) {
            throw new Exception("Array가 비어있음");
        }

        if (position < 0 || position >= count) {
            throw new Exception("position의 값이 잘못되었음");
        }

        ret = intArr[position];

        for (int i = position; i < count - 1; i++) {
            intArr[i] = intArr[++i];
        }
        count--;
        return ret;
    }

    public int getSize() {
        return count;
    }

    public boolean isEmpty() {
        if (count == 0) {
            return true;
        } else {
            return false;
        }
    }

    public int getElement(int position) {
        if (position < 0 || position > --count) {
            throw new Exception("검색 위치 오류");
        }
        return intArr[position];
    }
}

LinkedList(연결리스트)

• 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간이 빠름
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가될 때 노드 만큼의 메모리를 할당받고 이전 노드의 링크로 연결
• 연결 리스트의 i 번째 요소를 찾는데 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList

LinkedList 구현하기

class MyListNode {

    private String data;    // 자료
    public MyListNode next; // 다음 노드를 가리키는 링크

    public MyListNode() {
        data = null;
        next = null;
    }

    public MyListNode(String data) {
        this.data = data;
        this.next = null;
    }

    public MyListNode(String data, MyListNode link) {
        this.data = data;
        this.link = link;
    }

    public String getData() {
        return data;
    }

}

public class MyLinkedList {
    private MyListNode head;
    int count;

    public MyLinkedList() {
        head = null;
        count = 0;
    }

    public MyListNode addElement(String data) {
        MyListNode newNode;
        if (head == null) {
            newNode = new MyListNode(data);
            head = newNode;
        } else {
            newNode = new MyListNode(data);
            MyListNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
        count++;
        return newNode;
    }

    public MyListNode insertElement(int position, String data) {
        MyListNode tempNode = head;
        MyListNode newNode = new MyListNode(data);

        if (position < 0 || position > count) {
            throw new Exception("위치 오류");
        }

        if (position == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            MyListNode preNode = null;
            for (int i = 0; i < position; i++) {
                preNode = tempNode;
                tempNode = tempNode.next;
            }
            newNode.next = preNode.next;
            preNode.next = newNode;
        }
        count++;
        return newNode;
    }

    public MyListNode removeElement(int position) {
        MyListNode tempNode = head;

        if (position >= count) {
            throw new Exception("삭제할 위치 오류");
        }

        if (position == 0) {
            head = tempNode.next;
        } else {
            MyListNode preNode = null;
            for (int i = 0; i < position; i++) {
                preNode = tempNode;
                tempNode = tempNode.next;
            }
            preNode.next = tempNode.next;
        }
        count--;

        return tempNode;
    }

    public String getElement(int position) {
        MyListNode tempNode = head;

        if (position >= count) {
            throw new Exception("검색 위치 오류");
        }

        if (position == 0) {
            return head.getData();
        }

        for (i = 0; i < position; i++) {
            tempNode = tempNode.next;
        }
        return tempNode.getData();
    }

    public MyListNode getNode(int position) {
        MyListNode tempNode = head;

        if (position >= count) {
            throw new Exception("검색 위치 오류");
        }

        if (position == 0) {
            return head;
        }

        for (int i = 0; i < position; i++) {
            tempNode = tempNode.next;
        }

        return tempNode;
    }

    public void removeAll() {
        head = null;
        count = 0;
    }

    public int getSize() {
        return count;
    }

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

}

Stack(스택)

• 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 확인 할 수 있음
• Last In First Out(LIFO) 구조
• 함수의 메모리는 호출 순서에 따른 stack 구조
• jdk 클래스 : Stack

Stack 구현하기

public class MyStack {

    private int top;
    private MyArray arrayStack;

    public MyStack() {
        top = 0;
        arrayStack = new MyArray();
    }

    public MyStack(int size) {
        arrayStack = new MyArray(size);
    }

    public void push(int data) {
        if (isFull()) {
            throw new Exception("스택이 다 차 있음");
        }

        arrayStack.addElement(data);
        top++;
    }

    public int pop() {
        if (top == 0) {
            throw new Exception("스택이 비어있음");
        }
        return arrayStack.removeElement(--top);
    }

    public int peek() {
        if (top == 0) {
            throw new Exception("스택이 비어있음");
        }
        return arrayStack.getElement(top-1);
    }

    public int getSize() {
        return top;
    }

    public boolean isFull() {
        if (top == arrayStack.ARRAY_SIZE) {
            return true;
        }
        return false;
    }

    public boolean isEmpty() {
        if (top == 0) {
            return true;
        }

        return false;
    }

}

Queue

• 맨 앞(front)에 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가
• First In First Out (선입선출) 구조
• 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용되는 구조
• jdk 클래스 : ArrayList

Queue 구현하기

interface IQueue {
    public void enQueue(String data);
    public String deQueue();
}

public class MyQueue extends MyLinkedList implements IQueue {

    private MyListNode front;
    private MyListNode rear;

    public MyQueue() {
        front = null;
        rear = null;
    }

    public void enQueue(String data) {
        MyListNode newNode;

        if (isEmpty()) {
            newNode = addElement(data);
            front = newNode;
            rear = newNode;
        } else {
            newNode = addElement(data);
            rear = newNode;
        }
    }

    public String deQueue() {
        if (isEmpty()) {
            throw new Exception("큐가 비어있음");
        }
        String data = front.getData();
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

}

Stack(스택)과 Queue(큐) 비교

• 스택은 LIFO(Last In First Out)구조로 되어 있고, 큐는 FIFO(First In First Out) 구조로 되어 있음
• 스택에 0, 1, 2 순서로 데이터를 넣었다면 꺼낼때는 2, 1, 0의 순서로 꺼냄
• 큐에 0, 1, 2의 순서로 데이터를 넣었다면 꺼낼 때 역시 0, 1, 2의 순서로 꺼냄
• 스택은 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하지만, 큐는 데이터의 추가/삭제가 쉬운 Linked List로 구현하는 것이 적합함

참고자료

---

• https://fastcampus.co.kr/b2b_kdigitalcredit_java
• https://codechobo.tistory.com/22

Java & SpringBoot로 시작하는 웹 프로그래밍 강의 : #패스트캠퍼스 #내일배움카드 #K디지털크레딧 #바이트디그리 #자바인강