class HashTable { constructor() { this.storageLimit = 10; // 해시테이블의 용량 한계 설정 this.table = new Array(this.storageLimit); // 정해진 용량 크기로 해시 테이블을 배열로 만듬 } // 키, 인덱스, 값 // key -> index (키를 가지고 인덱스로 변환해주는 해시 함수) Hash(key) { let hash = 0; for (let i = 0; i

해시 - (1) 개념 해시란 무엇인가? 데이터를 관리하고 유지하는 자료구조 리소스 < 속도 (리소스를 포기하고 속도를 취한 자료구조) 키(key)는 해시 함수(Hash function)을 통해 해시(hash) = 배열의 인덱스 로 변경이 되고, 해시 = 배열의 인덱스는 값(value)와 매칭되어 저장소(storage)에 저장이 된다 Hash Table의 요소 키(key) : 고유한 값, 해시의 input 해시 함수(Hash function) : 키를 해시로 바꿔주는 역할 해시(Hash) : 해시 함수의 결과물, 저장소에서 값과 매칭되어 저장된다 = 배열의 인덱스 값(value) : 저장소에 최종 저장되는 값 해시 Big O Notation 각 조회의 평균 시간은 테이블에 저장된 요소 수와 관련이 없다. ..

딕셔너리(맵) 딕셔너리(맵) : 데이터를 [키,값] 쌍으로 담아두는 자료구조 (키와 값의 쌍으로 이루어진 컬렉션) 키: 원소를 찾기 위한 식별자 집합의 Set 클래스와 마찬가지로 ES6에는 Map 클래스가 내장되어 있음 Map 객체와 객체의 차이 Map 객체는 객체와 유사하지만 다음과 같은 차이가 있음 구분 객체 Map 객체 키로 사용할 수 있는 값 문자열 또는 심벌 값 객체를 포함한 모든 값 이터러블 X O 요소 개수 확인 object.keys(obj).length map.size 1. Map 객체의 생성 - new Map() / new Map([[키1,값1], [키2,값2]]) Map 객체는 Map 생성자 함수로 생성한다. Map 생성자 함수에 인수를 전달하지 않으면 빈 Map 객체가 생성된다. co..

집합(Set 클래스) 개념 집합이란 정렬되지 않은 컬렉션 원소는 반복되지 않음(중복되는 원소가 없음) 수학에 나오는 유한 집합의 개념을 컴퓨터 과학에 적용한 것 수학 시간에 배웠던 집합 집합 - 유일하게 구분되는 원소의 모임 원소는 중괄호 { }로 둘러싼다 예) 자연수의 집합은 1보다 같거나 큰 정수로 구성된다. ( N = {1,2,3,4,5,6,...} ) 공집합 (널집합) - 원솨 하나도 없는 집합 예) 24와 29 사이의 소수의 집합은 공집합임(24와 29 중에는 소수가 없기 때문, 소수: 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수) 공집합은 {} 으로 표시 **즉, 집합은 정렬 개념이 없는 원소가 중복되지 않는 배열이라고 볼 수 있음 집합 만들기(Set 객체의 생성) 자바스크립트에는 ..

연결 리스트 - (2) doubly linked list 이중 연결 리스트 단순 연결 리스트(single linked list)는 다음 노드의 연결 정보만 가지고 있었다면 이중 연결 리스트(doubly linked list)는 다음 노드와 이전 노드, 2개의 연결 정보를 가지고 있음 장점 이중 연결 리스트에서는 처음에서 끝/끝에서 처음, 양방향으로 리스트 순회가 가능 한 방향으로만 링크된 단순 연결 리스트는 순회 시 원소를 찾지 못하면 다시 맨 처음으로 돌아가야 했었으므로 이런 점이 이중 연결 리스트의 장점이라고 할 수 있음 단점 메모리를 더 많이 사용한다 좀 더 복잡하다 단순 연결 리스트와 비교해서 이중 연결 리스트에 추가해야 할 부분 class Node2{ constructor(element){ th..

연결 리스트 배열(일종의 리스트) 장점: 구현하기가 쉽고 사용하기 편하다. 배열의 원소에 접근하려면 대괄호에 인덱스만 넣어주면 된다. 단점 크기가 고정되어 있다 배열의 처음이나 중간에서 원소를 추가/삭제 하려면 다른 원소까지 옮겨야 하므로 번거롭다 연결리스트(Linked List) 연결리스트는 일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다 각 원소는 원소 자신과 다음 원소를 가리키는 참조 정보(포인터,링크 라고도함)가 포함된 노드로 구성된다 장점: 원소 추가 삭제 시 다른 원소들을 이동하지 않아도 된다(포인터 덕분) 단점: 배열은 특정 원소에 인덱스로 바로 접근할 수 있는 반면 연결 리스트에서는 원소를 찾을 때까지 처음(헤드,head)부터 루프를 반복해야함 연결..