자료구조 구현

오늘은 다양한 자료구조를 직접 구현해보고 그 동작 원리를 이해해보자. 자료구조는 데이터를 효율적으로 저장하고 관리하기 위해 사용되며, 각 자료구조는 특정 상황에서 더 유용하게 사용될 수 있다.

LinkedList

LinkedList는 노드(Node)들이 연결된 형태로 데이터를 저장하는 자료구조다. 각 노드는 데이터와 다음 노드를 가리키는 참조를 가지고 있다.

class Node {
    int data;
    Node next;

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

class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// 예제
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.printList(); // 출력: 1 2 3

Queue

Queue는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하는 자료구조다. 주로 줄 서기와 같은 상황에서 사용된다.

class Queue {
    private LinkedList<Integer> list = new LinkedList<>();

    public void enqueue(int data) {
        list.add(data);
    }

    public int dequeue() {
        if (list.isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return list.removeFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

// 예제
Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 출력: 1
System.out.println(queue.dequeue()); // 출력: 2

Stack

Stack은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 저장하는 자료구조다. 주로 재귀적인 문제를 해결할 때 사용된다.

class Stack {
    private LinkedList<Integer> list = new LinkedList<>();

    public void push(int data) {
        list.addFirst(data);
    }

    public int pop() {
        if (list.isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return list.removeFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

// 예제
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3
System.out.println(stack.pop()); // 출력: 2

Tree

Tree는 계층적 구조를 가지는 자료구조다. 각 노드는 자식 노드를 가질 수 있으며, 루트 노드부터 시작해 자식 노드로 확장된다. 여기서는 이진 트리(Binary Tree)를 예제로 들어보자.

class TreeNode {
    int data;
    TreeNode left, right;

    public TreeNode(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

class BinaryTree {
    private TreeNode root;

    public BinaryTree() {
        root = null;
    }

    public void add(int data) {
        root = addRecursive(root, data);
    }

    private TreeNode addRecursive(TreeNode node, int data) {
        if (node == null) {
            return new TreeNode(data);
        }

        if (data < node.data) {
            node.left = addRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = addRecursive(node.right, data);
        }

        return node;
    }

    public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }

    public TreeNode getRoot() {
        return root;
    }
}

// 예제
BinaryTree binaryTree = new BinaryTree();
binaryTree.add(6);
binaryTree.add(4);
binaryTree.add(8);
binaryTree.add(3);
binaryTree.add(5);
binaryTree.add(7);
binaryTree.add(9);

binaryTree.inOrderTraversal(binaryTree.getRoot()); // 출력: 3 4 5 6 7 8 9

So...

오늘은 다양한 자료구조인 LinkedList, Queue, Stack, Tree를 구현해보았다. 각 자료구조는 특정 상황에서 유용하게 사용될 수 있으며, 이를 잘 이해하고 활용하는 것이 중요하다. 이러한 자료구조들은 알고리즘의 효율성을 높이는 데 중요한 역할을 한다.