ฅ^._.^ฅ

배열과 리스트

배열(Array) 이란?

메모리 상에서 연속된 공간을 차지하는 데이터 구조

인덱스를 이용하여 O(1) 시간 복잡도로 접근 가능

배열 예제

 int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[2]); // O(1) - 즉시 접근 가능

➡︎ 빠른 조회 가능

➡︎ 크기가 고정되어 있고, 삽입/삭제가 비효율적

연결 리스트(Linked List) 란?

노드(Node) 와 포인터(Pointer) 로 구성된 데이터 구조

시간 복잡도: 삽입/삭제는 O(1), 검색 속도는 O(N)

단일 연결 리스트 예제

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 temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }
}

➡︎ 동적 크기 조절 가능

➡︎ 연속된 메모리 공간 사용하지 않아도 되지만, 노드 탐색 속도가 느림

배열 vs 연결 리스트 비교

스택과 큐

스택(Stack) 이란?

후입선출(LIFO, Last In First Out) 구조

재귀 함수 호출, 되돌리기(Undo), 괄호 검사 등에 활용

스택 예제

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3 (후입선출)

➡︎ 마지막에 넣은 데이터가 가장 먼저 제거

큐(Queue) 란?

선입선출(FIFO, First In First Out) 구조

작업 대기열, 너비 우선 탐색(BFS) 등에 활용

큐 예제

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

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 출력: 1 (선입선출)

➡︎ 먼저 들어온 데이터가 먼저 제거

스택 vs 큐