자료구조

LinkedList를 구현하는 방법에는 여러가지가 있는데 하나씩 살펴보겠습니다. 연결 리스트 종류 단일 연결 리스트 (Single Linked List) 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성됩니다. 마지막 노드는 null 을 가리킵니다. 단방향이기 때문에 주로 앞에서 부터 순회합니다. 구현이 간단하지만 뒤에서 앞으로의 이동은 불가능 합니다. 이중 연결 리스트 (Double Linked List) 각 노드가 데이터와 이전, 다음 노드를 가리키는 포인터로 구성됩니다. 앞, 뒤로의 이동이 자유롭게 가능하며 역순회도 간단합니다. 두개의 포인터를 갖기 때문에 메모리 공간이 더 필요합니다. 데이터 추가나 삭제시에 이전 노드와 다음 노드 모두의 참조를 업데이트하는 추가 작업이 필요합니다. 원형 연결..

해시함수(hash function) 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터 값을 key, 매핑 이후 데이터의 값을 hash value , 매핑하는 과정을 hashing 이라고 합니다. 해시충돌(hash collision) 해시함수는 보통 키값의 개수보다 적은 해쉬값을 관리하므로 서로 다른 두 개 이상의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다. 현재까지 알려진 거의 모든 해시함수는 해시충돌을 일으킨다고 합니다. 이때문에 해시 충돌 자체를 줄이거나, 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 해야 합니다. 해시테이블의 장점 해시테이블은 매우 효율적인 데이터 관리 도구입니다...