연결리스트(Linked List)
연결리스트(Linked List)란 각 데이터들을 포인터로 연결하여 관리하는 자료구조다.
연결리스트는 각 데이터를 저장하는 영역과 데이터가 저장되있는 영역을 연결해주는 포인터영역으로 구성되어 있다.
위의 그림은 연결리스트의 기본 구조입니다.
임의의 데이터를 데이터1과 데이터2 사이에 삽입시키고자 하면 데이터1의 포인터를 새로운 데이터영역을 연결하고 새로운데이터의 포인터가 데이터2를 연결하면 됩니다.
반대로 데이터2를 삭제하고 싶을경우 데이터2를 연결하고 있는 포인터를 연결하지 않으면 됩니다.
데이터1의 포인터가 데이터3을 연결하면 데이터2는 아무것도 연결이 되어있지 않아 삭제와 같은 효과를 가지게 됩니다.
+마지막 노드의 포인터영역은 NULL값이 되어야 합니다
Hash Table
데이터들은 해시함수(데이터를 연산하는 과정)를 거쳐서 규칙성을 가지고 해시테이블에 넣어진다
해시테이블은 (인덱스,키)와 (해시값, Value)로 구성되어 있고,
인덱싱 된 값을 버켓이라고 하고 버켓에 들어가는 값은 엔트리.
데이터->해시함수->해시 테이블 이 모든과정을 해싱이라고 한다.
해시의 장점 = 빠른 접근속도
해시의 단점 = 충돌
충돌이 발생했을 때 대처하는법
체이닝 - 리스트를 이용해 인덱스값에 자리가 있을 때 연결해줌.
Linear Probing(선형탐색) - 다음버켓자리에 넣어버림
Resizing - 테이블의 크기를 늘린다음에 다시 데이터들을 해시함수를 거쳐서 재정렬을 한다.
