알고리즘에서 쓰이는 자료구조(데이터타입)

자바 알고리즘에서 주로 쓰이는 데이터 타입들을 한번 정리하고 가기 위해.. 작성한 글이다.

Tree나 Map과 HashTable의 경우 서로 겹치는 클래스들이 많다.

(단순히 Map의 역할만하지않고 순서를 신경쓰는 Map의 경우 LinkedHashMap을 쓴다던가 서로의 역할이 겹치는 경우가 많음)

배열 (Array):

연속된 메모리 공간에 같은 데이터 타입의 원소를 저장.
인덱스를 통해 원소에 접근할 수 있으며, 원소의 삽입과 삭제가 비효율적인 편.
이전에 정리한 적 있음
https://lets-do-the-odessey.tistory.com/60

리스트 (List):

원소들을 순서대로 저장하는 자료구조로, 주요한 종류로는 ArrayList와 LinkedList.
ArrayList는 배열 기반으로 동작하며, 접근 시간이 빠르지만 삽입 및 삭제 연산이 느린편.
LinkedList는 연결 리스트 기반으로 동작하며, 삽입 및 삭제 연산이 빠르지만 접근 시간이 느린편.

ArrayList

// 리스트 생성
ArrayList<String> list = new ArrayList<>();

// 원소 추가
list.add("Apple");
list.add("Banana");
list.add("Cherry");

// 원소 출력
System.out.println("ArrayList: " + list);

// 원소 조회
String fruit = list.get(1);
System.out.println("Second element: " + fruit);

// 원소 삭제
list.remove(1);
System.out.println("After removing second element: " + list);

LinkedList

LinkedList<String> list = new LinkedList<>();

// 원소 추가
list.add("Apple");
list.add("Banana");
list.add("Cherry");

// 원소 출력
System.out.println("LinkedList: " + list);

// 원소 조회
String fruit = list.get(1);
System.out.println("Second element: " + fruit);

// 원소 삭제
list.remove(1);
System.out.println("After removing second element: " + list);

스택 (Stack):

후입선출(LIFO) 원칙에 따라 데이터를 저장하는 자료구조.
주요 연산으로는 push(삽입), pop(삭제), peek(가장 위의 원소 확인)가 있음.

Stack

// 스택 생성
Stack<Integer> stack = new Stack<>();

// 원소 추가 (push)
stack.push(1);
stack.push(2);
stack.push(3);

// 스택의 상태 출력
System.out.println("Stack: " + stack);

// 스택에서 원소 제거 (pop)
int removedElement = stack.pop();
System.out.println("Popped element: " + removedElement);
System.out.println("Stack after popping: " + stack);

// 스택의 맨 위 원소 조회 (peek)
int topElement = stack.peek();
System.out.println("Top element: " + topElement);

// 스택이 비어있는지 확인 (empty)
boolean isEmpty = stack.empty();
System.out.println("Is the stack empty? " + isEmpty);

// 스택의 크기 확인 (size)
int size = stack.size();
System.out.println("Stack size: " + size);

큐 (Queue):

선입선출(FIFO) 원칙에 따라 데이터를 저장하는 자료구조.
주요 연산으로는 enqueue(삽입), dequeue(삭제), peek(가장 앞의 원소 확인).
큐와 스택의 역할을 모두 구행하는 Deque도 존재

Queue

큐라 대기열 자료 구조, 선입선출(FIFO)

// 큐 생성
Queue<String> queue = new LinkedList<>();

// 큐에 요소 추가 (offer)
queue.offer("Apple");
queue.offer("Banana");
queue.offer("Cherry");

// 큐의 상태 출력
System.out.println("Queue: " + queue);

// 큐에서 요소 제거 및 반환 (poll)
String removedElement = queue.poll();
System.out.println("Removed element: " + removedElement);
System.out.println("Queue after polling: " + queue);

// 큐의 맨 앞 요소 조회 (peek)
String frontElement = queue.peek();
System.out.println("Front element: " + frontElement);

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

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

Deque

Queue + Stack의 자료구조, 선입선출&후입선출 모두 지원

Deque<Integer> deque = new ArrayDeque<>();

