정렬
데이터를 순서대로 나열하는 방법이다. 이진 탐색이 가능하며 데이터 탐색이 효율적이다.
ex)버블정렬, 선택정렬, 삽입정렬, 병합정렬
스택
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조 바구니에 물건을 넣고 뺄 때 입구에서만 가능한 것
후입 선출 Last In First Out LIFO라고 한다
큐
한쪽 끝으로 자료를 넣고 다른 한쪽 끝으로는 자료를 뺄 수 있는 구조. 선입선출 First In First Out FIFO
enqueue(data) : 맨 뒤에 데이터 추가하기 dequeue() : 맨 앞의 데이터 뽑기 peek() : 맨 앞의 데이터 보기 isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
이 때, 스택과 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야 하므로, self.head 와 self.tail 을 가지고 시작
해쉬 테이블(Hash Table) "키"와 "데이터"를 저장해 즉각적으로 데이터를 받아오고 업데이트 하고싶을 때 사용하는 자료구조.
해쉬 함수(Hash Function) 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.
해쉬 테이블의 내부구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장한다.
해쉬 값이나 인덱스가 중복되어 충돌이 일어난다면 체이닝과 개방주소법으로 해결이 가능하다.
개방 주소법 : 배열의 다음 남는 공간에 넣는 개방주소법
chaining : 각 배열에 링크드 리스트를 연결한 것