선형 자료구조

배열(Array)

• 많은 수의 데이터를 다룰 때 사용하는 자료구조
• 각 데이터를 인덱스와 1:1 대응하도록 구성
• 데이터가 메모리 상에 연속적으로 저장됨
• 배열의 장점
  • 인덱스를 이용하여 데이터에 빠르게 접근 가능
• 배열의 단점
  • 데이터의 추가/삭제가 번거로운 편
    • 미리 최대 길이를 정해서 생성해야 함
    • 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성
    • 데이터 삭제 시, 인덱스를 유지하기 위해 빈공간 유지

public class ArrayExample {
    public static void main(String[] args) {
        // 배열 초기화
        int[] arr = {1, 2, 3, 4, 5};

        // 원소 접근
        System.out.println(arr[2]); // 3

        // 배열 크기
        System.out.println(arr.length); // 5

        // 배열 수정
        arr[2] = 10;
        System.out.println(arr[2]); // 10

        // 배열 순회
        for (int num : arr) {
            System.out.print(num + " "); // 1 2 10 4 5
        }
    }
}

스택(Stack)

• 후입선출(LIFO) 자료구조
• 데이터의 입력된 순서의 역순으로 처리되어야 할 때 사용
• Stack stack = new Stack();
• push, pop, peek, contains, size, empty등...

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 스택 초기화
        Stack<Integer> stack = new Stack<>();

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

        System.out.println(stack); // [1, 2, 3]

        // 제거 (pop)
        int topElement = stack.pop();
        System.out.println(topElement); // 3
        System.out.println(stack); // [1, 2]

        // 스택 최상단 원소 확인 (peek)
        System.out.println(stack.peek()); // 2

        // 스택이 비었는지 확인 (isEmpty)
        System.out.println(stack.isEmpty()); // false
    }
}

큐(Queue)

• 선입선출(FIFO) 자료구조
• 입력 순서대로 데이터 처리가 필요할때(BFS등..)
• Queue queue = new LinkedList();
• add, poll, peek, contains, size, empty, clear등...

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

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

        // 삽입 (offer)
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        System.out.println(queue); // [1, 2, 3]

        // 제거 (poll)
        int frontElement = queue.poll();
        System.out.println(frontElement); // 1
        System.out.println(queue); // [2, 3]

        // 큐의 첫 번째 원소 확인 (peek)
        System.out.println(queue.peek()); // 2

        // 큐가 비었는지 확인 (isEmpty)
        System.out.println(queue.isEmpty()); // false
    }
}

데크(Deque)

• 양쪽에서 삽입과 삭제가 가능한 자료구조
• 스택과 큐를 합친 느낌
• 입력 제한 데크(Scroll)
  • 한 쪽의 입력을 제한한 데크
• 출력 제한 데크(Shelf)
  • 한 쪽의 출력을 제한한 데크
• Deque deque = new ArrayDeque();
• addFirst, addLast, removeFirst, removeLast등...

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
    public static void main(String[] args) {
        // 덱 초기화
        Deque<Integer> deque = new LinkedList<>();

        // 앞쪽 삽입 (addFirst)
        deque.addFirst(1);
        deque.addFirst(2);
        System.out.println(deque); // [2, 1]

        // 뒤쪽 삽입 (addLast)
        deque.addLast(3);
        System.out.println(deque); // [2, 1, 3]

        // 앞쪽 제거 (removeFirst)
        int front = deque.removeFirst();
        System.out.println(front); // 2
        System.out.println(deque); // [1, 3]

        // 뒤쪽 제거 (removeLast)
        int back = deque.removeLast();
        System.out.println(back); // 3
        System.out.println(deque); // [1]

        // 첫 번째 원소 확인 (peekFirst)
        System.out.println(deque.peekFirst()); // 1

        // 마지막 원소 확인 (peekLast)
        System.out.println(deque.peekLast()); // 1

        // 덱이 비었는지 확인 (isEmpty)
        System.out.println(deque.isEmpty()); // false

        // 순회
        deque.addFirst(2);
        deque.addLast(3);
        for (int num : deque) {
            System.out.print(num + " "); // 2 1 3
        }
    }
}

연결 리스트(Linked List)

• 데이터를 링크로 연결해서 관리하는 자료구조

• 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음

• 연결 리스트의 장점

  • 데이터 공간을 미리 할당할 필요 없음
  • 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이

• 열결 리스트의 단점

  • 연결구조를 위한 별도 데이터 공간 필요
  • 연결 정보를 찾는 시간이 필요
  • 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

• 연결 리스트 기본 구조

  • 노드 : 데이터 저장 단위, 값과 포인터로 구성

• 연결 리스트 기본 연산

  • 데이터 추가 : 데이터 추가 위치에 따른 연결 잡업이 필요
  • 데이터 삭제 : 데이터 추가와 동일

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // 연결 리스트 초기화
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 삽입 (add)
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println(linkedList); // [1, 2, 3]

        // 특정 위치에 삽입 (add(index, value))
        linkedList.add(1, 10);
        System.out.println(linkedList); // [1, 10, 2, 3]

        // 삭제 (remove)
        linkedList.remove(1); // 인덱스 1의 원소 제거
        System.out.println(linkedList); // [1, 2, 3]

        // 첫 번째 요소 확인 (getFirst)
        System.out.println(linkedList.getFirst()); // 1

        // 마지막 요소 확인 (getLast)
        System.out.println(linkedList.getLast()); // 3

        // 크기 확인 (size)
        System.out.println(linkedList.size()); // 3

        // 순회
        for (int num : linkedList) {
            System.out.print(num + " "); // 1 2 3
        }
    }
}

해시 테이블(Hash Table)

• 키, 값을 대응시켜 저장하는 데이터 구조
  • 키를 통해 해당 데이터에 빠르게 접근 가능
• 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
• 해시 테이블 구조
  • 키 : 해시 테이블 접근을 위한 입력 값
  • 해시 함수 : 키를 해시 값으로 매핑하는 연산
  • 해시 값 : 해시 테이블의 인덱시
  • 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        // 해시 테이블 초기화
        HashMap<String, Integer> map = new HashMap<>();

        // 삽입 (put)
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // 값 접근 (get)
        System.out.println(map.get("Alice")); // 25

        // 키 존재 여부 확인 (containsKey)
        System.out.println(map.containsKey("Bob")); // true

        // 값 존재 여부 확인 (containsValue)
        System.out.println(map.containsValue(40)); // false

        // 원소 제거 (remove)
        map.remove("Charlie");
        System.out.println(map); // {Alice=25, Bob=30}

        // 모든 키와 값 순회
        for (String key : map.keySet()) {
            System.out.println(key + " -> " + map.get(key));
        }
    }
}