[Java] 자바 자료구조 간단 정리 - 코테용

≣ 목차

 

자료구조

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법이나 형식을 의미합니다. 자료구조는 데이터의 조직, 관리, 저장 방식을 정의하며, 이를 통해 데이터에 대한 접근, 수정, 삭제 등의 작업을 효율적으로 수행할 수 있습니다. 자바에서 자료구조는 Array, List, Hash, Map, Stack 등 여러가지만 있지만 코딩테스트에서 자주 사용되는 자료구조만 정리하겠습니다.

 

 

배열

자바에서 배열은 객체로 취급되며, 배열의 이름은 배열 객체의 메모리 주소를 참조하여 배열이 저장된 메모리 위치를 가리키는 포인터와 같은 역할을 합니다. 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조로, 배열의 값은 인덱스를 통해 직접 접근할 수 있으며, 선언한 자료형의 값만 저장할 수 있습니다. 배열의 크기는 처음 선언할 때 지정할 수 있지만, 한 번 선언하면 크기를 늘리거나 줄일 수 없으며, 특정 인덱스에 값을 채워넣거나 삭제할 경우에는 다른 인덱스가 이동해야 하는 과정을 거쳐야 합니다.

출처: https://poiemaweb.com/js-array-is-not-arrray

 

 

리스트 - Linked List

리스트는 배열과 달리 인덱스가 없어 특정 값에 한 번에 접근할 수 없으며, 처음 포인터부터 순서대로 접근해야 하므로 접근 속도가 느립니다. 그러나 리스트는 값과 포인터가 묶여 있어 데이터를 삽입하거나 삭제하는 속도가 배열보다 빠르며, 리스트의 크기는 정하지 않고 자유롭게 변경할 수 있습니다. 단 ArrayList는 내부적으로 배열을 사용해서 인덱스가 없어서 생기는 단점을 해결할 수 있습니다.

 

스택 - Stack

스택은 LIFO(Last In, First Out) 구조로, 마지막에 추가된 데이터가 가장 먼저 제거되며, 요소의 추가(push)와 제거(pop)는 한 쪽 끝에서만 이루어지고, 재귀 호출을 지원합니다.

출처: https://yoongrammer.tistory.com/45

import java.util.Stack;

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

        stack.push(10); // 스택에 요소 추가
        stack.push(20);
        stack.push(30);

        System.out.println(stack.pop()); // 30 (마지막 요소 제거 및 반환)
        System.out.println(stack.peek()); // 20 (제거 없이 확인)
        System.out.println(stack.isEmpty()); // false (비어있는지 확인)
    }
}

 

 

큐 - Queue

큐는 FIFO(First In, First Out) 구조로, 가장 먼저 추가된 데이터가 가장 먼저 제거되며, 요소의 추가(enqueue)와 제거(dequeue)는 양쪽 끝에서 이루어지고, 주로 작업 스케줄링에 사용됩니다.

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

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

        queue.offer(10); // 큐에 요소 추가
        queue.offer(20);
        queue.offer(30);

        System.out.println(queue.poll()); // 첫 번째 요소 제거 및 반환
        System.out.println(queue.peek()); // 제거 없이 확인
        System.out.println(queue.isEmpty()); // 비어있는지 확인
    }
}

출처: https://www.geeksforgeeks.org/introduction-and-array-implementation-of-queue/

 

 

덱 - Deque 

덱은 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조입니다. 스택과 큐의 특성을 모두 갖춘 형태로, 유연한 데이터 처리가 가능합니다.

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

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

        deque.addFirst(10); // 앞에 추가
        deque.addLast(20); // 뒤에 추가
        deque.offerFirst(5); // 앞에 추가 (예외 발생 X)
        deque.offerLast(25); // 뒤에 추가 (예외 발생 X)

        System.out.println(deque.pollFirst()); // 첫 번째 요소 제거 및 반환
        System.out.println(deque.pollLast()); // 마지막 요소 제거 및 반환
        System.out.println(deque.peekFirst()); // 첫 번째 요소 확인
        System.out.println(deque.peekLast()); // 마지막 요소 확인
    }
}

출처: https://yesdohyun.tistory.com/21

 

 

우선순위 큐 - PriorityQueue

우선순위 큐는 일반적인 큐와 달리 각 요소에 우선순위를 부여하여, 우선순위가 높은 요소가 먼저 제거되는 큐입니다.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); 

        pq.offer(30); // 추가
        pq.offer(10);
        pq.offer(20);

        System.out.println(pq.poll()); // 최소값 제거
        System.out.println(pq.peek()); // 최소값 확인
    }
}

 

 

해쉬 맵 - Hash Map

해시 맵은 키-값 쌍으로 데이터를 저장하는 자료구조이며, 키를 통해 값에 빠르게 접근할 수 있어 데이터 검색 속도가 매우 빠릅니다. 해쉬 맵은 중복 키를 허용하지 않습니다.

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        map.put("apple", 3); // 키-값 추가
        map.put("banana", 2);
        map.put("cherry", 5);

        System.out.println(map.get("banana")); // 키에 해당하는 값 반환
        System.out.println(map.containsKey("apple")); // 키 존재 여부 확인
        System.out.println(map.containsValue(5)); // 값 존재 여부 확인

        map.remove("cherry"); // 특정 키 삭제
        System.out.println(map.size()); // 현재 저장된 개수
    }
}

출처: https://velog.io/@db_jam/Java-%ED%95%B4%EC%8B%9C%EB%A7%B5HashMap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC

 

 

 

 

참고자료

김종관, Do it! 알고리즘 코딩 테스트 자바 편, 이지스퍼블리싱