자료구조 정리

1. 스택

• 스택은 후입선출(last in first out)의 개념으로 만들어진 자료구조이다.

생성자

private int size; // 요소 개수
    private int[] stack;

    public Stack(int capacity) {
        this.size = 0;
        this.stack = new int[capacity];
    }

• size : stack안에 담긴 요소의 갯수
• stack을 생성할 때의 매개변수로 스택의 사이즈를 결정한다.

 

public void resize() {

        if (size == stack.length) {

            int newSize = 2 * stack.length;

            stack = Arrays.copyOf(stack, newSize);

        }
    }

• resize() : 기본적으로 stack은 정해진 최대 사이즈가 존재하지 않기에, 처음 생성할 때의 용량보다 더 많은 요소를 넣기 위해서는 배열을 새로 만들어 복사해야 한다.
• 사이즈를 2배로 만들고, 기존 stack배열을 copy해 새로운 용량의 배열에 넣는다.

 

public void push(int data) {

        if (size == stack.length) {
            resize();
        }

        stack[size] = data;
        size++;

    }

• push() : stack에 값을 넣는 메소드로 만약 스택에 들어있는 요소의 갯수(size) 가 stack의 용량과 동일하면, 사이즈를 2배 만들어준다.
• stack에 값을 넣을 때, index를 size로 지정해 0번 index부터 값을 쌓아준다.

 

public int pop() {

        if (size == 0) {
            throw new RuntimeException("꺼낼 요소가 존재하지 않습니다.");
        }

        int pop = stack[size - 1];
        stack[size - 1] = 0;
        return pop;
    }

• stack에 존재하는 요소의 갯수가 0이면 예외를 발생시킨다.
• stack의 가장 위에 있는 요소를 꺼낼 때, size - 1인 인덱스의 값을 꺼내는데, 이는 push()에서 값을 넣은 후 size++ 하기 때문이다.
• 값을 꺼낸 후 0으로 초기화한다.

 

public int peek() {

        if (size == 0) {
            throw new RuntimeException("stack에 요소가 존재하지 않습니다.");
        }

        return stack[size - 1];

    }

• peek() : stack의 가장 윗 요소가 무엇인지 리턴하는 함수

 

2. 큐

• 큐는 선입선출(first in first out)의 개념으로 만들어진 자료구조이다.

생성자

    private int[] queue;
    private int front;
    private int rear;
    private int max;

    public Queue(int size) {

        this.queue = new int[size + 1];
        this.front = 0;
        this.rear = 0;
        this.max = size + 1;

    }

• front : 머리 쪽에 위치하는 인덱스로 pop할 때 사용한다.
• rear : 꼬리 쪽에 위치하는 인덱스로 push할 때 사용한다.
• 생성자에서 queue배열 초기화 시 크기를 size + 1로 지정했는데, 이는 push() 함수를 이해하면 알 수 있다.

 

public void push(int data) {

        if (isFull()) {
            throw new RuntimeException("큐가 가득 찼습니다!");
        }

        rear = (rear + 1) % max;
        queue[rear] = data;
    }

• queue에 값을 넣어줄 때, (rear + 1) % max의 결과값에 넣어준다.
  rear에 바로 값을 넣어주면 어떻게 될까?
• index rear에 값을 넣어주는 경우 : 값이 계속 들어가면 결국, queue의 최대 용량에 들어가게 되는데, 이후 값을 다시 넣으려 하면 RuntimeException("큐가 가득 찼습니다!") 이 발생한다.
  queue의 최대 크기를 정해두고, queue를 원형 큐로 구현해 예외가 발생하는 것을 막는다.
• Queue의 생성자에서 size + 1을 queue의 size로 잡았는데, size로 잡으면, Queue가 요소가 몇개 존재하는지 알 수 없다.
  (Queue에 요소가 가득 찼을 경우와 비어있을 경우를 구분할 수 없다.)

 

public int poll() {

        if (isEmpty()) {
            throw new RuntimeException("큐가 비어있습니다!");
        }

        front = (front + 1) % max;
        return queue[front];
    }

