[CS] 자료구조란 무엇인가? (배열, 리스트, 스택, 큐, 트리, 그래프)

자료구조는 데이터를 효율적으로 저장하고 조작하기 위한 방법이나 구조를 의미합니다. 대표적인 자료구조로 배열, 리스트, 스택, 큐, 트리, 그래프 등이 있으며, 각각의 자료구조는 특정한 작업을 수행하는데 적합한 기능과 효율성을 제공합니다. java를 기반으로 알아보도록 하겠습니다.

목차

배열 (Array)

리스트 (Linked List)

스택 (Stack)

큐 (Queue)

트리 (Tree)

그래프 (Graph)

---

배열 (Array)

배열은 동일한 타입의 요소를 연속된 메모리 공간에 저장하는 자료구조입니다. 배열은 크기가 고정되어 있고 인덱스를 사용하여 요소에 접근할 수 있습니다. 배열은 빠른 접근 속도를 제공하며, 요소의 추가 및 삭제가 어렵습니다.

예시

int[] scores = new int[5]; // 크기가 5인 정수형 배열 생성

scores[0] = 90; // 첫 번째 요소에 접근하여 값 할당
scores[1] = 85;
scores[2] = 95;
scores[3] = 80;
scores[4] = 92;

int firstScore = scores[0]; // 첫 번째 요소 값 호출

배열은 주어진 크기에 따라 메모리를 할당하므로 크기 조정이 어렵습니다. 따라서 요소의 추가나 삭제가 빈번하게 발생하는 상황에서는 다른 자료구조를 사용하는 것이 좋습니다.

주요 메서드

length

int[] arr = {1, 2, 3, 4, 5};
int length = arr.length;  // 배열의 길이를 반환
System.out.println(length);  // 출력: 5

toString

int[] arr = {1, 2, 3, 4, 5};
String arrString = Arrays.toString(arr);  // 배열의 내용을 문자열로 변환
System.out.println(arrString);  // 출력: [1, 2, 3, 4, 5]

sort

int[] arr = {5, 2, 8, 1, 4};
Arrays.sort(arr);  // 배열의 요소를 정렬
System.out.println(Arrays.toString(arr));  // 출력: [1, 2, 4, 5, 8]

fill

int[] arr = new int[5];
Arrays.fill(arr, 0);  // 배열의 모든 요소를 0으로 채움
System.out.println(Arrays.toString(arr));  // 출력: [0, 0, 0, 0, 0]

copyOf

int[] src = {1, 2, 3, 4, 5};
int[] copy = Arrays.copyOf(src, 3);  // src 배열의 처음 3개 요소를 복사
System.out.println(Arrays.toString(copy));  // 출력: [1, 2, 3]

---

리스트 (Linked List)

리스트는 동적 크기의 요소들을 저장하는 선형 자료구조입니다. 리스트는 요소의 삽입과 삭제가 용이하며, 인덱스를 사용하여 요소에 접근할 수 있습니다.

예시

List<String> todoList = new ArrayList<>();

todoList.add("운동하기"); // 요소 추가
todoList.add("공부하기");
todoList.add("식사하기");
todoList.add("독서하기");

String firstTask = todoList.get(0); // 첫 번째 요소 값 호출

todoList.remove(2); // 인덱스 2의 요소 삭제

리스트는 동적으로 크기가 조정되기 때문에 요소의 추가와 삭제가 자유롭습니다. 따라서 요소의 변경이 빈번하게 발생하거나 크기가 변경될 수 있는 상황에서 유용합니다.

주요 메서드

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        // add: 리스트의 끝에 요소를 추가
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");
        System.out.println(linkedList);  // 출력: [Apple, Banana, Cherry]

        // remove: 주어진 요소를 리스트에서 삭제
        linkedList.remove("Banana");
        System.out.println(linkedList);  // 출력: [Apple, Cherry]

        // get: 주어진 인덱스에 해당하는 요소를 반환
        String element = linkedList.get(0);
        System.out.println(element);  // 출력: Apple

        // size: 리스트의 크기(요소의 개수)를 반환
        int size = linkedList.size();
        System.out.println(size);  // 출력: 2

        // addFirst: 리스트의 맨 앞에 요소를 추가
        linkedList.addFirst("Strawberry");
        System.out.println(linkedList);  // 출력: [Strawberry, Apple, Cherry]

        // addLast: 리스트의 맨 뒤에 요소를 추가
        linkedList.addLast("Grapes");
        System.out.println(linkedList);  // 출력: [Strawberry, Apple, Cherry, Grapes]

        // removeFirst: 리스트의 맨 앞의 요소를 삭제
        linkedList.removeFirst();
        System.out.println(linkedList);  // 출력: [Apple, Cherry, Grapes]

        // removeLast: 리스트의 맨 뒤의 요소를 삭제
        linkedList.removeLast();
        System.out.println(linkedList);  // 출력: [Apple, Cherry]
    }
}

