자료구조 (4) 썸네일형 리스트형 [자료 구조] 해시 테이블(Hash Table) key-value 쌍의 데이터를 입력받아 빠른 탐색을 가능하게 하는 자료구조이다. 각 해시 테이블의 hash function에 key 값을 집어넣어 얻은 해시값을 위치로 key-value 데이터 쌍을 저장합니다. key 에 해당하는 value 값을 찾을 때 다른 주소의 탐색없이 Hash function에 key 값을 넣은 결과값의 위치만 확인하면 되기에 빠른 탐색이 가능하다. 여기서 value값을 저장하는 위치를 버킷(슬롯)이라고 한다. Hash Function Hash Function은 각 key값에 해당하는 고유한 인덱스 값을 얻기 위해 존재한다. Division Method Index = key % 테이블의 크기 Digit Folding Key의 각 자리 문자를 ASCII 코드로 바꾼 값을 합한 값.. [자료구조] 큐(Queue) FIFO(First In First Out), LILO(Last In Last Out) 즉 선입선출의 규칙를 가지고 있는 자료구조이다. FILO(First In Last Out) 의 규칙을 가지고 있는 스택(Stack) 과는 반대의 성격을 가지고 있다. 데이터의 삽입, 삭제가 빨라서 데이터의 입출력이 자주 일어나는 경우 사용한다. 프린터 작업 처리 , CPU task scheduling, BFS, Cache 용어 Front (Head) : 논리적으로 가장 앞에 있는 데이터의 위치, 데이터를 Dequeue 할 수 있는 위치이다. Rear (Tail) : 논리적으로 마지막에 있는 데이터의 위치, 데이터를 Enqueue 할 수 있는 위치이다. Enqueue : Queue에 데이터를 삽입. Rear에 데이터를 .. [자료구조] LinkedList vs ArrayList LinkedList와 ArrayList는 같은 List라는 이름을 달고 있지만 data 구조나 장단점에서 확연한 차이를 보인다. LinkedList에 대해 정리해보며 ArrayList와는 어떤 차이가 있는지 정리해보았다. LinkedList 각 노드가 데이터와 다음 노드의 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 데이터가 물리적, 논리적으로 연결되어 있는 배열 리스트와는 다르게 연결 리스트는 데이터가 논리적으로만 연결 되어있다. ArrayList https://mson-it.tistory.com/3 [자료구조] Array vs ArrayList Array 미리 할당된 크기 내에서 연관된 data를 메모리와 index가 연속적이고 순차적으로 저장하는 자료구조이다. .. [자료구조] Array vs ArrayList Array 미리 할당된 크기 내에서 연관된 data를 메모리와 index가 연속적이고 순차적으로 저장하는 자료구조이다. ArrayList 연관된 data를 메모리와 index가 연속적이고 순차적으로 저장한다는 점에서는 Array와 비슷하지만 미리 할당된 크기보다 더 큰 data가 들어왔을 경우 capacity를 늘린다. Performance 기본적인 구조가 비슷하기 때문에 두 자료구조가 비슷한 시간 복잡도를 가진다. Search O(n) Append O(1) Insertion (append가 아닌) O(n) - 해당 index를 기준으로 뒤에 있는 index의 data를 한칸씩 뒤로 밀어야한다 Delete(맨 끝) O(1) Delete O(n) - Insertion 과 같은 이유이다. Access O(1.. 이전 1 다음
