“Linked List, Hash Table”
Data Structure
1. Linked List
연결리스트 : : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
연결리스트는 각 노드들의 배열로 이루어져있고, 노드는 데이터와 포인터로 이루어져 있으며, 각각의 노드의 포인터는 다음 노드를 가리키고 있다.
연결리스트의 단점:
연결리스트를 배열과 비교를 했을 때, 특정 데이터를 검색하는데 시간이 오래걸린다는 단점이 있다. 그 이유는 배열은 각 공간의 주소가 인덱스로 정해져있기 때문에, 어떤 값의 주소만 알고 있다면 찾는 것은 쉽다.
하지만, 연결리스트는 값들이 링크로 연결되어 있고, 각 노드들은 다음 노드의 링크만을 가지고 있기 때문에 어떠한 값을 찾기 위해서는 계속해서 링크를 타고 가야한다. 따라서 1개를 찾더라도 모든 링크를 다 돌 수도 있기 때문에 단점이 존재한다.연결리스트의 장점:
반면에, 중간에 삽입 또는 삭제를 할 경우에는 배열보다 연결리스트의 방법이 편하게 된다.
배열의 경우 중간에 값을 추가하거나 삭제할 경우, 추가하거나 삭제한 값으로부터 모든 인덱스들을 재위치 시켜줘야하지만
연결리스트의 경우에는 원하는 부분에 노드를 삽입한 뒤에, 전에 노드를 삽입한 노드에 연결시키고, 삽입한 노드를 그 다음 노드에 연결 시키기만 하면 된다.
결론: 중간에 삽입 또는 삭제를 할 경우에는 연결리스트를, 특정 값을 찾는 것은 배열을 사용하는 것이 유리할 것이라고 생각된다.
Linked List
Property
- head : 리스트의 첫번째 노드
- tail : 리스트의 마지막 노드
- next: 마지막 노드를 가리키는 next pointer
Methods
- addToTail : 마지막 번째 노드에 데이터를 삽입
removeHead : 첫 번째 노드를 삭제
contains : 연결 리스트가 주어진 값을 포함하고 있는지 확인
2. Hash Table
해시테이블은 연관배열 구조를 이용하여 키(key) 에 결과 값(value)을 저장하는 자료구조이다.
연관배열 구조란?
- 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조로 키(key)의 값을 이용하여 값(value)을 알아낼 수 도 있다.
연관배열 구조는 다음의 명령을 지원한다.
- 키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장하는 명령
- 키(key)가 주어졌을 때, 연관되는 값(value)을 얻는 명령
- 키(key)와 새로운 값(value)이 주어졌을 때, 기존 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령
- 키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하는 명령
해시 테이블의 구성
해시테이블은 Key, Hash Function, Hasth, value, Bucket 으로 구성 되어있다.
key 는 hash function 을 통해 hash 로 변경되고, hash는 value 와 bucket에 저장된다.
key : 고유한 값으로 해시함수의 input이 된다. bucket에 저장이 되면 길이만큼 저장소를 구성해야하기 때문에, 해시함수를 통해 값을 바꾼 뒤 저장하여 공간의 효율성을 가져올 수 있다.
Hash Function : 키를 해시로 바꿔주는 역할을 한다. 하지만 서로 다른 키가 같은 해시가 되는 경우를 해시충돌 (Collision)이라고 하는데, 해시 충돌을 최대한 줄이는 함수를 만드는 것이 중요하다.
Hash : 해시함수의 결과로, 저장소 (bucket)에서 값(value)과 매칭되어 저장된다.
Value: bucket에 최종적으로 저장되는 값으로 키와 매칭된다.
Bucket : value 가 저장되는 곳으로, 각 bucket은 hash 로 접근한다.
이어서 작성할것
: collision , property, method, implement hash function
