5.2 선형 자료 구조

선형 자료 구조

선형 자료 구조란 자료를 구성하는 원소를 하나씩 순차적으로 나열시킨 형태이다. 자료들간의 앞, 뒤 관계가 1:1 관계이다.

연결 리스트 (Linked List)

• 데이터 요소를 연결된 노드로 표현하는 방식이며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 링크)로 구성된다.
• 이 포인터를 통해 다음 노드로 이동하면서 데이터에 순차적으로 접근할 수 있다.
• 동적으로 크기가 조절될 수 있으며, 데이터의 삽입과 삭제가 빠르게 이루어진다는 특징이 있다.
• 다만, 임의 접근이 어려워서 특정 위치의 데이터에 접근하려면 처음부터 순차적으로 탐색해야 한다. (따라서 검색 작업에도 긴 시간이 걸린다.)

class Node {
    int data; // 데이터를 저장하는 변수
    Node next; // 다음 노드를 가리키는 링크(포인터)

    public Node(int data) {
        this.data = data;
        this.next = null; // 초기에는 다음 노드를 가리키는 링크가 없으므로 null로 설정
    }
}

class LinkedList {
    Node head; // 첫 번째 노드를 가리키는 헤드(포인터)

    public LinkedList() {
        this.head = null; // 초기에는 헤드가 null인 빈 LinkedList
    }

    // 노드를 LinkedList의 맨 끝에 추가하는 메서드
    public void append(int data) {
        Node newNode = new Node(data); // 새로운 노드 생성

        if (head == null) {
            // LinkedList가 비어있는 경우, 헤드로 설정
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next; // 마지막 노드까지 이동
            }
            current.next = newNode; // 마지막 노드의 다음 링크에 새로운 노드를 연결
        }
    }

    // LinkedList의 모든 요소를 출력하는 메서드
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " "); // 현재 노드의 데이터 출력
            current = current.next; // 다음 노드로 이동
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList(); // LinkedList 인스턴스 생성

        list.append(1); // LinkedList에 1을 추가
        list.append(2); // LinkedList에 2를 추가
        list.append(3); // LinkedList에 3을 추가

        list.display(); // LinkedList의 모든 요소를 출력 (1 2 3)
    }
}

배열

• 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 방법이다.
• 인덱스를 사용해 각 요소에 접근할 수 있다.
• 데이터의 순서를 유지하고, 특정 위치의 요소에 빠르게 접근할 수 있는 장점이 있다.
• 메모리 공간 내부에서 인접해서 저장되기에 캐시 지역성이 좋아 성능 향상에 도움을 줄 수 있다.
• 생성할 때 크기를 정하고 이 크기를 변경할 수 없어 크기 조정 제약이 있다.
• 요소를 삽입하거나 삭제하는 작업에 비용이 크다.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        int[] numbers = new int[5];
        
        //배열에 값 할당
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        //배열의 값 참조
        System.out.println(numbers[2]);
        
        //배열의 길이
        System.out.println(numbers.length); // 5
        
        //배열 반복문 순회
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }
}

스택

• 후입선출 원칙에 따라 데이터를 저장하는 추상 자료형이다.
• 데이터를 저장하는 컨테이너로 구현이 비교적 쉽고 빠르게 데이터를 추가하거나 제거할 수 있다.
• 크기가 제한되어 있어 초과할 경우 오버플로우가 발생한다.
• 중간에 있는 데이터에는 접근하거나 수정하기 어렵다.
• 함수 호출, 재귀 알고리즘, 뒤로 가기 기능 등에 활용된다. (데이터를 일시적으로 저장하고 나중에 역순으로 처리해야 할 때 유용하다.)

<주요 연산>

• push : 스택에 데이터 추가, 스택의 맨 위에 데이터를 삽입한다.
• pop : 스택에서 데이터를 제거, 스택의 맨 위에서 데이터를 삭제하고 반환한다.
• peek or top : 스택의 맨 위에 있는 데이터를 반환만 한다.
• isEmpty : 스택이 비어있는지 확인한다.
• size : 스택에 저장된 데이터의 개수를 반환한다.

<Stack 클래스 사용한 경우>