• push()로직과 동일한 로직을 사용하지만, poll은 front를 사용해 값을 뺴낸다.
• 기존 값을 0으로 초기화해줄 필요는 없다.
  (front가 이동하면서, Queue의 시작을 front부터로 판단하기 때문에)

 

public int size() {

        if (front <= rear) {
            return rear - front;
        }

        return max - front + rear;
    }

• size() : queue에 포함된 요소의 갯수를 리턴한다.

 

public void clear() {
        front = 0;
        rear = 0;
    }

• clear() : queue를 초기화 한다.

 

public boolean isEmpty() {

        return front == rear;
    }

• isEmpty() : queue가 비어있는지 확인하는 메소드

 

private boolean isFull() {

        return (rear + 1) % max == front;
    }

• isFull() : queue가 가득 찼는지 확인하는 메소드로, 원형 큐와 queue의 크기가 size + 1이기에 (rear + 1) % max == front를 사용해 판단한다.

 

3. 그래프

• 노드와 해당 노드를 연결하는 간선을 하나로 모아 놓은 자료구조이다.
• 그래프를 구현하는 방식에는 2차원배열로 구현하는 인접행렬 방식과 리스트로 구현하는 인접리스트 방식이 있다.

3-1. 인접행렬 방식

private int[][] graph;

    public Graph1(int size) {
        this.graph = new int[size + 1][size + 1];
    }

• 인접행렬은 2차원 행렬로 그래프를 만드는 방식이다.
  예를들어 (1,2)의 값이 1이면 1번 노드에서 2번 노드로 갈 수 있는 간선이 존재한다는 의미이다.

 

public void addDirectEdge(int x, int y) { // 단방향 연결
        graph[x][y] = 1;
    }

• addDirectEdge() : 노드 x와 노드 y를 단방향 연결 해준다.
  x -> y (노드 x에서 노드 y로 이동할 수 있다.)

 

public void addCompleteEdge(int x, int y) { // 양방향 연결
        graph[x][y] = 1;
        graph[y][x] = 1;

    }

• addCompleteEdge() : 노드 x와 노드 y를 양뱡향 연결 해준다.
  x <-> y (노드 x에서 y로, y에서 x로 이동할 수 있다.)

 

public void deleteDirectedEdge(int x, int y) {
        graph[x][y] = 0;
    }

• deleteDirectedEdge() : 단방향 연결을 해제한다.
  노드 x에서 노드 y로 가는 간선을 제거한다.

 

public void deleteCompleteEdge(int x, int y) {
        graph[x][y] = 0;
        graph[y][x] = 0;
    }

• deleteCompleteEdge() : 양방향 연결을 해제한다.
  노드 x에서 노드 y로 y에서 x로 가는 간선을 제거한다.

 

public void print() {
        for (int[] ints : graph) {
            for (int j = 0; j < graph.length; j++) {
                System.out.print(ints[j] + " ");
            }
            System.out.println();
        }
    }

• 인접행렬로 만들어진 그래프를 나타낸다.

 

장점
구현이 간편하며, 노드끼리 연결되어 있는지를 확인하기 위해 graph[i][j]만 확인하면 된다.

단점
메모리가 많이 사용되며, 노드에 비해 간선이 적으면 비효율적인 구조를 가지게 된다.

 

3-2. 인접리스트 방식

• 인접리스트는 리스트안에 리스트로 그래프를 만드는 방식이다.

private ArrayList<ArrayList<Integer>> graph;

    public Graph2() {
        graph = new ArrayList<ArrayList<Integer>>();
    }

• 인접리스트 방식은 리스트 안에 리스트를 넣어 그래프를 구현한다.
  ex) 노드 1 : 2, 3
  1번 노드는 2번과 3번으로 갈 수 있는 간선이 존재한다.
  -> 1번 리스트에 요소 2, 3이 존재한다.

 

public void addDirectedEdge(int x, int y) {
        graph.get(x).add(y);
    }

• addDirectedEdge() : 노드 x는 노드 y로 갈 수 있는 간선을 추가한다.

 

