자료구조
8편
LinkedList 는 손을 잡고 선 줄이다
칸이 붙어 있지 않고 각자 다음 사람의 위치를 들고 있습니다. 끼워 넣기는 싸지고 번호로 찾기는 비싸집니다.
넣고 빼는 순서가 규칙이다
어느 것을 꺼낼지 우리가 고르지 않습니다. 나중에 넣은 것부터 나오거나, 먼저 넣은 것부터 나옵니다.
해시 테이블은 자리를 계산해서 정한다
Dictionary 와 HashSet 이 곧장 찾는 이유입니다. 해시 코드를 버킷 개수로 나눈 나머지가 자리이고, 그 버킷 개수는 언제나 소수입니다. 겹치면 어떻게 되고 줄은 어디까지 길어지는지까지 봅니다.
HashSet 은 중복을 받지 않는다
이미 있는지 확인하는 일을 List 로 하면 전부 훑습니다. Dictionary 에서 값을 떼고 키만 남긴 것이 HashSet 입니다.
Dictionary 는 번호 대신 이름으로 찾는다
이름을 숫자로 바꿔서 자리를 계산합니다. 그래서 몇 개가 들어 있든 찾는 시간이 거의 같습니다.
List 는 칸이 모자라면 알아서 늘린다
속은 그냥 배열입니다. 꽉 차면 더 큰 배열을 만들어 옮기는 일을 대신 해 줄 뿐입니다.
2차원 배열은 행과 열로 찾는다
격자로 보이지만 메모리에는 여전히 한 줄로 놓여 있습니다. 번호 두 개가 한 자리를 가리키는 방식입니다.
배열은 번호가 붙은 칸 한 줄이다
값 하나에 변수 하나씩 만들면 백 개를 다룰 수 없습니다. 배열은 이름 하나에 칸을 여러 개 붙여 번호로 꺼냅니다.