// 데크의 앞쪽과 뒤쪽에 요소 추가
deque.addFirst(1);
deque.addLast(2);

// 데크의 앞쪽과 뒤쪽에서 요소 제거 및 반환
int first = deque.removeFirst(); // 1
int last = deque.removeLast(); // 2

// 데크에 요소 추가
deque.offerFirst(3);
deque.offerLast(4);

// 데크에서 요소 가져오기(제거하지 않음)
int peekFirst = deque.peekFirst(); // 3
int peekLast = deque.peekLast(); // 4

// 요소 출력
System.out.println("First: " + first + ", Last: " + last);
System.out.println("Peek First: " + peekFirst + ", Peek Last: " + peekLast);

우선순위 큐 (Priority Queue):

우선순위에 따라 데이터를 저장하는 자료구조.
일반적으로 최솟값 또는 최댓값을 빠르게 찾을 때 사용.

Priority Queue

큐지만 최소 힙임

// 우선순위 큐 생성
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

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

// 우선순위 큐의 상태 출력
System.out.println("PriorityQueue: " + priorityQueue);

// 우선순위 큐에서 요소 제거 및 반환 (poll)
int removedElement = priorityQueue.poll();
System.out.println("Removed element: " + removedElement);
System.out.println("PriorityQueue after polling: " + priorityQueue);

// 우선순위 큐에서 가장 우선순위가 높은 요소 조회 (peek)
int topElement = priorityQueue.peek();
System.out.println("Top element: " + topElement);

// 우선순위 큐가 비어있는지 확인 (isEmpty)
boolean isEmpty = priorityQueue.isEmpty();
System.out.println("Is the PriorityQueue empty? " + isEmpty);

// 우선순위 큐의 크기 확인 (size)
int size = priorityQueue.size();
System.out.println("PriorityQueue size: " + size);

만약 역순으로 하고 싶다면

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

만약 Queue안에 배열이 들어간다면 요소의 정렬 기준을 지정하려면 Comparator를 사용해야함

// 사용자 정의
PriorityQueue<Integer[]> priorityQueue = new PriorityQueue<>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] arr1, Integer[] arr2) {
                // 배열의 첫 번째 요소를 기준으로 정렬
                return Integer.compare(arr1[0], arr2[0]);
            }
        });

// 람다함수
PriorityQueue<Integer[]> priorityQueue = new PriorityQueue<>((arr1, arr2) -> Integer.compare(arr1[0], arr2[0]));

맵 (Map) / 딕셔너리 (Dictionary):

키-값 쌍을 저장하는 자료구조로, 주요한 종류로는 HashMap, TreeMap, LinkedHashMap 등이 있습니다.
검색, 삽입, 삭제 연산을 효율적으로 수행할 수 있습니다.

HashMap

저장된 데이터의 순서를 보장하지 않고, 빠른 검색속도를 원할때 사용

Map<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "One");
hashMap.put(2, "Two");
hashMap.put(3, "Three");

for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

TreeMap

데이터를 정렬된 순서로 저장(키값을 기준으로 정렬), 기본 오름차순 정렬

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");

for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

만약 정렬 순서를 사용자 정의하고 싶다면 마찬가지로 Comparator를 사용하면 된다.

// 1번 방법

// 내림차순으로 정렬하는 Comparator를 생성
Comparator<Integer> descendingOrder = Collections.reverseOrder();

// Comparator를 사용하여 TreeMap 생성
TreeMap<Integer, String> treeMap = new TreeMap<>(descendingOrder);

// 2번 방법 (람다를 사용해 Comparator구현)

TreeMap<Integer, String> treeMap = new TreeMap<>((a, b) -> b.compareTo(a)); // 내림차순 정렬

// 추가적으로 array가 key인 경우

// Comparator를 람다식으로 정의하여 TreeMap 생성
TreeMap<Integer[], String> treeMap = new TreeMap<>((a, b) -> {
    int cmp = Arrays.compare(b, a); // 내림차순으로 정렬
    if (cmp != 0) return cmp;
    return 1; // 중복된 키를 허용하지 않도록 추가 정렬 로직
});

LinkedHashMap