public void addCompleteEdge(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

• addCompleteEdge() : 노드 x에서 노드 y로 y에서 x로 갈 수 있는 간선을 추가한다.

 

public void print() {

        for (int i = 1; i < graph.size(); i++) {
            System.out.print(i + " -> ");

            for (int j = 0; j < graph.get(i).size(); j++) {
                System.out.print(graph.get(i).get(j));
            }

            System.out.println();
        }
    }

• print() : 인접리스트로 구현한 그래프를 출력한다.

ex) 1 -> 2 , 3
    2 -> 4 , 5
    3 -> 1 , 4

 

장점
노드가 어떤 노드들과 연결되어 있는지 알기 쉽다.
간선 갯수만큼만 메모리공간을 할당해, 인접행렬방식보다 적은 메모리공간을 사용한다.

단점
노드간 연결관계를 알고싶을 때, 인접행렬 방식보다 탐색속도가 느리다.

 

4. 트리

• 그래프의 일종으로 정점과 간선을 이용해 데이터를 표현하는 자료구조로, 서로 다른 노드를 연결하는 길이 하나뿐인 그래프를 트리라 한다.
• Tree는 데이터의 저장보다는 저장된 데이터를 효과적으로 탐색하기 위해 사용한다.
• Tree는 사이클이 존재하지 않으며, 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다.

private int cnt; // 총 노드 갯수

    public Tree() {
        cnt = 0;
    }

• Tree의 필드에 cnt를 만들었는데, Tree에 총 몇개의 정점이 존재하는지 알기위해 선언했다.

 

public class Node {

        Object data;
        Node left;
        Node right;

        public Node(Object data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }

        public void addLeft(Node node) {
            this.left = node;
            cnt++;
        }

        public void addRight(Node node) {
            this.right = node;
            cnt++;
        }

        public void deleteLeft() {
            this.left = null;
            cnt--;
        }

        public void deleteRight() {
            this.right = null;
            cnt--;
        }
    }

• 노드를 다른 노드와 연결하기 위해서는 해당 노드가 연결할 노드의 주소를 알아야 하기에 필드에 left노드와 right노드를 추가했다.

• 노드를 원하는 위치에 더하거나 제거하기위해서는 연결할 위치에 노드를 넣거나, null로 만들어 연결을 해제한 후 Tree의 총 노드 갯수를 갱신해주면 된다.

 

public Node addNode(Object data) {
        return new Node(data);
    }

addNode() : 기존 Node의 메소드들로는 Tree를 시작할 수 없기 때문에,
(노드를 아래에 붙이거나, 제거만 할 수 있다.)
부모노드를 addNode()를 통해 새로 생성해준다.

 

