자료구조 및 알고리즘23 [자료구조] 자바에서의 해쉬 테이블과 충돌 문제 해결 해쉬 테이블 Hash Table : 키(Key) 에 데이터(value) 를 저장하는 데이터 구조(데이터베이스와 비슷한 구조이다.) - key 를 통해 즉시 데이터를 받아올 수 있으므로 탐색 속도가 빠르다. - 자바의 경우 HashMap 클래스를 통해 객체를 생성할 수 있다. 용어 해쉬(Hash) : 임의 값을 고정 길이로 변환하는것 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function) : key 에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) : key 를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key.. 2021. 11. 25. [자료구조] - 자바로 연결 리스트를 구현해보자. #2 이중 연결 리스트 기존 연결 리스트 구조의 단점 - 연결 리스트의 길이가 길어질 경우 원하는 데이터를 찾을 때 최악의 경우 연결 리스트의 최대 길이만큼 탐색해야 한다. - 연결 리스트는 데이터를 헤더에서 부터 순차 탐색으로 찾기 때문이다. * 이중 연결 리스트의 장점 - 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능하다.(자바의 경우 ListIterator 클래스로 구현가능) - 데이터를 탐색 할 때 찾고자 하는 데이터가 리스트의 후반부 쯤에 있을 경우, 리스트의 가장 뒤에서 부터 앞으로 탐색하면 기존의 리스트 보다 더 빨리 데이터를 찾을 수 있다. 이중 연결 리스트는 기존의 연결 리스트가 자신의 다음에 있는 노드의 주소를 가지고 있는것과 달리 자신의 앞에 있는 노드의 주소 또한 가지고 있으.. 2021. 11. 25. [자료구조] - 자바로 연결 리스트를 구현해보자. #1 연결 리스트(Linked List) 구조 순차적으로 연결된 공간에 데이터를 나열하는 배열과는 달리, 연결 리스트의 경우 메모리상에서 떨어진 곳에 위치한 데이터를 주소 참조를 통해 연결하여 관리할 수 있는 데이터 구조이다. - 데이터의 추가, 삭제의 경우 배열보다 유리하다. - 데이터 탐색의 경우 배열보다 불리하다. - 배열의 경우 인덱스 번호를 통해 찾고자 하는 데이터에 즉시 접근할 수 있으나, 연결 리스트의 경우 헤더에서 부터 순차적으로 탐색하여 데이터를 찾아야 한다. 자바의 경우 각 객체간의 참조를 통해 연결 리스트를 구현할 수 있다. * 연결 리스트의 경우 다음과 같은 구조로 이루어져 있다. - 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터) 로 구성 - 포인터(Pointer) : 각 .. 2021. 11. 24. 이전 1 ··· 3 4 5 6 다음
