자료구조
자료를 정리하는 여러가지 구조
해야할 일 == 리스트
물건을 쌓아둠, 냉장고에 콜라를 넣은 것 == 스택
티켓 줄서기 ==큐
영어사전 == 사전, 탐색구조(이진트리)
지도 == 그래프
조직도 == 트리
알고리즘
주어진 문제를 처리하는 절차
프로그램은 논리적으로 자료구조와 알고리즘으로 구성되어 있다.프로그램
시험 성적을 읽어서 최고 점수를 구하는 프로그램
외부에서 점수가 입력되면 이 점수들을 처리하기 좋게끔 프로그램 내부의 어딘가에 저장시켜야 한다.
가장 쉽게 사용할 수 있는 것이 배열이다.
배열에 점수를 저장하면 바로 배열이 자료를 저장하는 구조 == 자료 구조
다음으로 필요한 것은 배열에 저장된 점수들 중에서 가장 큰 점수를 찾는 절차이다.
변수를 하나 만들고 배열의 첫 번째 요소 값을 변수에 대입한 다음,
이 변수와 배열 의 각 요소들을 순차적으로 비교하여,
만약 배열의 요소가 더 크다면 배열 요소의 값을 변수에 저장한다.
이런 식으로 배열의 끝까지 진행하면 최댓값을 찾을 수 있다.
이렇게 문제를 해결하는 절차를 알고리즘.
알고리즘 성능 분석 방법
시간복잡도
알고리즘의 실행시간 분석
데이터량에 따라 시간이 증가한다
가장 이상적 속도는 O(1)
다음으로는 O(log n)
공간복잡도
알고리즘이 사용하는 기억 공간 분석
반복 iteration
반복 구조를 사용하여 반복시키는 문장을 작성하는 프로그래밍
ex) for, while
순환 recursion
알고리즘, 함수가 자기 자신을 호출하여 문제를 해결하는 방법
종류
- factorial
- 피보나치 수열
- 이진 트리 알고리즘
- 이진 탐색
- 하노이탑
array
순서 있음, 중복 허용, 크기 고정
인덱스
| int[] arr = new int[5]; |
| addLast(int[] arr, int newValue) addFirst(int[] arr, int newValue) addAtIndex(int[] arr, int index, int newValue) |
- array
더보기
package collection.array;
import java.util.Arrays;
/**
* 배열
* 순서 있음
* 중복 허용
* 크기 고정
*/
public class ArrayMain1 {
public static void main(String[] args) {
int[] arr = new int[5];
arr[0] = 1;
arr[1] = 2;
System.out.println(Arrays.toString(arr));
// 조회 O(1)
System.out.println("조회: " + arr[1]);
int count = 0;
// 검색 O(N)
for (int a : arr) {
++count;
if (a == arr.length) {
System.out.println("검색 >> " + count);
}
}
addFirst(arr, 10);
System.out.println("맨 앞 추가>> " + Arrays.toString(arr));
addLast(arr, 11);
System.out.println("맨 뒤 추가>> " + Arrays.toString(arr));
addAtIndex(arr, 3, 12);
System.out.println("중간 추가>> " + Arrays.toString(arr));
}
private static void addLast(int[] arr, int newValue) {
arr[arr.length - 1] = newValue;
}
private static void addFirst(int[] arr, int newValue) {
for (int i = arr.length - 1; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = newValue;
}
private static void addAtIndex(int[] arr, int index, int newValue) {
for (int i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = newValue;
}
}
특징
- 인덱스 사용
인덱스가 있어서 검색 빠르다
한계
- 배열 크기를 미리 정해야한다
처음부터 미리 너무 많은 배열을 확보하면 메모리가 많이 낭비된다.
배열의 길이를 동적으로 변경할 수 없다
| 추가 | 앞 추가 O(1) + O(N) = O(N) 배열 위치 찾기O(1) 왼쪽 값을, 오른쪽으로 이동 O(N) |
중간 추가 O(1) + O(N/2) = O(N/2) 배열 위치 찾기O(1) 중간에서 추가하고 왼쪽 값을, 오른쪽으로 이동O(N/2) |
마지막 추가 O(1) |
| 조회 | O(1) | ||
| 수정 | - 검색 후, 수정 O(1) |
||
| 삭제 | 앞 삭제 O(1) + O(N) = O(N) 배열 위치 찾기O(1) 오른쪽 값을, 왼쪽으로 이동 |
중간 삭제 O(1) + O(N/2) = O(N/2) 배열 위치 찾기O(1) 인덱스에서 오른쪽 값을, 왼쪽으로 이동 |
마지막 삭제 O(1) |
| 순회 | - 순회 순회는 처음부터 끝까지 가야하기때문에 O(N) |
정렬
| 듀얼 피봇 퀵 정렬 |  |
list
- array list
순서 있음, 중복 허용, 크기 동적
/**
* ArrayList
* 순서 있음
* 중복 허용
* 크기 동적
*/
public class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] objectData;// 동적으로 사이즈 변함
private int size = 0;
}
더보기
package collection.array;
import java.util.Arrays;
/**
* ArrayList
* 순서 있음
* 중복 허용
* 크기 동적
*/
public class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] objectData;// 동적으로 사이즈 변함
private int size = 0;
public MyArrayList() {
this.objectData = new Object[DEFAULT_CAPACITY];
}
public MyArrayList(int initialCapacity) {
this.objectData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(E e) {
if (size == objectData.length) {
grow();
}
// 증가시키고 다시 원래대로 추가
objectData[size] = e;
size++;
}
// 특정 위치 추가
public void add(int index, E e) {
if (size == objectData.length) {
grow();
}
// 인덱스 기준으로 오른쪽 데이터가 -> 오른쪽으로 이동
shiftRightFrom(index);
objectData[index] = e;
size++;
}
// 인덱스 기준으로 오른쪽 데이터가 -> 오른쪽으로 이동
private void shiftRightFrom(int index) {
// 배열의 마지막에서부터 인덱스까지 오른쪽으로 밀기(마지막 배열 값은 사라진다)
for (int i = size; i > index; i--) {
objectData[i] = objectData[i - 1];
}
}
public E remove(int index) {
E oldVaule = get(index);
// 인덱스 기준으로 오른쪽 데이터가 -> 왼쪽으로 이동
shiftLeftFrom(index);
size--;
objectData[size] = null;// 마지막 지우기
return oldVaule;
}
// 인덱스 기준으로 오른쪽 데이터가 -> 왼쪽으로 이동
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
objectData[i] = objectData[i + 1];
}
}
private void grow() {
int oldCapacity = objectData.length;
int newCapacity = oldCapacity * 2;
objectData = Arrays.copyOf(objectData, newCapacity);// 대체 해버림
}
public E get(int index) {
return (E) objectData[index];
}
public E set(int index, E element) {
E oldValue = get(index);
objectData[index] = element;
return oldValue;
}
public int indexOf(E o) {
for (int i = 0; i < size; i++) {
if (o.equals(objectData[i])) {
return i;
}
}// for end
return -1;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(objectData, size)) + " size=" + size + ", capacity=" + objectData.length;
}
}
| private Object[] elementData; private int size = 0; |
 |
