Linked List
: 크기가 동적인 자료구조다. 연결 리스트는 배열 처럼 직선적으로 요소들을 갖는다. 그러나 여기서 요소를 요소라고 부르지않고 '노드(Node)'라고 부른다. 다시 말해 이 노드들이 연결되어 이루어진 자료구조인다. 연결 리스트에는 단일 연결 리스트(Singly-Linked List), 이중 연결 리스트(Doubly-Linked List)등의 종류가 있습니다.
연결 리스트의 특징
- 인덱스를 갖지 않는다.
- linked list 만의 메소드를 가지고있다 (addToTail,remove etc)
- 이중 연결 리스트이지 않는 이상 뒤쪽 노드를 알 수 없다.
- 배열에 비해 추가 및 삭제가 빠르다.
- 인덱스를 가지고 있지않아서, 특정 노드를 빠르게 찾기 힘들다.
- 연결된 노드가 끊어지면, 다음 노드를 찾을 수 없다.
- 끊어진 노드는 가비지 컬렉션이 그 노드를 제거한다.
위 의 그림처럼, 가장 맨 앞의 노드를 head라고 부르고, 마지막 노드를 tail 이라고 부른다.
링크드 리스트를 UI로 잘 볼 수 있는곳( Visualgo.net )
Hash table (hash map)
: 해쉬 테이블은 두가지의 데이터 밸류를 쌍으로 같이 저장하는 구조의 자료구조다. 그중 하나는 key이고 다른하나는 value이다. 객체과 비슷한 느낌을 가지고있다. 그러나 객체와 조금 다른점은 hashing 이라는 프로세스이다.
hashing 이란? 이 자료구조는 해쉬 함수를 가지고있다. 해쉬 함수는 input으로 들어오는 key를 해쉬 알고리즘에 따라 변경하여, 변경된 그 값을 키로 가지고, 밸류를 저장한다. 이때 해쉬 함수를 통해 mapping되어 들어오는 데이터값을 hash value라고 부르고, 이 전체 프로세스를 Hashing 이라고 한다.
해쉬 테이블 용어
- 튜플(tuple) : 해쉬 테이블에서 key와 value의 한쌍을 튜플이라고 부른다.
- 스토리지(storage) : 튜플들이 모여 데이터를 저장하고 있는 배열 형태의 테이블을 스토리지라고 칭한다.
- 버켓(bucket) : 튜플이 저장되어있는 장소(배열에서는 인덱스 느낌)를 버켓이라고하고, 버켓이 담고 있는 데이터들을 튜플이라고 칭한다 .
hash table을 자료구조에서 조심해야 할 점.
- collision(충돌) : 하나의 키에 두개 이상의 밸류가 들어갈때 충돌이 일어난다. 이렇게 충돌이 일어날때, 두가지 방법으로 충돌을 해결할 수 있다.
-
Chaining : 튜플들을 linked list처럼 사용하는것이다.
-
Open addressing : 1번째 버켓에 한 튜플이 있고, 새로운 튜플이 1번째 버켓으로 들어갈때, 1번으로 버켓으로 넣지않고, 옆에 비어있는 버컷으로 배치되게하는것. 이때, 튜플이 스토리지 길이의 75% 이상 채워지면 스토리지를 두배로 늘려주고, 25%이하면 스토리지 길이를 반으로 줄인다.
