Linked List
특징
노드를 만듬
노드 안에는 데이터필드
링크로 노드가 어디있는지 알려줌
노드 안에는 데이터와 링크가 있음
제일 처음은 해드
제일 마지막은 테일
링크는 다음 데이터를 가리킴
제일 마지막 테일의 링크는 null을 가리킴
싱글 링크드 리스트
링크가 한개밖에 없으면
한방향으로 이동하는 것
돌아올 수 없음
더블링크드 리스트
링크를 한 개 더 추가
앞으로 갈 수 있고, 뒤로도 갈 수 있는 것
환영 링크드 리스트
계속 도는 링크
인풋사이즈를 모를떄 리스트가 어레이보다 좋음
링크 하나당 4byte를 차지
노드 10개면 40byte
노드 10개이고, 더블링크드면 80byte 임
한개씩 다 떙겨줘야함
중간 데이터 삭제는 리스트가 더 좋음
어레이 vs 리스트
메모리 할당 효율은 리스트
데이터 저장값은 어레이
중간값 추가/삭제는 리스트
리스트가 어레이보다 링크때문에 메모리를 더 사용
어떤 자료를 찾고 싶을때 링크마다 물어봐야함
어레이는 한번에 찾을 수 있음
어레이는 탐색 /정렬에 유리
리스트는 무족건 연속적으로 할당되지는 않음
리스트는 계속 추가를 유연하게가능
삭제하고싶을 때는 1번의 연산으로 연결만 끊어주면 끝
따라서 추가와 삭제가 용이하다
single linked list
hash Table
특징
데이터를 관리/유지 자료구조
리소스 < 속도
원리
데이터를 해시함수를 거쳐서 인덱스와 값을 가짐
해시함수는 특정 규칙을 담음
해싱충돌 처리방법
체이닝
같은 인덱스에 리스트로 이어버리는것
linear probing
빈자리에 넣는 것
resizing
배열의 사이즈를 재지정하는 것
검색하는 것의 키값을 입력받아서 헤쉬코드를 받아서
배열의 인덱스로 환산해서 배열의 값으로 접근하는 것
키값이 얼마나 큰지 상관없이 동일한 헤쉬코드를 만들어준다.
블록체인에서도 사용
검색속도가 가장 빠름
검색 시간이 1만큼 걸림
헤쉬코드는 정수로 만듬
헤쉬코드의 갯수가 배열의 인덱스 갯수임
바로 접근할 수 있는 것
두 개 이상의 값에 하나의 키를 사용할 수 없다
새로운 키가 들어오면 새로운 키가 이전의 키 대신 사용한다
(SHA-256은 일방향 함수이다. 해시는 일방향이 아니다)