import java.util.Stack;

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

        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("스택 크기: " + stack.size()); // 출력: 3
        System.out.println("맨 위 데이터: " + stack.peek()); // 출력: 30

        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 30
        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 20
        System.out.println("스택이 비어있는지 확인: " + stack.isEmpty()); // 출력: false
    }
}

<Stack 직접 구현한 경우>

public class Stack {
    private int maxSize; // 스택의 최대 크기
    private int top; // 스택의 맨 위 인덱스
    private int[] stackArray; // 스택을 위한 배열

    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // 스택이 비어있는 상태를 나타내기 위해 -1로 초기화
    }

    public void push(int data) {
        if (top == maxSize - 1) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }
        stackArray[++top] = data; // 스택의 맨 위에 데이터 추가
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }
        return stackArray[top--]; // 스택의 맨 위 데이터 제거 후 반환
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }
        return stackArray[top]; // 스택의 맨 위 데이터 반환
    }

    public boolean isEmpty() {
        return (top == -1); // 스택이 비어있는지 확인
    }

    public int size() {
        return top + 1; // 스택에 저장된 데이터의 개수 반환
    }
}
public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 크기가 5인 스택 생성

        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("스택 크기: " + stack.size()); // 출력: 3
        System.out.println("맨 위 데이터: " + stack.peek()); // 출력: 30

        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 30
        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 20
        System.out.println("스택이 비어있는지 확인: " + stack.isEmpty()); // 출력: false
    }
}

큐

• 선입선출 원칙에 따라 동작하는 자료구조이다.
• 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나는 구조를 가지고 있다.
• 한쪽 끝을 rear, 다른 한쪽 끝을 front라고 한다.
• 데이터는 front에서 삭제되고, rear에서 삽입된다.
• 동적으로 크기 조절이 가능하지만 특정 구현에서는 크기가 제한되어 있을 수 있다.
• 데이터 순서를 보장하고, 대기열 관리, 작업 분배 등 다양한 상황에서 매우 유용하다.
• 중간 항목 접근이 어렵다.
• 특정 항목을 찾기 위해서 큐를 선형적으로 탐색해야 한다.

<기본 연산>

• enqueue : 큐의 rear에 항목을 삽입한다.
• dequeue : 큐의 front에서 항목을 삭제하고 반환한다.
• peek or top : 큐의 front에 있는 데이터를 반환만 한다.
• isEmpty : 큐가 비어있는지 확인한다.
• size : 큐에 저장된 데이터의 개수를 반환한다.

<Linked List를 활용해 Queue 구현>

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

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

        // enqueue: 큐에 항목 삽입
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        // dequeue: 큐에서 항목 삭제 및 반환
        int item = queue.poll();
        System.out.println("Dequeued item: " + item);

        // peek: 큐의 프론트(front) 항목 참조
        int frontItem = queue.peek();
        System.out.println("Front item: " + frontItem);

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

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

import java.util.LinkedList;

public class Queue<T> {
    private LinkedList<T> queue;  // LinkedList를 사용해 큐를 구현

    public Queue() {
        queue = new LinkedList<>();
    }

    public void enqueue(T item) {
        queue.addLast(item);  // 큐의 리어(rear)에 항목 추가
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty.");
        }
        return queue.removeFirst();  // 큐의 프론트(front)에서 항목을 제거하고 반환
    }

    public boolean isEmpty() {
        return queue.isEmpty();  // 큐가 비어 있는지 여부 반환
    }

    public int size() {
        return queue.size();  // 큐의 현재 크기 반환
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty.");
        }
        return queue.getFirst();  // 큐의 프론트(front)에 위치한 항목 반환
    }
}
public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();  // 큐 생성

        queue.enqueue(10);  // 항목 삽입
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println("Dequeued item: " + queue.dequeue());  // Dequeued item: 10

        System.out.println("Front item: " + queue.peek());  // Front item: 20

        System.out.println("Is queue empty? " + queue.isEmpty());  // Is queue empty? false

        System.out.println("Queue size: " + queue.size());  // Queue size: 2
    }
}

참고

https://hoehen-flug.tistory.com/29
https://hoehen-flug.tistory.com/28
https://hoehen-flug.tistory.com/30
https://hoehen-flug.tistory.com/31?category=1077201