public void preOrder(Node node) { // 전위
        if (node == null) {
            return;
        }

        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

• 노드를 전위순회하는 방법으로, 재귀를 이용해 각 노드들을 출력한다.
• 전위 순회의 경우 left - mid - right 순으로 순회하는 방식이다.
  (뿌리(root)를 먼저 방문하는 방식이다.)

 

public void inOrder(Node node) { // 중위
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

• 중위 순회 : mid - left - right 순으로 순회하는 방식이다.
  (왼쪽 하위트리를 방문 후 뿌리(root)를 방문하는 방식이다.)

 

public void postOrder(Node node) { // 후위
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

• 중위 순회 : left - right - mid 순으로 순회하는 방식이다.
  (하위 트리를 모두 방문한 후 뿌리(root)를 방문하는 방식이다.)

 

5. 링크드 리스트

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

Node

    static class Node {

        private int data;
        public Node nextNode;

        public Node(int data) {
            this.data = data;
            this.nextNode = null;
        }

        public int getData() {
            return this.data;
        }
    }

• 링크드리스트는 노드들로 이루어저 있는 자료구조이기에, 노드를 링크드리스트 내에 만들어준다.
• Node는 값과 다음노드에 대한 정보(포인터)로 이루어져있는데, 다음노드와 현재노드를 연결하려면, 현재노드가 다음노드의 주소를 알고 있어야 하기때문이다.

 

    private Node head;
    public LinkedList() {
        head = null;
    }

• 링크드리스트의 필드는 head만 존재하며, head를 통해 다음 노드를 알 수 있다.

 

  public void addNode(Node preNode, int data) {
        Node newNode = new Node(data);

        newNode.nextNode = preNode.nextNode;
        preNode.nextNode = newNode;
    }

• 중간에 노드 삽입

1. 삽입할 노드를 만들어 준다.
2. 삽입할 노드를 뒷 노드와 먼저 연결해준다.
3. 삽입할 노드를 앞 노드와 연결한다.
   (앞 노드와 삽입할 노드를 먼저 연결하면, 삽입할 노드와 뒷 노드를 연결할 수 없다.)

 

    public void addNode(int data) {

        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;

        } else {

            Node tmpNode = head;

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

            tmpNode.nextNode = newNode;
        }
    }

• 마지막노드와 새로운 노드 연결하기

1. 삽입할 새로운 노드를 만들어 준다.
2. 만약 헤드가 없다면 새로운 노드는 head이다.
3. 마지막 노드에 새로운 노드를 연결하기 위해서는 가장 마지막 노드까지 이동해야 한다.
   이동을 위해 임시노드에 head를 할당하고, 임시노드의 다음노드가 없을 때까지 이동한 후 임시노드에 새로운 노드를 연결하면 된다.

 

  public void deleteNode(int data) {

        Node preNode = head;
        Node tmpNode = head.nextNode;

        if (data == preNode.getData()) {
            head = preNode.nextNode;
            preNode.nextNode = null;

        } else {
            while (tmpNode != null) {
                if (data == tmpNode.getData()) {
                    if (tmpNode.nextNode == null) {
                        preNode.nextNode = null;

                    } else {
                        preNode.nextNode = tmpNode.nextNode;
                        tmpNode.nextNode = null;
                    }
                    break;
                } else {
                    preNode = tmpNode;
                    tmpNode = tmpNode.nextNode;
                }
            }
        }
    }

• 원하는 노드 삭제

1. addNode()처럼 임시노드를 만들어 노드를 이동하는데, 우선 삭제할 노드의 값이 head의 값과 같은지 확인한 후 같으면 삭제한다.
   head를 다음 노드로 지정해준 후 기존head와 새로운head의 연결을 끊는다.
2. 삭제할 노드를 찾아 이동하면서 노드의 값이 삭제할 값과 동일하면, 이전 노드와 이후 노드를 연결해주고 삭제할 노드와 이후 노드의 연결을 끊는다.
   (만약 연결을 해제하지 않으면, 이전 노드와 삭제할드가 모두 이후 노드와 연결된 상태로 남는다.)

 

    public void deleteNode() {
        Node preNode;
        Node tmpNode;

        if (head == null) {
            System.out.println("존재하는 노드가 없습니다!");
            return;
        }

        if (head.nextNode == null) {
            head = null;
        } else {

            preNode = head;
            tmpNode = head.nextNode;

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

            preNode.nextNode = null;
        }
    }

• 마지막 노드 삭제

1. 마지막 노드를 삭제하기 위해 마지막 노드이전까지 이동한다.
2. 링크드리스트에 노드가 head만 존재한다면, head를 삭제한다.
3. 마지막 노드 이전 노드와 마지막 노드의 연결을 끊는다.
   (preNode는 마지막 노드 이전 노드가 되는 것이 목표)
   (tmpNode는 마지막 노드가 되는 것이 목표)

 

    public Node searchNode(int data) {
        Node tmpNode = head;

        while (tmpNode != null) {

            if (data == tmpNode.getData()) {
                return tmpNode;

            } else {
                tmpNode = tmpNode.nextNode;
            }
        }

        return tmpNode;
    }

• 원하는 노드 찾기

1. 현재 노드가 원하는 노드인지 확인한 후 아니면, 다음 노드로 이동한다.

 

    public void print() {
        Node tmpNode = head;

        while (tmpNode != null) {
            System.out.print(tmpNode.getData() + " ");
            tmpNode = tmpNode.nextNode;
        }

        System.out.println();
    }

• 링크드 리스트 출력하기

1. 다음 노드로 이동하면서, 현재 노드를 출력한다.