💡 선형조사법 (Linear Probing) 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법이다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 한다. 예시 객체 x 객체 x의 hashCode 값인 h를 구한다. h를 양수로 변환 -> h & 0x7FFFFFFF; 테이블의 크기와 % 연산 -> h % table.size(); h를 가지고 x를 적절한 위치로 저장, 이 때 위치는 hashCode의 값에 따라 다름 객체 y 위와 동일한 방법으로 h를 구한다. x의 위치와 동일한 값이 나오면 x의 위치에 y를 저장해야 한다. 이런 상황을 충돌이라고 한다. 해결 x의 다음 칸에 y를 저장 y의 위치가 바뀌었다는 사실을 알려야 한다.\ 삭제의 경우 데이..

💡 Hash Chaining 가장 안정적이며 보편적으로 사용되는 자료구조 중 하나이다. 파이썬의 딕셔너리도 이것을 기반으로 만들어졌으며 자바에서도 쉽게 해시를 만들 수 있게 API를 제공한다. 펄에서도 이 방법으로 연상 배열과 해시를 만든다. 해시는 사실상 배열 1개로 구성되어 있으며, 요소들이 들어가야 할 위치에 추가되면서 배열은 점점 채워진다. 그래서 배열의 위치마다 새로운 자료구조를 만들면서 수많은 데이터를 수용할 수 있도록 만드는것이다. 즉, Hash 배열의 각 요소에 자료구조인 LinkedList를 사용하며 각 요소는 테이블의 크기보다 클 수 있다. 어떤 자료구조가 가장 적합할까? 정답은 LinkedList 이다. 체인을 만들기 위해 배열의 각 위치마다 LinkedList를 만들어 주는 방법이며..

💡 Hash 연결 리스트에 비해 검색 & 추가 & 제거 & 수정의 시간복잡도 효율이 좋은 자료구조인 키 & 값 기반의 Hash Hash -> Key & Value Array의 구조로 가정함 해시는 사실상 배열 1개로 구성되어 있다. Hash의 메서드 시간복잡도를 효율적으로 바꿀 수 있는 메서드들 add() remove(0 lookup() / find() / contains() change() 시간복잡도가 최소 O(n)이 걸릴수 밖에 없는 메서드들 all entries all keys all values Hash에선 시간복잡도가 O(1)이지만 연결 리스트에선 O(n)이던 메서드들 size() isEmpty() isFull() loadFactor() public static void main(String[]..

💡 큐 데이터를 순서대로 쌓는 자료구조 먼저 들어간 데이터는 제일 처음에 나오는 FIFO 구조 데이터 삽입은 Add, 데이터 추출은 Poll이다. 데이터를 하나씩 넣고 뺄수 있다. 입출력 방향이 두 곳이며 방향이 다르다. 우선순위 큐 (Priority Queue) 들어간 순서와 상관엇이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 front에 항상 최대값 or 최소값이 위치한다. 일반적으로 Heap을 이용해 구현하는데 Heap은 트리 종류 중 하나이다. 구현 add(): 큐에 데이터를 추가할 수 있어야 합니다. poll(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다. size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다. peek(): 큐에 ..

💡 스택 데이터를 순서대로 쌓는 자료구조 먼저 들어간 데이터는 제일 나중에 나오는 LIFO 구조 데이터 삽입은 Push, 데이터 추출은 Pop이다. 데이터를 하나씩 넣고 뺄수 있다. 입출력 방향이 한곳이다. 구현 push(): 스택에 데이터를 추가할 수 있어야 합니다. pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다. size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다. peek(): 가장 나중에 추가된 데이터를 리턴해야 합니다. show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다. clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제합니다. remove(): 삭제와 삭제된 요소 반환이 동시에 됩니다...

💡 이중 연결 리스트 & 원형 연결 리스트 전에 만들었던 단순 연결 리스트에 previous 필드를 추가한다 즉, 이중 연결 리스트의 Node 구성은 next & prev & data 3개의 요소가 들어감 원형 연결 리스트(Circular Linked List) tail.next가 null이 아닌 연결 리스트의 노드를 가리키는 연결리스트 단순 연결 리스트의 단점 tail 포인터가 있더라도 removeLast()를 하기 위한 시간복잡도는 O(n)으로 마지막 요소부터 앞으로 넘어갈 방법이 없으므로 비효율적이다. 무조건 처음부터 시작해서 마지막의 2번째 요소까지 와야 마지막 요소를 삭제 할 수 있었다 왼쪽 - 이중 연결 리스트 & 오른쪽 - 원형 연결 리스트 이중 연결 리스트 previous 필드를 추가함으로..

💡 LinkedList 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조 자료구조를 사용할때 항상 경계 조건을 생각하기 배열과의 차이점 배열도 순서대로 여러 데이터를 저장할때 사용한다는 공통점이 있지만 크기 조정이 어렵지만, LinkedList는 항상 맞는 크기로 만들어지도록 설계되어 많은양의 데이터나 순차적 데이터를 사용할때 적합함 LinkedList의 기본 구조 연결 리스트의 기본구조에는 노드가 있다 노드에는 두가지 정보가 들어있다 next - 다음 노드를 가리키는 포인터 data - 노드에 넣는 데이터를 가리키는 포인터 노드를 정의하는 법 public class LinkedList { private Node head; private int currentSize; /** currentSize 변..