Data Structure - Linked List & Hash Table

Linked List (연결 리스트)

• 크기가 동적인 자료구조
• 자료구조를 구성하는 요소 => 이것을 노드(Node)라고 부름
• 노드의 연결로 이루어진 자료 구조
• 연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 가짐
• 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다름
• 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 가지지 않음
• 연결 리스트에서 검색하고자 할 때 전체 연결 리스트를 훑어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 함

Linked List method

• addToTail(value) : 주어진 값을 연결 리스트의 끝에 추가
• remove(value) : 주어진 값을 찾아서 연결을 해제(삭제)
• getNodeAt(index) : 주어진 인덱스 노드를 찾아서 반환, 노드를 반환(주의), 인덱스 노드가 없다면 undefined 반환
• contains(value) : 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환
• indexOf(value) : 주어진 값의 인덱스를 반환, 없을 경우 -1을 반환

 

단일 연결 리스트

각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

자료출처 : 위키백과 (단일 연결 리스트)

 

이중 연결 리스트

단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

자료출처 : 위키백과 (이중 연결 리스트)

 

원형 연결 리스트

일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

자료출처 : 위키백과 (원형 연결 리스트)

 

Hash Table (해시 맵)

• 해시 테이블은 키, 값 쌍을 지정하고 있는 자료 구조
• 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록,
• 키를 "해시 함수(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환
• 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지
• 데이터가 저장되는 곳 : buckets

Hash Table method

• insert(key, value) : 주어진 키와 값을 저장, 해당 키가 저장되어 있다면 값을 덮어씌움
• retrieve(key) : 주어진 키에 해당하는 값을 반환, 없다면 undefined 반환
• remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환, 없다면 undefined 반환
• _resize(newLimit) : 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수, 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 함

자료출처 : 위키백과 (해시 테이블)

 

 

사이트 참조 : 위키백과 - 연결리스트

연결 리스트 - 위키백과, 우리 모두의 백과사전

사이트 참조 : 위키백과 - 해시 테이블

해시 테이블 - 위키백과, 우리 모두의 백과사전