💡 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 필드를 추가함으로..