| int size() grow() |
 |
| add(E e) add(int index, E e) |
 |
| E get(int index) E set(int index, E element) E remove(int index) shiftRightFrom(int index) shiftLeftFrom(int index) int indexOf(E o) |
   |
- linked list
Node 등장
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
}
더보기
package collection.link;
public class MyLinkedList<E> {
private Node<E> first;
private int size = 0;
public void add(E e) {
Node<E> newNode = new Node<>(e);
if (first == null) {
first = newNode;
} else {
Node<E> lastNode = getLastNode();
lastNode.next = newNode;
}
size++;
}
public void add(int index, E e) {
Node<E> newNode = new Node<>(e);
if (first == null) {
first = newNode;
} else {
Node<E> x = getNode(index - 1);
newNode.next = x.next;
x.next = newNode;
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
public E set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
public E get(int index) {
Node<E> c = getNode(index);
return c.item;
}
// 내부용
private Node<E> getNode(int idx) {
Node<E> c = first;
for (int i = 0; i < idx; i++) {
c = c.next;
}
return c;
}
public E remove(int index) {
Node<E> c = getNode(index);
E removeItem = c.item;
if (index == 0) {
first = c.next;
} else {
Node<E> x = getNode(index - 1);
x.next = c.next;
}
c.item = null;
c.next = null;
size--;
return removeItem;
}
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "collection.link.MyLinkedList{" +
"first=" + first +
", size=" + size +
'}';
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> temp = this;
sb.append("[");
while (temp != null) {
sb.append(temp.item);
if (temp.next != null) {
sb.append("->");
}
temp = temp.next;
}
sb.append("]");
return sb.toString();
}
}
}- single linked list
- double linked list
public class Node {
Object item;
Node next; //다음 노드 참조
Node prev; //이전 노드 참조
}- circular linked list
stack
- array 구현
class ArrayStack {
private int[] stack;
private int top;
private int capacity;
}더보기
class ArrayStack {
private int[] stack;
private int top;
private int capacity;
public ArrayStack(int capacity) {
this.capacity = capacity;
stack = new int[capacity];
top = -1;
}
// 요소 추가
public void push(int value) {
if (top == capacity - 1) {
throw new StackOverflowError("Stack is full");
}
stack[++top] = value;
}
// 요소 제거
public int pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack[top--];
}
// 맨 위 요소 확인
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack[top];
}
// 스택이 비었는지 확인
public boolean isEmpty() {
return top == -1;
}
}
public class StackExample {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element: " + sta- LinkedList 구현
class LinkedListStack {
private LinkedList<Integer> stack;
}
더보기
import java.util.LinkedList;
class LinkedListStack {
private LinkedList<Integer> stack;
public LinkedListStack() {
stack = new LinkedList<>();
}
// 요소 추가
public void push(int value) {
stack.addFirst(value); // 맨 앞에 추가
}
// 요소 제거
public int pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.removeFirst();
}
// 맨 위 요소 확인
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return stack.getFirst();
}
// 스택이 비었는지 확인
public boolean isEmpty() {
return stack.isEmpty();
}
}
public class StackExample {
public static void main(String[] args) {
LinkedListStack stack = new LinkedListStack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element: " + stack.peek()); // 출력: 30
System.out.println("Popped element: " + stack.pop()); // 출력: 30
System.out.println("Popped element: " + stack.pop()); // 출력: 20
System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false
}
}- Deque 구현
더보기
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeStackExample {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
// 요소 추가 (push)
stack.push(10);
stack.push(20);
stack.push(30);
// 요소 확인 (peek)
System.out.println("Top element: " + stack.peek()); // 출력: 30
// 요소 제거 (pop)
System.out.println("Popped element: " + stack.pop()); // 출력: 30
System.out.println("Popped element: " + stack.pop()); // 출력: 20
// 스택이 비었는지 확인
System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false
// 스택 요소 출력
System.out.println("Remaining stack: " + stack); // 출력: [10]
}
}
queue
- 자바에서 queue
queue |
 |
