[Java] 자료구조 - 배열, 연결리스트, 스택, 큐, 힙, 트리, 그래프, 해시

1. 자료구조

1) 자료구조의 정의

• 자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하여 필요한 작업을 빠르게 수행할 수 있게 하는 구조
• 데이터의 조작, 접근 방식을 설계하는 중요한 개념으로 데이터의 성격과 사용 목적에 따라 다양한 형태로 구현
  
  • '효율적이다' : 데이터를 처리하는 데 필요한 시간과 공간을 최소화하는 것

자료의 형태에 따라 다음과 같이 분류할 수 있다.

• 단순 구조 : 기본 자료형 정수, 실수, 문자, 문자열 등
• 선형 구조 : 자료들 간의 앞뒤 관계가 1:1의 선형 관계를 가지는 자료형 리스트, 연결리스트, 스택, 큐, 데크 등
• 비선형 구조 : 자료들 간의 앞뒤 관계가 1:다, 다:다의 관계를 가지는 자료형 트리, 그래프 등
• 파일 구조 : 레코드의 집합인 파일에 대한 구조 순차파일, 색인파일, 직접파일 등

 

2) 자료구조의 종류

(1) 배열 (Array)

• 고정된 크기의 연속적인 메모리 공간에 같은 유형의 데이터를 순차적으로 저장하는 자료구조
• 각 요소는 인덱스를 통해 접근할 수 있으며, 데이터에 접근하는 속도가 빠름
• 크기가 고정되어 있어 크기를 동적으로 조정하기 어려움
  • 물리적 연속성, 정적 구조, 외부단편화O, 검색 연산▲, 기록 밀도▼, 수정 연산▲, 삽입/삭제 연산▼

public class ArrayExample {
    public static void main(String[] args) {
        int[] array = new int[5]; // 배열 크기 5
        array[0] = 10;
        array[1] = 20;
        array[2] = 30;
        
        // 배열 요소 출력
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

(2) 연결리스트 (Linked List)

• 요소들이 각각 노드(node)로 구성되며, 각 노드는 다음 노드를 가리키는 포인터를 통해 서로 연결된 자료구조
• 삽입과 삭제가 용이하며, 배열과 달리 각 요소가 메모리 상의 임의의 위치에 저장되고, 크기를 유동적으로 조절할 수 있음
• 특정 요소에 접근하기 위해 순차적으로 탐색해야 하므로 검색 속도가 저하될 수 있음
  • 논리적 연속성, 동적 구조, 외부단편화X, 검색 연산▼, 기록 밀도▼, 수정 연산▲, 삽입/삭제 연산▼

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

class LinkedList {
    Node head;
    
    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();
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        list.printList();
    }
}

(3) 스택 (Stack)

• 후입선출(LIFO; Last In, First Out) 방식의 자료구조
• 가장 마지막에 추가된 요소가 가장 먼저 제거됨, 요소를 추가(push)하고 제거(pop)하는 연산만 가능
• 함수 호출의 관리, 실행 취소(undo), 괄호 검사, 후위 표기법 등에 이용

import java.util.EmptyStackException;

class Stack {
    private int[] stack;
    private int top;
    
    public Stack(int size) {
        stack = new int[size];
        top = -1;
    }
    
    public void push(int value) {
        if (top == stack.length - 1) {
            System.out.println("Stack is full");
            return;
        }
        stack[++top] = value;
    }
    
    public int pop() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return stack[top--];
    }
    
    public int peek() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return stack[top];
    }
}

public class StackExample {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(10);
        stack.push(20);
        System.out.println(stack.pop()); // 20
        System.out.println(stack.peek()); // 10
    }
}

(4) 큐 (Queue)

• 선입선출(FIFO; First In First Out) 방식의 자료구조
• 가장 먼저 들어온 요소가 가장 먼저 제거됨. 데이터 넣기(enqueue), 꺼내기(dequeue)
• 너비 우선 탐색, 대기열 관리, 작업(CPU) 스케줄링, 데이터 스트리밍 등에 이용