데이터의 저장 순서를 보장(추가한 순서대로 순서가 유지 됨), 추가 순서를 유지해야할때 사용

Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put(3, "Three");
linkedHashMap.put(1, "One");
linkedHashMap.put(2, "Two");

for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

세트 (Set):

중복을 허용하지 않는 데이터 집합을 나타내는 자료구조.
주요한 종류로는 HashSet, TreeSet, LinkedHashSet

HashSet

순서 보장X, 중복 원소 허용X

Set<String> hashSet = new HashSet<>();

// 데이터 추가
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");
hashSet.add("Banana"); // 중복된 데이터, 추가되지 않음

// 데이터 순회
for (String fruit : hashSet) {
    System.out.println(fruit);
}

TreeSet

이진 검색 트리 기반, 오름차순 정렬

Set<String> treeSet = new TreeSet<>();

// 데이터 추가
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");
treeSet.add("Banana"); // 중복된 데이터, 추가되지 않음

// 데이터 순회 (오름차순으로 정렬됨)
for (String fruit : treeSet) {
    System.out.println(fruit);
}

LinkedHashSet

원소의 추가 순서를 보장

Set<String> linkedHashSet = new LinkedHashSet<>();

// 데이터 추가
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
linkedHashSet.add("Cherry");
linkedHashSet.add("Banana"); // 중복된 데이터, 추가되지 않음

// 데이터 순회 (추가된 순서를 보장함)
for (String fruit : linkedHashSet) {
    System.out.println(fruit);
}

그래프 (Graph):

정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 다양한 그래프 알고리즘에 활용.
주요한 그래프 종류로는 무방향 그래프, 방향 그래프, 가중치 그래프 등이 있음.

자바에서 그래프 데이터 구조를 직접 제공하는 내장 클래스는 없음, 다반 외부 라이브러리 중 JGraphT가 존재(이건 알아보지 않을 예정)

트리 (Tree):

계층적인 데이터 구조로, 이진 트리, 이진 탐색 트리(BST), 힙(Heap) 등이 흔히 사용.
Heap의 경우 위에서 우선순위 큐가 최소 힙처럼 사용됨
TreeMap과 TreeSet은 이진 탐색 트리를 기반으로한 데이터 구조임(위에 예제 코드 존재)

해시 테이블 (Hash Table):

키와 값으로 데이터를 저장하는 자료구조로, 키를 해시 함수를 사용하여 값과 연결하는 방식으로 동작합니다.
빠른 검색과 삽입 연산을 지원하며, 주요한 종류로는 HashMap, HashTable이 있습니다. (hashmap은 위에 있음)

HashTable

키-값 쌍을 저장할때 사용됨, 중복된 키를 허용하지 않음, 순서를 보장하지 않음. (만약 순서를 보장하고싶으면 LinkedHashMap사용하면 됨)

// 해시 테이블 생성
Hashtable<String, Integer> hashtable = new Hashtable<>();

// put 메서드를 사용하여 키-값 쌍 추가
hashtable.put("apple", 3);
hashtable.put("banana", 2);
hashtable.put("cherry", 5);

// 값을 가져오기
int cherryCount = hashtable.get("cherry");
System.out.println("Cherry count: " + cherryCount);

// 키의 존재 확인
boolean containsBanana = hashtable.containsKey("banana");
System.out.println("Contains banana: " + containsBanana);

// 키-값 쌍 제거
hashtable.remove("banana");

// 해시 테이블의 크기 확인
int size = hashtable.size();
System.out.println("Hashtable size: " + size);

// 해시 테이블 비우기
hashtable.clear();
System.out.println(hashtable);

저작자표시

더이상미룰수없어

알고리즘에서 쓰이는 자료구조(데이터타입)

배열 (Array):

리스트 (List):

스택 (Stack):

큐 (Queue):

우선순위 큐 (Priority Queue):

맵 (Map) / 딕셔너리 (Dictionary):

세트 (Set):

댓글

티스토리툴바

알고리즘에서 쓰이는 자료구조(데이터타입)

배열 (Array):

리스트 (List):

스택 (Stack):

큐 (Queue):

우선순위 큐 (Priority Queue):

맵 (Map) / 딕셔너리 (Dictionary):

세트 (Set):

관련글

댓글

티스토리툴바