关于前端:前端内练基础你应该知道的数据结构之链表

前言：为什么要学数据结构，它能帮忙咱们什么？能解决什么问题呢，首页数据结构并不是一门具体的编程语言，它教会咱们的是一种思维形式，即如何以更优的形式存储数据和解决的一些问题，通过学习数据结构，能够大大拓宽咱们的思维模式。把握了数据结构与算法，咱们对待问题的深度、解决问题的角度会大有不同，对于集体逻辑思维的晋升，也是质的飞跃。

上面从以下几个点呈现逐个的理解他们实现的原理和场景：

• 什么是栈
• 什么是队列
• 什么是链表
• 什么是汇合
• 什么是字典
• 什么 二叉树

什么是链表

    要贮存多个元素、数组或者列表可能是最罕用的数据结构，然而这种数据结构有个毛病：数组的大小都是固定的，挪动元素和插入元素的老本很高；

    链表存储是有序的元素汇合，不同于数组的是链表的元素在内存中并不是间断的，每个元素是由一个元素的自身的节点指向下一个元素的援用。如下图所示：

如何实现一个链表

• 创立一个LinkedList的类骨架
• 创立一个连贯链表数据结构的Node类
• 丰盛链表的数据办法

创立一个LinkedList的类

初始三个值:

• count： 代表链表的元素数量
• head： 代表链表的数据结构
• equalsFn： 应用一个外部函数，代表链表中的元素是否相等

const defaultEquals = (a, b) => a === b

class LinkedList {
    constructor(equalsFn = defaultEquals){
        this.count = 0;  // 
        this.head = undefined
        this.equalsFn = equalsFn
    }
}

创立一个Node的类

初始两个值:

• element： 代表退出链表元素的值
• next： 代表指向下一个链表的指针

class Node  {
    constructor(element){
        this.element = element
        this.next = undefined
    }
}

丰盛链表的办法

• push(element)：向链表尾部增加一个新元素。
• insert(element, position)：向链表的特定地位插入一个新元素。
• getElementAt(index)：返回链表中特定地位的元素。如果链表中不存在这样的元素， 则返回 undefined
• remove(element)：从链表中移除一个元素。
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1
• removeAt(position)：从链表的特定地位移除一个元素。
• isEmpty()：如果链表中不蕴含任何元素， 返回 true，如果链表长度大于 0则返回 false。
• size()：返回链表蕴含的元素个数，与数组的 length 属性相似。

class LinkedList {
    constructor(equalsFn = defaultEquals){
        this.count = 0;
        this.head = undefined
        this.equalsFn = equalsFn
    }

    push(element) {
        const node = new Node(element)
        let current; 

        // 第一次进入是否为空
        if(this.head == null) {
            this.head = node
        }else {
            
            // 记录以后的援用关系
            current = this.head;

            while (current.next != null) {

                current = current.next;
            }

            // 将next 赋予新元素、建设链接
            current.next = node 
        }

        // 每次更新链表的长度
        this.count ++ 
    }

    // 返回链表中特定地位的元素
    getElementAt(index){
        
        if(index > 0 && index <= this.count ) {

            let node = this.head;
            let j = 0;
            
            while(j < index && node != null) {
                // 一直进行赋值
                node = node.next
                j++
            }
            return node;
        }

        return undefined
    }

    // 移除链表指定地位
    removeAt(index) {

        // 查看是否过界
        if(index >= 0 && index < this.count ) {
            
            // 保留对象的援用
            let current = this.head

            // 移除第一项
            if(index === 0 ) {

                this.head = current.next;
            }else {
                const previous = this.getElementAt(index - 1)
                current = previous.next;
                
                // 建设previous和current的下一项链接起来、起到一个挪动的作用
                previous.next = current.next
            }

            // 移除结束、进行长度减一
            this.count-- 
            return current.element

        }
        return undefined
    }

    // 项链表插入一个新元素
    insert(element, index ){
        if(index >=0 && index <= this.count) {

            const node = new Node(element);

            if(index === 0) {
                
                // 第一个地位增加
                const current = this.head;
                node.next = current
                this.head = node;
            }else {
                // 找到以后的链表地位
                const previous = this.getElementAt(index - 1);

                // 链表的下一个援用
                const current = previous.next;
                
                // 新增加的链表节点 进行连贯
                node.next = current;

                // 更新整个链表
                previous.next = node;
            }

            // 更新长度
            this.count ++ 
            return true
        }

        return false

    }

    // 返回元素在链表中的索引
    indexOf(element) {
        let current = this.head;

        for (let i = 0; i< this.count && current != null; i++) {
            
            if(this.equalsFn(element, current.element)) {
                return i
            }

            // 一直的更新current的值。
            current = current.next
        }
        return -1
    }

    // 移除元素
    remove (element) {
        const index = this.indexOf(element)
        return this.removeAt(index)
    }

    // 获取链表的个数
    size () {
        return this.count
    }

    // 链表是否为空
    isEmpty(){
        
        return this.size() === 0
    }

    // 获取head 办法
    getHead() {
        return this.head
    }
}

测试

const nodes = new LinkedList()

nodes.push(10)
nodes.push(20)
nodes.push(30)
nodes.push(40)
nodes.push(50)
nodes.push(60)

console.log(nodes.getHead())

后果如下图：

移除指定的链表地位：

const nodes = new LinkedList()

nodes.push(10)
nodes.push(20)
nodes.push(30)
nodes.push(40)
nodes.push(50)
nodes.push(60)

// 移除制订地位的链表
nodes.removeAt(4)

console.log(nodes.getHead())

后果如下图：

那么链表能够解决什么问题？

参考力扣的原题为例，试着用链表的思维来解决

  来自力扣83题删除排序链表中的反复元素

题解：

const nodes = new LinkedList()

nodes.push(10)
nodes.push(10)
nodes.push(20)
nodes.push(40)
nodes.push(40)
nodes.push(60) 

var deleteDuplicates = function({ head }) {
    // 放弃援用关系
    let cur = head;

    while(cur && cur.next) {
    
        // 层级向下比拟
        if(cur.element === cur.next.element) {
            
            // 跟移除元素相似
            cur.next = cur.next.next
        }else {
            cur = cur.next
        }
    }

    return head
};

let result = deleteDuplicates(nodes)
console.log(result)

以上就是简略回顾了一下链表的根本实现和场景利用、在理论的需要场景中还有很链表构造类型、比方：双向链表、循环链表、有序链表等等只有深刻的理解其外部的实现形式和办法能力在应酬简单的我的项目中大展手脚。

最初

本文系列参照《学习JavaScript数据结构与算法第3版》进行的整顿演绎、心愿能帮忙大家。