class Queue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    
    public Queue(int size) {
        queue = new int[size];
        front = -1;
        rear = -1;
        this.size = size;
    }
    
    public void enqueue(int value) {
        if (rear == size - 1) {
            System.out.println("Queue is full");
            return;
        }
        queue[++rear] = value;
        if (front == -1) front = 0;
    }
    
    public int dequeue() {
        if (front == -1 || front > rear) {
            System.out.println("Queue is empty");
            return -1;
        }
        return queue[front++];
    }
}

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new Queue(5);
        queue.enqueue(10);
        queue.enqueue(20);
        System.out.println(queue.dequeue()); // 10
        System.out.println(queue.dequeue()); // 20
    }
}

(5) 힙 (Queue)

• 완전 이진 트리 형태의 자료 구조로, 우선순위 큐(Priority Queue)를 구현하기 위해 사용됨

// 최소 힙 예제

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(20);
        minHeap.add(10);
        minHeap.add(30);
        
        System.out.println(minHeap.poll()); // 10
        System.out.println(minHeap.poll()); // 20
    }
}

(6) 그래프 (Graph)

• 객체(노드 또는 정점)와 객체 간의 관계(엣지 또는 간선)를 표현하는 비선형 자료구조
• 순환적인 구조(사이클 허용)를 가질 수 있고, 방향을 가질 수도 있음
• 사회/도로 네트워크, 웹 페이지의 링크 구조, 소셜 미디어, 지도 탐색 등 복잡한 관계를 표현할 때 유용

// 인접 리스트를 이용한 그래프 구현

import java.util.ArrayList;
import java.util.List;

class Graph {
    private List<List<Integer>> adjList;
    
    public Graph(int vertices) {
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }
    
    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src); // 무방향 그래프
    }
    
    public void printGraph() {
        for (int i = 0; i < adjList.size(); i++) {
            System.out.print("Vertex " + i + ":");
            for (int edge : adjList.get(i)) {
                System.out.print(" -> " + edge);
            }
            System.out.println();
        }
    }
}

public class GraphExample {
    public static void main(String[] args) {
        Graph graph = new Graph(3);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        
        graph.printGraph();
    }
}

(7) 트리 (Tree)

• 계층 구조를 표현하는 비선형 자료구조로, 각 노드가 부모-자식 관계로 연결되어 있음
• 루트(root) 노드를 기준으로 각 노드가 자식을 가질 수 있으며, 한 개의 부모 노드를 가짐(루트 노드 제외)
• 데이터의 계층적 구조를 표현하고 검색/삽입/삭제 연산을 효율적으로 수행할 수 있음
• 이진 검색 트리, AVL 트리, B-트리, 레드-블랙 트리 등 다양한 변형이 존재
• 그래프의 특수한 형태로 사이클을 허용하지 않는다.
• 파일 시스템, HTML 문서의 DOM, 데이터베이스 관리 등에 사용

// 이진 트리

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

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

public class TreeExample {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(20);
        tree.root.right = new TreeNode(30);
        
        tree.preorder(tree.root); // 10 20 30
    }
}

(8) 해시 (Hash)

• 키(Key)를 입력 받아 해시 함수를 통해 값을 빠르게 검색할 수 있는 자료구조
• 키를 해시 테이블의 인덱스로 변환하여 데이터를 저장하거나 찾음
• 충돌(collision) 해결 기법 : 해시 함수의 출력이 같아(같은 해시 값) 충돌이 발생하는 경우
  • 개별 체이닝, 개방 주소법, 이차 해시, 해싱 후체이닝 등
• 해시 맵(hash map) 또는 딕셔너리(dictionary)로 구현
  • 해시 맵 : 키-값 쌍으로 데이터를 저장하는 자료구조. 각 키는 해시 함수를 통해 고유의 인덱스로 매핑되어 빠르게 데이터에 접근할 수 있음 (Java의 HashMap)
  • 딕셔너리 : 키-값 쌍으로 이루어져 있고 내부적으로 해시 테이블로 구현됨 (Python의 dict)
• 데이터의 빠른 검색과 삽입에 매우 효율적

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Alice", 30);
        map.put("Bob", 25);
        
        System.out.println(map.get("Alice")); // 30
        System.out.println(map.containsKey("Bob")); // true
        System.out.println(map.remove("Alice")); // 30
    }
}