前端必須要掌握常見的數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)這招，讓你對(duì)開發(fā)中的數(shù)據(jù)結(jié)構(gòu)更加清晰！
一.隊(duì)列
像排隊(duì)一樣，隊(duì)列就是先進(jìn)先出，排隊(duì)入場(chǎng)！
image
class Queue {
constructor() {
this.arr = []
}
enqueue(element){ // 入隊(duì)列
this.arr.push(element)
}
dequeue(){ // 出隊(duì)列
return this.items.shift()
}
}
二.棧
像拿起堆放的柴火一樣，棧就是先進(jìn)后出，就是離場(chǎng)時(shí)后進(jìn)的人先出！
image
class Stack {
constructor(){
this.arr = [];
}
push(element){ // 入棧
this.arr.push(element);
}
pop() { // 出棧
return this.items.pop();
}
}
三.鏈表
image
鏈表讓我們刪除數(shù)據(jù)和新增數(shù)據(jù)更加方便！
head指針指向第一個(gè)存入的元素節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有next屬性指向一下一個(gè)元素節(jié)點(diǎn)，最后一個(gè)元素的指針指向null
創(chuàng)建一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)非常簡(jiǎn)單
class Node {
constructor(element){
this.element = element; // 每個(gè)節(jié)點(diǎn)保存的內(nèi)容
this.next = null; // 保存的指針，指向下一個(gè)節(jié)點(diǎn)
}
}
構(gòu)建鏈表
class LinkList {
constructor(){
this.head = null; // 表頭 默認(rèn)指向第一個(gè)節(jié)點(diǎn)，沒(méi)有為null
this.length = 0;
}
append(element){
// 追加節(jié)點(diǎn)
const node = new Node(element);
if(this.head == null){
this.head = node; // 第一個(gè)節(jié)點(diǎn)就是表頭
}else{
let current = this.head;
// 從第一個(gè)節(jié)點(diǎn)查找到最后一個(gè)節(jié)點(diǎn)
while(current.next){
current = current.next;
}
current.next = node; // 找到最后一個(gè)節(jié)點(diǎn)添加next指向新增節(jié)點(diǎn)
}
this.length++; // 每增加一個(gè)長(zhǎng)度
}
}
使用鏈表，不難看出鏈表的特點(diǎn)就是通過(guò)next來(lái)指向下一個(gè)節(jié)點(diǎn)（像鏈條一樣）
const ll = new LinkList();
ll.append(1);
ll.append(2);
console.log(ll); // head: Node { element: 1, next: Node { element: 2, next: null } }
實(shí)現(xiàn)鏈表的插入
insert(position,element){
// 插入的時(shí)候判斷插入的位置
if(position>=0 && position <=this.length){
const node = new Node(element); // 創(chuàng)建一個(gè)節(jié)點(diǎn)
if(position === 0){ // 如果位置是0
node.next = this.head; // 那么就讓當(dāng)前節(jié)點(diǎn)變成頭
this.head = node;
}else{
let current = this.head; // 獲取頭節(jié)點(diǎn)查找位置
let previous = null;
let index = 0;
while(index++ < position){ // 查找到節(jié)點(diǎn)位置
previous = current;
current = current.next;
}
node.next = current; // 讓當(dāng)前節(jié)點(diǎn)next是剛才找到的節(jié)點(diǎn)
previous.next = node; // 他的上一個(gè)節(jié)點(diǎn)的next是當(dāng)前節(jié)點(diǎn)
}
this.length++;
}
}
實(shí)現(xiàn)鏈表的刪除
removeAt(position){
if(position > -1 && position < this.length){
if(position ==0){ // 如果是第一個(gè)直接改變指針
this.head = this.head.next
}else{
let index = 0;
let previous = null;
let current = this.head;
while(index++ < position){ // 找到要?jiǎng)h除的這一項(xiàng)，直接讓上一個(gè)指針指向下一個(gè)人
previous = current;
current = current.next
}
previous.next = current.next; // 上一個(gè)next直接指向下一個(gè)next
}
this.length--;
}
}
更新鏈表中的內(nèi)容
update(position,element) {
if (position >= 0 && position < this.length) {
if (position === 0) {
// 根位置 直接更改跟的內(nèi)容即可
this.head.element = element
}else{
let index = 0;
// 查找到要修改的項(xiàng)來(lái)更新
let current = this.head;
while(index++ < position){
current = current.next;
}
current.element = element;
}
}
}
四.集合
ES6已經(jīng)為我們提供了Set的api，但是在某些時(shí)候(瀏覽器不支持的情況下),我們還是需要自己來(lái)實(shí)現(xiàn)Set的
class Set{
constructor(){
this.items = {};
}
has(value){ // 判斷
return this.items.hasOwnProperty(value);
}
add(value){ // 像集合中添加
if(!this.has(value)){
this.items[value] = value;
}
}
remove(value){ // 刪除集合中的某一項(xiàng)
if(this.has(value)){
delete this.items[value];
}
}
}
集合，常見的方法有：交集、并集、差集
五.hash表
image
特點(diǎn)是查找速度快，但是存儲(chǔ)量需要手動(dòng)擴(kuò)展
class HashTable{
constructor(){
this.table = [];
}
calcuteHash(key){ // 通過(guò)put的key 計(jì)算hash戳，存到數(shù)組中
let hash = 0;
for(let s of key){
hash += s.charCodeAt();
}
return hash % 100; // 只能存放100個(gè)
}
get(key){ // 從hash表中取出值
let hash = this.calcuteHash(key);
return this.table[hash]
}
put(key,value){ // 像hash表中存入
let hash = this.calcuteHash(key);
this.table[hash] = value;
}
}
let hash = new HashTable();
hash.put('abc',1);
console.log(hash.get('abc'));
六.樹
叫做“樹”是因?yàn)樗雌饋?lái)像一棵倒掛的樹，也就是說(shuō)它是根朝上，而葉朝下的。
image
前端最常考察的就是二叉樹！
二叉樹: 樹中的節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)
二叉查找樹:
若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
若右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值
class Node {
constructor(key){
this.key = key;
this.left = null; // 左樹
this.right = null;// 右樹
}
}
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(key){
const newNode = new Node(key);
const insertNode = (node,newNode)=>{
// 看下是放在左邊還是右邊
if(newNode.key < node.key){ // left
if(node.left == null){
node.left = newNode;
}else{ // 如果節(jié)點(diǎn)已經(jīng)有了那么繼續(xù)像當(dāng)前節(jié)點(diǎn)插入
insertNode(node.left,newNode);
}
}else{ // right
if(node.right == null){
node.right = newNode;
}else{
insertNode(node.right,newNode);
}
}
}
if(!this.root){ // 如果根沒(méi)有值 那么他就是根
this.root = newNode;
}else{ // 插到某一側(cè)
insertNode(this.root,newNode)
}
}
}
let binaryTree = new BinarySearchTree();
binaryTree.insert(8);
binaryTree.insert(3);
binaryTree.insert(10);
七.圖
圖可以看成有關(guān)聯(lián)的樹,我們可以使用鄰接表來(lái)描述各個(gè)節(jié)點(diǎn)的關(guān)系
image
class Graph{
constructor(){
this.List = {};
}
addNode(v){
this.List[v] = [];
}
addRelation(v,w){
// 相互存儲(chǔ)關(guān)系
this.List[v].push(w);
this.List[w].push(v);
}
}
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(node => graph.addNode(node));
graph.addRelation('A', 'B')
graph.addRelation('A', 'C')
graph.addRelation('A', 'D')
console.log(graph.List['A']);
看到這里是不是對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識(shí)啦！接下來(lái)就靠大家的合理應(yīng)用啦~
覺(jué)得本文對(duì)你有幫助嗎？請(qǐng)分享給更多人
關(guān)注「前端優(yōu)選」加星標(biāo)，提升前端技能
前端優(yōu)選公眾號(hào).jpg
加我微信：webyouxuan