---

스택 (Stack)

스택은 후입선출(Last In First Out, LIFO)의 원리를 따르는 자료구조입니다. 가장 최근에 추가된 요소가 가장 먼저 제거되는 구조입니다. 스택은 주로 임시 데이터 저장 함수 호출 및 역추적, 웹 브라우저의 뒤로 가기 기능 등에 활용됩니다.

예시

Stack<String> history = new Stack<>();

history.push("www.google.com"); // 요소 추가
history.push("www.openai.com");
history.push("www.github.com");

String currentURL = history.peek(); // 최상단 요소 값 확인

String previousURL = history.pop(); // 최상단 요소 제거

스택은 가장 최근에 추가된 요소에 빠르게 접근할 수 있으며, 이전 단계로 되돌아가는 등의 역추적이 필요한 상황에서 유용합니다.

주요 메서드

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // push: 스택에 요소를 추가
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack);  // 출력: [10, 20, 30]

        // pop: 스택의 맨 위 요소를 삭제하고 반환
        int poppedElement = stack.pop();
        System.out.println(poppedElement);  // 출력: 30
        System.out.println(stack);  // 출력: [10, 20]

        // peek: 스택의 맨 위 요소를 반환 (삭제하지 않음)
        int topElement = stack.peek();
        System.out.println(topElement);  // 출력: 20
        System.out.println(stack);  // 출력: [10, 20]

        // empty: 스택이 비어있는지 확인 (비어있으면 true, 아니면 false 반환)
        boolean isEmpty = stack.empty();
        System.out.println(isEmpty);  // 출력: false

        // search: 스택에서 주어진 요소의 인덱스를 반환 (스택의 맨 위부터 1부터 시작)
        int index = stack.search(10);
        System.out.println(index);  // 출력: 2
    }
}

---

큐 (Queue)

큐는 선입선출(First In First Out, FIFO)의 원리를 따르는 자료구조입니다. 가장 먼저 추가된 요소가 가장 먼저 제거되는 구조입니다. 큐는 작업 처리, 이벤트 처리, 메시지 전달, 주문 처리 등에 사용됩니다.

예시

Queue<String> orders = new LinkedList<>();

orders.offer("아메리카노"); // 요소 추가
orders.offer("카페라떼");
orders.offer("카푸치노");

String nextOrder = orders.peek(); // 다음 주문 확인

String processedOrder = orders.poll(); // 다음 주문 처리

큐는 요소의 추가와 제거가 효율적으로 이루어지므로 작업이 순차적으로 처리되어야 하는 상황에서 유용합니다.

주요 메서드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Queue 생성
        Queue<Integer> queue = new LinkedList<>();

        // 요소 추가 (Enqueue)
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 요소 확인 (Peek)
        int front = queue.peek();
        System.out.println("Front: " + front);

        // 요소 제거 (Dequeue)
        int removed = queue.poll();
        System.out.println("Removed: " + removed);

        // 큐의 크기 확인
        int size = queue.size();
        System.out.println("Size: " + size);

        // 큐 비어있는지 확인
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is Empty: " + isEmpty);
    }
}

---

트리 (Tree)

트리는 계층 구조를 표현하는 비선형 자료구조입니다. 트리는 하나의 루트 노드에서 여러 개의 자식 노드들이 연결되어 있는 구조입니다. 트리는 계층 구조, 정렬, 탐색, 조직도, 등의 작업에 사용됩니다. java의 표준 라이브러리에 포함되어있지 않습니다. 아래와 같이 구현할 수 있습니다.

예시

class Employee {
    private String name;
    private int id;
    private List<Employee> subordinates;

    // 생성자, getter, setter 생략

    public void addSubordinate(Employee employee) {
        subordinates.add(employee);
    }
}

Employee ceo = new Employee("John", 1);
Employee manager1 = new Employee("Alice", 2);
Employee manager2 = new Employee("Bob", 3);

ceo.addSubordinate(manager1);
ceo.addSubordinate(manager2);

트리는 계층 구조를 표현하고 부모, 자식 관계를 표현하기에 유용합니다.

---

그래프 (Graph)

그래프는 노드와 간선으로 구성된 자료구조입니다. 노드 간의 관계를 나타내기 위해 사용되며, 네트워크, 지도, 소셜 그래프 등 다양한 상황에 활용됩니다. java의 표준 라이브러리에 포함되어있지 않습니다. 아래와 같이 구현할 수 있습니다.

예시

class Person {
    private String name;
    private List<Person> friends;

    // 생성자, getter, setter 생략

    public void addFriend(Person person) {
        friends.add(person);
    }
}

Person person1 = new Person("John");
Person person2 = new Person("Alice");
Person person3 = new Person("Bob");

person1.addFriend(person2);
person2.addFriend(person3);

그래프는 노드 간의 관계를 표현하고 탐색하는 데 사용됩니다.