자료구조 정리 및 활용 예시

내내 개발만하다가 요즘들어 알고리즘 공부를 함으로써 자료구조를 다시 한번 정리하려한다. 알고리즘 문제를 해결할때 도움이 되고자 간단하고 빠르게 자료구조에 대해 코드 위주로 정리해보았다 !!

1. Array (배열)

• 정의: 동일한 데이터 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조다. 각 요소는 인덱스를 통해 접근할 수 있다.
• 사용 시기: 데이터의 크기가 고정되어 있고, 인덱스를 통해 빠르게 접근해야 할 때 사용된다 !

// 배열 선언 및 초기화
int[] arr = {1, 2, 3, 4, 5};

// 배열 요소 접근 및 출력
System.out.println(arr[2]);  // 출력: 3

// 배열 요소 삽입 (새로운 배열 필요)
int[] newArr = new int[arr.length + 1];
System.arraycopy(arr, 0, newArr, 0, 2);
newArr[2] = 6;  // 6을 삽입
System.arraycopy(arr, 2, newArr, 3, arr.length - 2);
arr = newArr;
System.out.println(java.util.Arrays.toString(arr));  // 출력: [1, 2, 6, 3, 4, 5]

// 배열 요소 삭제 (새로운 배열 필요)
int[] newArr2 = new int[arr.length - 1];
System.arraycopy(arr, 0, newArr2, 0, 2);
System.arraycopy(arr, 3, newArr2, 2, arr.length - 3);
arr = newArr2;
System.out.println(java.util.Arrays.toString(arr));  // 출력: [1, 2, 3, 4, 5]

---

2. Linked List (연결 리스트)

• 정의: 각 요소(Node)가 데이터와 다음 요소를 가리키는 포인터를 가지고 있는 자료구조이다. 요소들이 물리적으로 연속되지 않더라도 논리적으로 연결된다.
• 사용 시기: 데이터의 크기가 동적이거나, 삽입 및 삭제가 빈번히 발생할 때 사용된다 !

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // 노드 추가
    void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }

    // 리스트 출력
    void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// 사용 예시
LinkedList list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.printList();  // 출력: 1 2 3

---

3. Stack (스택)

• 정의: 후입선출(LIFO) 방식으로 동작하는 자료구조다. 데이터는 스택의 꼭대기에서 삽입되고 제거된다 !
• 사용 시기: 데이터의 삽입과 삭제가 한쪽 끝에서만 발생할 때 사용된다.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

// 데이터 삽입
stack.push(1);
stack.push(2);
stack.push(3);

// 데이터 제거 및 출력
System.out.println(stack.pop());  // 출력: 3

// 데이터 접근만 (제거하지 않음)
System.out.println(stack.peek());  // 출력: 2

// 스택이 비어있는지 확인
System.out.println(stack.isEmpty());  // 출력: false

---

4. Queue (큐)

• 정의: 선입선출(FIFO) 방식으로 동작하는 자료구조다. 데이터는 큐의 한쪽 끝에서 삽입되고 반대쪽 끝에서 제거된다 !
• 사용 시기: 데이터의 삽입과 삭제가 양쪽 끝에서 발생할 때 사용된다.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();

// 데이터 삽입
queue.add(1);
queue.add(2);
queue.add(3);

// 데이터 제거 및 출력
System.out.println(queue.poll());  // 출력: 1

// 데이터 접근만 (제거하지 않음)
System.out.println(queue.peek());  // 출력: 2

// 큐가 비어있는지 확인
System.out.println(queue.isEmpty());  // 출력: false

---

5. Hash Table (해시 테이블)

• 정의: 키-값 쌍을 저장하는 자료구조다. 해시 함수를 사용해 키를 인덱스로 변환하여 값을 저장한다 !
• 사용 시기: 키를 사용해 데이터를 빠르게 검색, 삽입, 삭제해야 할 때 사용된다.

import java.util.HashMap;

HashMap<String, Integer> hashMap = new HashMap<>();

// 데이터 삽입
hashMap.put("apple", 1);
hashMap.put("banana", 2);
hashMap.put("cherry", 3);

// 데이터 접근
System.out.println(hashMap.get("banana"));  // 출력: 2

// 데이터 삭제
hashMap.remove("apple");
System.out.println(hashMap.containsKey("apple"));  // 출력: false

---

6. Tree (트리)

• 정의: 계층적인 구조를 가지며, 루트 노드와 하위의 자식 노드들로 구성된 자료구조다.
• 사용 시기: 계층적 데이터 표현이나, 이진 탐색을 위한 데이터 구조가 필요할 때 사용된다 !

class TreeNode {
    int data;
    TreeNode left, right;

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

class BinaryTree {
    TreeNode root;

    // 노드 삽입
    TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            return new TreeNode(data);
        }

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

        return node;
    }

    // 중위 순회 (In-order Traversal)
    void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.data + " ");
            inOrder(node.right);
        }
    }
}

// 사용 예시
BinaryTree tree = new BinaryTree();
tree.root = tree.insert(tree.root, 5);
tree.insert(tree.root, 3);
tree.insert(tree.root, 7);
tree.inOrder(tree.root);  // 출력: 3 5 7

---

7. Graph (그래프)

• 정의: 노드(정점)와 그 노드를 연결하는 간선으로 이루어진 자료구조다. 방향성에 따라 방향 그래프와 무방향 그래프로 나뉜다 !
• 사용 시기: 복잡한 연결 관계를 표현하거나 탐색이 필요한 경우 사용된다.

import java.util.LinkedList;

class Graph {
    private int numVertices;
    private LinkedList<Integer>[] adjList;

    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 간선 추가
    void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

    // 그래프 출력
    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer node : adjList[i]) {
                System.out.print(" -> " + node);
            }
            System.out.println();
        }
    }
}

// 사용 예시
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.printGraph();
// 출력:
// Vertex 0: -> 1 -> 4
// Vertex 1: -> 2 -> 3
// Vertex 2:
// Vertex 3:
// Vertex 4:

---

8. Priority Queue (우선순위 큐)

• 정의: 각 요소가 우선순위를 가지고 있는 자료구조로, 우선순위가 높은 요소가 먼저 제거된다 !
• 사용 시기: 우선순위가 있는 데이터를 관리할 때 사용된다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

// 데이터 삽입
pq.add(3);
pq.add(1);
pq.add(5);

// 데이터 접근 및 제거 (기본적으로 오름차순)
System.out.println(pq.poll());  // 출력: 1
System.out.println(pq.poll());  // 출력: 3
System.out.println(pq.poll());  // 출력: 5

// 우선순위가 높은 값 (내림차순 정렬)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(java.util.Collections.reverseOrder());
maxHeap.add(3);
maxHeap.add(1);
maxHeap.add(5);

System.out.println(maxHeap.poll());  // 출력: 5
System.out.println(maxHeap.poll());  // 출력: 3
System.out.println(maxHeap.poll());  // 출력: 1