노드(Node)
노드(Node) : 크기가 동적인 자료구조로, 자료구조를 구성하는 요소
노드(Node)는 데이터가 담기는 데이터 공간과 다음데이터를 가리키는 주소값(포인터(pointer))이 담기는 포인터공간으로 구성되어 있다.
포인터공간에 담겨있는 포인터(pointer)는 노드 안에서 이전 노드나 다음 노드와의 연결정보를 가지고 있으며 마지막 노드의 포인터는 null이다.
연결리스트(Linked List)
연결리스트(Linked List) : 노드의 연결로 이루어진 자료구조이다.
가장 앞에 있는 노드를 head, 가장 뒤에 있는 노드를 tail이라고 한다. 이 때, head는 데이터를 가지지 않고 가장 앞에 있는 노드의 주소값만 가지고 있다. tail은 다음노드가 없는(다음 노드의 주소값이 null임)노드이다.
연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖는다. 추가와 삭제에 대해 O(n) (선형시간)의 복잡도를 갖는 배열과는 다르다.
다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 가지고 있지 않기 때문에, 특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훑어야 하고, 이것은 O(n) (선형 시간)의 복잡도를 필요로 한다.
연결리스트(Linked List)에는 여러 종류가 있는데
단일 연결 리스트(Singly-Linked List) : 각 노드에 데이터 공간과 1개의 포인터 공간이 있다. 각 노드의 포인터는 다음 노드의 데이터를 가리킨다. 가장 뒤에 있는 노드인 tail의 포인터는 null을 가리킨다.
단일 연결 리스트구조는 Head노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 뒤쪽 자료들이 유실된다.
단일 연결 리스트는 Tail노드로는 리스트 순회가 불가능하다.
- 도미노
이중 연결 리스트(Doubly-Linked List) : 단일 연결 리스트(Singly-Linked List)와 비슷하지만 포인터 공간이 2개가 있고, 각 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 가장 뒤에 있는 노드인 tail의 뒤의 노드를 가리키는 포인터는 null을 가리킨다.
이중 연결 리스트는 단일 연결 리스트보다는 손상에 강한 편이다. Head와 Tail노드를 갖고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 게 가능하다.
- 음악 재생 리스트(반복 기능이 없는)
원형 연결 리스트 (Circular Linked List) : 단일 연결 리스트(Singly-Linked List)에서 tail의 포인터가 null을 가리키지 않고 head를 가리키는 연결리스트 종류이다.
- 반복기능이 있는 음악 재생 리스트
해시테이블(Hash Table) (Hash Map이라고도 함)
해시테이블(Hash Table)은 키,값 쌍을 저장하고 있는 자료구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환한다. 그래서 해시테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 메모리를 유지한다. 즉, 해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조이다. 이 때, 데이터가 저장되는 공간을 버킷(bucket) 또는 슬롯(slot)이라고한다.
해시함수의 특징
가지고있는 배열의 길이 안에서만 값이 나와야된다
언제든지 일정한 값이 나와야 된다.
어떠한 저장(기억)도 할 수 없다.
해시테이블은 25%에서 75%일때 가장 효율적이다.
자료가 75%이상이 되려고 할 때 스토리지의 사이즈를 늘리고
25%미만이 되려고 할 때 스토리지의 사이즈를 줄이면 효율적으로 관리할 수 있다.
해시테이블 사이즈를 늘릴 때 해시테이블을 키우고 나서 해싱을 다시 해줘야 한다.