deque |
 |
- queue 구현
| array 구현 Object[] elements int head int tail |
 |
| linkedList 구현 Node<> E item; Node<E> next; Node<E> head; Node<E> last; |
 |
| array | linkedlist | |
| 추가 |  |
  |
- circular queue
- priority queue
배열로 관리함
값을 비교해서 저장함
더보기
package main._202401._02;
import java.util.Collections;
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
System.out.println("expect: [0,0], result:" + solution(new String[] {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"}));
System.out.println("expect: [333, -45], result:" + solution(new String[] {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"}));
}
public static int[] solution(String[] operations) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (String oper : operations) {
if (oper.startsWith("I")) {
String[] split = oper.split(" ");
minHeap.add(Integer.parseInt(split[1]));
maxHeap.add(Integer.parseInt(split[1]));
} else if (oper.startsWith("D 1")) {
if (!maxHeap.isEmpty()) {
int max = maxHeap.poll();
minHeap.remove(max);
}
} else if (oper.equals("D -1")) {
if (!minHeap.isEmpty()) {
int min = minHeap.poll();
maxHeap.remove(min);
}
}
}
// 결과 계산
int max = maxHeap.isEmpty() ? 0 : maxHeap.peek();
int min = minHeap.isEmpty() ? 0 : minHeap.peek();
return new int[] {max, min};
}
}| 구성 |  |
| 추가 |  |
| 추가시 정렬 | index에 e를 넣는다 |
| 삭제시 정렬 |  |
| 값 찾아서 삭제 |
   |
| 최상위 값 꺼내기 |  |
| 순회 O(N) |
 |
선형 자료 구조(inear data structure)
자료들이 직선과 같이 나열되어 있는 구조
ex) array, list, stact, queue
계층 자료 구조(hierarchical structure)
ex) tree
tree
트리(Tree)의 특징
- 계층적 구조:
- 루트(Root) 노드에서 시작해서 계층적으로 확장됩니다.
- 사이클 없음:
- 트리는 사이클(Cycle)이 없는 연결된 비순환 그래프입니다.
- 노드 수와 간선 수:
- 노드가 N개일 때, 간선은 항상 N-1개입니다.
- 단방향:
- 트리는 항상 부모 → 자식으로 연결됩니다.
- 루트 존재:
- 트리는 반드시 루트 노드가 있으며, 하나의 루트만 존재합니다.
- binary tree
- array 구현
- linked list 구현
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
더보기
class BinaryTree {
TreeNode root;
// 노드 삽입
public void insert(int data) {
root = insertRecursively(root, data);
}
private TreeNode insertRecursively(TreeNode root, int data) {
if (root == null) {
return new TreeNode(data);
}
if (data < root.data) {
root.left = insertRecursively(root.left, data);
} else if (data > root.data) {
root.right = insertRecursively(root.right, data);
}
return root;
}
// 노드 탐색
public boolean search(int data) {
return searchRecursively(root, data);
}
private boolean searchRecursively(TreeNode root, int data) {
if (root == null) {
return false;
}
if (root.data == data) {
return true;
}
if (data < root.data) {
return searchRecursively(root.left, data);
}
return searchRecursively(root.right, data);
}
// 중위 순회 (In-order Traversal: Left -> Root -> Right)
public void inOrderTraversal() {
inOrderRecursively(root);
System.out.println();
}
private void inOrderRecursively(TreeNode root) {
if (root != null) {
inOrderRecursively(root.left);
System.out.print(root.data + " ");
inOrderRecursively(root.right);
}
}
// 전위 순회 (Pre-order Traversal: Root -> Left -> Right)
public void preOrderTraversal() {
preOrderRecursively(root);
System.out.println();
}
private void preOrderRecursively(TreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preOrderRecursively(root.left);
preOrderRecursively(root.right);
}
}
// 후위 순회 (Post-order Traversal: Left -> Right -> Root)
public void postOrderTraversal() {
postOrderRecursively(root);
System.out.println();
}
private void postOrderRecursively(TreeNode root) {
if (root != null) {
postOrderRecursively(root.left);
postOrderRecursively(root.right);
System.out.print(root.data + " ");
}
}
}
public class BinaryTreeExample {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// 노드 삽입
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// 탐색
System.out.println("Search 40: " + tree.search(40)); // 출력: true
System.out.println("Search 90: " + tree.search(90)); // 출력: false
// 순회 (Traversal)
System.out.println("In-order Traversal:");
tree.inOrderTraversal(); // 출력: 20 30 40 50 60 70 80
System.out.println("Pre-order Traversal:");
tree.preOrderTraversal(); // 출력: 50 30 20 40 70 60 80
System.out.println("Post-order Traversal:");
tree.postOrderTraversal(); // 출력: 20 40 30 60 80 70 50
}
}
- binary search tree
특징:
- 모든 왼쪽 자식의 값은 부모보다 작다.
- 모든 오른쪽 자식의 값은 부모보다 크다.
- 삽입, 탐색의 평균 시간 복잡도는 O(log n).
더보기
class BinarySearchTree {
private TreeNode root; // 트리의 루트 노드
// 삽입 메서드
public void insert(int data) {
root = insertRecursively(root, data);
}
private TreeNode insertRecursively(TreeNode root, int data) {
if (root == null) {
return new TreeNode(data);
}
if (data < root.data) {
root.left = insertRecursively(root.left, data);
} else if (data > root.data) {
root.right = insertRecursively(root.right, data);
}
return root;
}
// 검색 메서드
public boolean search(int data) {
return searchRecursively(root, data);
}
private boolean searchRecursively(TreeNode root, int data) {
if (root == null) {
return false;
}
if (data == root.data) {
return true;
}
if (data < root.data) {
return searchRecursively(root.left, data);
} else {
return searchRecursively(root.right, data);
}
}
// 삭제 메서드
public void delete(int data) {
root = deleteRecursively(root, data);
}
private TreeNode deleteRecursively(TreeNode root, int data) {
if (root == null) {
return null;
}
if (data < root.data) {
root.left = deleteRecursively(root.left, data);
} else if (data > root.data) {
root.right = deleteRecursively(root.right, data);
} else {
// 자식이 없는 경우
if (root.left == null && root.right == null) {
return null;
}
// 한쪽 자식만 있는 경우
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// 두 자식이 있는 경우: 오른쪽 서브트리에서 최소값 찾기
- AVL tree
- red black tree
- B tree
- B+ tree
- segment tree
- fenwick tree
graph
그래프(Graph)의 특징
- 비계층적 구조:
- 트리와 달리 노드 간의 관계가 계층적이지 않고, 다양한 연결을 가질 수 있습니다.
- 사이클 허용:
- 그래프는 사이클이 존재할 수 있습니다.
- 방향/무방향:
- 그래프는 방향 그래프(Directed Graph) 또는 무방향 그래프(Undirected Graph)일 수 있습니다.
- 루트 없음:
- 그래프에는 루트 노드가 없습니다.
- 간선 수 제한 없음:
- 간선의 수에 제한이 없습니다.
class Graph {
private Map<Integer, List<Integer>> adjacencyList;
}
더보기
import java.util.*;
class Graph {
private Map<Integer, List<Integer>> adjacencyList;
public Graph() {
this.adjacencyList = new HashMap<>();
}
// 노드 추가
public void addNode(int node) {
adjacencyList.putIfAbsent(node, new ArrayList<>());
}
// 간선 추가
public void addEdge(int from, int to) {
adjacencyList.get(from).add(to); // 방향 그래프
// adjacencyList.get(to).add(from); // 무방향 그래프일 경우
}
// 그래프 출력
public void printGraph() {
for (var entry : adjacencyList.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
// BFS (너비 우선 탐색)
public void bfs(int startNode) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adjacencyList.get(node)) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
System.out.println();
}
}
public class GraphExample {
public static void main(String[] args) {
Graph graph = new Graph();
// 노드 추가
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
// 간선 추가
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
System.out.println("Graph Representation:");
graph.printGraph();
System.out.print("BFS Traversal starting from node 1: ");
graph.bfs(1); // 출력: 1 2 3 4 5
}
}
- directed graph
- undirected graph
- weight graph
set
* 유일성(중복X)
* 순서 미보장
* 인덱스 X
* 빠른 검색
ex) 회원 ID, 집합
- HashSet(순서 X),
- LinkedHashSet(순서 O)
- TreeSet(정렬 O)
Tree: 부모 Node, 자식 Node
package collection.set;
/**
* 유일성(중복X)
* 순서 미보장
* 인덱스 X
* 빠른 검색
* <p>
* ex) 회원 ID, 집합
* <p>
* HashSet(순서 X), LinkedHashSet(순서 O)
* TreeSet(정렬 O)
* <p>
* Tree:
* 부모 Node, 자식 Node
*/
public interface MySet<E> {
// 인덱스가 없어서 기능이 단순
boolean add(E element);
boolean remove(E value);
boolean contains(E value);
}
- hash set
set은 추가할 때마다 값이 유일한지 O(N) 탐색해야 함
따라서 Hash를 적용해서 탐색을 개선한 것이 hash set
Hash는 index를 사용한다
hashTable LinkedList안에 LinkedList 생성 * [[], [], [], [], ...]
public class MyHashSetV2 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
LinkedList<Object>[] buckets;
private int size = 0;
private int capacity = DEFAULT_INITIAL_CAPACITY;
// 기본 생성자
public MyHashSetV2() {
initBuckets();
}
public MyHashSetV2(int capacity) {
this.capacity = capacity;
initBuckets();
}
private void initBuckets() {
buckets = new LinkedList[capacity];// 생성
// 이중 배열
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
}
더보기
package collection.set;
import java.util.Arrays;
import java.util.LinkedList;
/**
* 추가할 때마다 값이 유일한지 O(N) 탐색해야 함
* 따라서 Hash를 적용해서 탐색을 개선한다
* Hash는 index를 사용한다
* <p>
* hashTable LinkedList안에 LinkedList 생성
* [[], [], [], [], ...]
* <p>
* hash 저장: O(1), 최악: O(N)
* hash 조회: O(1), 최악: O(N)
*/
public class MyHashSetV2 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
LinkedList<Object>[] buckets;
private int size = 0;
private int capacity = DEFAULT_INITIAL_CAPACITY;
// 기본 생성자
public MyHashSetV2() {
initBuckets();
}
public MyHashSetV2(int capacity) {
this.capacity = capacity;
initBuckets();
}
private void initBuckets() {
buckets = new LinkedList[capacity];// 생성
// 이중 배열
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
// size
public int getSize() {
return size;
}
// 추가
public boolean add(Object value) {
int hashIndex = hashIndex(value);
// 중복 체크후 저장
LinkedList<Object> bucket = buckets[hashIndex];//O(1)
if (bucket.contains(value)) {// 과거에 O(N) -> 평균적으로 1,2개 들어있어서 O(1)
return false;
}
bucket.add(value);
size++;
return true;
}
// hash Table
private int hashIndex(Object value) {
//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
return Math.abs(value.hashCode()) % capacity;
}
// 탐색
public boolean contains(Object value) {// 과거에 O(N) -> 평균적으로 1,2개 들어있어서 O(1)
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];//O(1)
return bucket.contains(value);
}
// 삭제
public boolean remove(Object value) {
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];
// 중복 체크후 제거
boolean removedResult = bucket.remove((Object) value);
if (removedResult) {
size--;
return true;
} else {
return false;
}
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
'}';
}
}
- linked hash set
- tree set
class Node {
Object item;
Node left;
Node right;
}
hash table
해시 인덱스를 사용하는 경우
| 데이터 저장 | 평균: O(1) 최악: O(n) |
 |
| 데이터 조회 | 평균: O(1) 최악: O(n) |
 |
- 해시 충돌
- 최악
map
`Set` 과 `Map` 의 구현체는 거의 같다.
실제로 자바 `HashSet` 의 구현은 대부분 `HashMap` 의 구현을 가져다 사용한다.
`Map` 에서 `Value` 만 비워두면`Set`으로 사용할 수 있다.
- HashSet -> HashMap
- LinkedHashSet -> LinkedHashMap
- TreeSet -> TreeMap
heap
perfect binary tree
- min heap
- max heap
'기술 블로그 (Tech Blog) > Dev Notes' 카테고리의 다른 글
| singleton - Problem&Solve (0) | 2024.12.22 |
|---|---|
| 4대천왕👑이 정리한 객체 정의서(Gof 디자인패턴) (0) | 2024.12.07 |
| 사가패턴은 왜 사가라고 하는걸까? 🍎아님 (0) | 2024.11.16 |
