程序=数据结构+算法

1、初步认知

数据结构的定义

数据结构时计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法——中文维基百科

常见的数据结构

• 队列(Queue)
• 树(Tree)
• 堆(Heap)
• 数组(Array)
• 栈(Stack)
• 链表(Linked List)
• 图(Graph)
• 散列表(Hash)

每一种都有其对应的应用场景，不同的数据结构的不同操作性能是不同的。有的查询性能很快，有的插入速度很快，有的是插入头和尾速度很快。有的做范围查找很快，有的允许元素重复，有的不允许重复等等......在开发中如何选择，要根据具体的需求来选择

算法 Algorithm

定义：一个有限指令集，每条指令的描述不依赖于语言，接受一些输入（有些情况不需要输入），产生输出，一定在有限步骤之后终止

2、数组

2.1 创建和初始化

1、 使用new关键字

// 创建和初始化数组
var daysOfWeek = new Array()
var daysOfWeek = new Array(7)
var daysOfWeek = new Array('Sunday', 'Monday', 'Tuesday', 'Wednesday',
    'Thursday', 'Friday', 'Saturday')

        // 创建数组并赋值
        const arr = new Array()
        arr[0]=1;
        arr[2]=2;
        console.log(arr);
        //输出：[1,空，2]

        // 初始好长度
        const arr2 = new Array(7)
        arr2[0]=1;
        arr2[1]=2;
        console.log(arr2);
        //输出：[1,2,空x5]

2、 使用中括号（[]）创建数组

var daysOfWeek = ['Sunday', 'Monday', 'Tuesday', 'Wednesday',
    'Thursday', 'Friday', 'Saturday'];

2.2 数组的长度和遍历

// 获取数组的长度
alert(daysOfWeek.length)

//普通for循环遍历
const arr = ['beibei','jingjing','huanhuan','yingying','nini']
for(var i=0;i<=arr.length;i++){
    console.log(arr[i])
}
//输出
//beibei
//jingjing
//huanhuan
//yingying
//nini
//undefined

为什么会打印出undefined呢？

注意for循环的i<=arr.length=5，所以i会依次等于0,1,2,3,4,5,然而并不存在arr[5]

// 通过foreach遍历数组
arr.forEach(function (value) {
    alert(value)
})
//es6写法
arr.forEach(value=>{
    console.log(value)
})

2.3 数组的常见操作

添加元素、删除元素、修改元素、获取元素.

• 添加

从上边的arr例子中可以看出，一般情况下，数组的length总会比数组的索引大“1”

//初始化一个数组
let numbers = [0,1,2,3,4,5,6,7,8,9]
//这时numbers的length=10，而实际numbers的索引最大为9，利用这个特点，可以这样来向数组最后一位添加元素
numbers[numbers.length]=10	

//向数组最后添加新元素方式二
numbers.push(11)
numbers.push(12, 13)

向数组首位插入数据

// 通过unshift在首位插入数据
numbers.unshift(-2)
numbers.unshift(-4, -3)
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

• 删除

删除数组最后的元素, 可以使用pop()方法

// 删除最后的元素
numbers.pop()
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12

移除的首位元素, 自己实现代码

// 删除首位的元素
for (var i = 0; i < numbers.length; i++) {
    numbers[i] = numbers[i+1]
}
numbers.pop() //把最后一位删掉undefined
alert(numbers)

也可以通过shift()来删除

numbers.shift()

• 任意位置

通过splice删除数据

let arr = [1,23,4,5,67,89,9,54,34]
arr.splice(3,2)
//解析：上面的代码会删除索引为3,4位置的元素
//第一个参数表示索引起始的位置为3(其实是第4个元素, 因为索引从0开始的), 删除2个元素

通过splice()增加数据

let arr = [1,23,4,5,67,89,9,54,34]
arr.splice(3,0,'a','b','c')
//解析：上面的代码会从索引为3的位置开始插入数据. 其他数据依次向后位移.
//第二个参数为0时表示不是删除数据, 而是插入数据.
//后面紧跟的是在这个位置要插入的数据, 可以是其他类型, 比如"a", "b", "c".

通过splice()修改数据

let arr = [1,23,4,5,67,89,9,54,34]
arr.splice(3,3,'a','b','c')
//解析：上面的代码会从值为5的位置开始修改数据, 修改多少个呢? 第二个参数来决定的.
//第二个参数是要将数组中多少个元素给替换掉, 我们这里是3个
//后面跟着的就是要替换的元素

2.4 数组常见的方法

数组的合并

使用concat即可(也可以直接+进行合并)

//方法一
let arr = [1,2,3,4,5,'a','b','c']
let arr2 = [23,43,5,'da','ada','fsf']
let newArr = arr.concat(arr2)
console.log(newArr);
//[1, 2, 3, 4, 5, "a", "b", "c", 23, 43, 5, "da", "ada", "fsf"]

//方法二
let newArr =arr+arr2
//输出：1, 2, 3, 4, 5, "a", "b", "c", 23, 43, 5, "da", "ada", "fsf"
//非数组

数组的迭代

• every()

1、every()方法是将数组中每一个元素传入到一个函数中, 该函数返回true/false

2、如果函数中每一个元素都返回true, 那么结果为true, 有一个为false, 那么结果为false

//判断数组的元素是否都大于11
let arr = [22,33,44,55]
let res = arr.every(value=>{
    return value>11
})
console.log(res); //true

• some()方法

1、some()方法是将数组中每一个元素传入到一个函数中, 该函数返回true/false

2、但是和every不同的是, 一旦有一次函数返回了true, 那么迭代就会结束. 并且结果为true

// 定义数组
var names = ["abc", "cb", "mba", "dna"]

// 判断数组中是否包含有a字符的字符
//只要存在一个，即返回true
var flag = names.some(function (t) {
    alert(t)
    return t.indexOf("a") != -1
})
alert(flag)

• forEach()

快速遍历数组

// 定义数组
var names = ["abc", "cb", "mba", "dna"]

// forEach的使用
names.forEach(t=>{
    alert(t)
})

• filter()

filter()方法是一种过滤的函数

首先会遍历数组中每一个元素传入到函数中

函数的结果返回true, 那么这个元素会被添加到最新的数组中, 返回false, 则忽略该元素.

最终会形成一个新的数组, 该数组就是filter()方法的返回值

//数组中有哪些值大于11
let arr = [1,2,4,55,12,7,88,2]
let res = arr.filter(value=>{
    return value>11
})
console.log(res);

• map()

map()方法提供的是一种映射函数.

首先会遍历数组中每一个元素传入到函数中.

元素会经过函数中的指令进行各种变换, 生成新的元素, 并且将新的元素返回.

最终会将返回的所有元素形成一个新的数组, 该数组就是map()方法的返回值

//为数组中的每一个元素添加"your"前缀
let arr = ['day','mon','sister','brother']
let res = arr.map(value=>{
    return 'your'+value
})
console.log(res);

• reduce()

arr.reduce(callback[, initialValue])

callback（一个在数组中每一项上调用的函数，接受四个函数：

​ 1、previousValue（上一次调用回调函数时的返回值，或者初始值）

​ 2、currentValue（当前正在处理的数组元素）

​ 3、currentIndex（当前正在处理的数组元素下标）

​ 4、array（调用reduce()方法的数组）

initialValue（可选的初始值。作为第一次调用回调函数时传给previousValue的值）

通过例题解析——求一个数组中数字的累加和

//方法一
var numbers = [1, 2, 3, 4]
var total = 0
numbers.forEach(t=>{
    total += t
})
alert(total)

//方法二——通过reduce
var total = numbers.reduce((pre, cur)=>{
    return pre + cur
})
alert(total)

代码解析:

• pre中每次传入的参数是不固定的, 而是上次执行函数时的结果保存在了pre中
• 第一次执行时, pre为0, cur为1
• 第二次执行时, pre为1 (0+1, 上次函数执行的结果), cur为2
• 第三次执行时, pre为3 (1+2, 上次函数执行的结果), cur为3
• 第四次执行时, pre为6 (3+3, 上次函数执行的结果), cur为4
• 当cur为4时, 数组中的元素遍历完了, 就直接将第四次的结果, 作为reduce函数的返回值进行返回.

• splice()

1、删除（起始位置，删除个数）

const arr = [22,33,44,556,77,888]）
arr.splice(1,1); //输出索引1处的1个值
alert(arr)

2、替换（起始位置，长度，替换的值）

arr.splice(3,1,55)
alert(arr) //将索引值为3处的一个值，替换成55

3、添加（起始位置，0，添加的值）

arr.splice(4,0,66)
console.log(arr); //在索引值为4处添加一个

3 、栈结构

3.1 概述

栈是一种非常常见的数据结构，并且在程序中的应用十分广泛

栈（stack），是一种==受限的线性表==，后进先出（LIFO Last In First Out）

• 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对的，另一端称为栈底

• LIFO（last in first out)表示就是后进入的元素，第一个弹出栈空间

• 向一个栈插入新元素又被称作进栈，入栈或压栈，它是把新元素放到栈顶元素的上面，使之称为新的栈顶元素

• 从一个栈删除元素又被称作出栈或退栈，它是把栈顶元素删掉，使其相邻的元素成为新的栈顶元素

面试题

有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列（）

• A. 5,4,3,6,1,2
• B. 4,5,3,2,1,6
• C. 3,4,6,5,2,1
• D. 2,3,4,1,5,6

答案：C

栈结构的实现

方式：1、基于数组实现 2、基于链表实现

栈的常见操作

• push(element):添加一个新元素到栈顶位置
• pop() :移除栈顶的元素，同时返回被移除的元素
• peek():返回栈顶的元素，不对栈进行任何修改
• isEmpty():如果栈里没有任何元素就返回true,反则返回false
• size(): 返回栈里的元素个数。
• toString():将栈结构的内容以字符串形式返回

3.2 栈的封装

基于数组实现

 // 封装栈类
    function Stack(){
        //栈中的属性
        this.items = []

        // 栈的相关操作
        // 1.将元素压入栈
        Stack.prototype.push =function(element){
            this.items.push(element)
        }

        // 2.从栈中取出元素
        Stack.prototype.pop = function(){
            return this.items.pop()
        }

        // 3.查看一下栈顶的元素
        Stack.prototype.peek = function(){
            return this.items[this.items.length-1]
        }

        // 4. 判断栈是否为空
        Stack.prototype.isEmpty = function(){
            return this.items.length ==0
        }

        // 5.获取栈中元素的个数
        Stack.prototype.size = function(){
            return this.items.length
        }

        //  6.toString方法
        Stack.prototype.toString = function(){
            var resultString = '';
            for(var i =0;i<this.items.length;i++){
                resultString +=this.items[i]+''
            }
            return resultString
        }
    }

基于类的改进写法

// 栈的封装
class Stack2 {
    constructor(){
        this.items = [] //也可为对象
        this.count = 0 //记录栈的长度
    }
    push(element){
        this.items[this.count] = element
        this.count++
    }

    pop(){
        if(this.isEmpty()) {
            console.log('栈为空')
            return
        }
        const temp = this.items[this.count - 1]
        delete this.items[this.count - 1]
        this.count--
        return temp
    }
    isEmpty() {
        return this.count === 0
    }
    top() {
        if(this.isEmpty()) {
             console.log('栈为空')
            return
        }
        return this.items[this.count - 1]
    }
    size() {
        return this.count
    }
    clear() {
        this.items = []
        this.count = 0
    }
}

3.3 栈的应用

栈的应用

案例一：十进制转换为二进制

例题解析：将十进制100转换为二进制是多少，怎么算（取余倒排序法）

十进制：100
计算：100/2 余数：0
计算：50/2  余数：0
计算：25/2  余数：1
计算：12/2  余数：0
计算：6/2   余数：0
计算：3/2   余数：1
计算：1/2   余数：1
结果：二进制：1100100

封装一个能将是十进制转换为二进制的函数

//利用栈结构将十进制转换为二进制
// 封装栈类
function Stack(){
    this.items = []

    // 入栈
    Stack.prototype.push = function(element){
        this.items.push(element)
    }

    //栈是否为空
    Stack.prototype.isEmpty = function(){
        return this.items.length == 0
    }

    //出栈
    Stack.prototype.pop = function(){
        return this.items.pop()
    }
}

//函数：将十进制转换为二进制
function dec2bin(decNumber){
    // 1.定义栈对象
    var stack = new Stack()

    // 2.循环操作
    while(decNumber > 0){
        //获取余数，并放入栈中
        stack.push(decNumber % 2)

        // 获取整除后的结果，作为下一次运行的数字
        decNumber = Math.floor(decNumber/2)
    }

    // 3.从栈中取出0和1
    var binaryString = ''
    while(!stack.isEmpty()){
        binaryString += stack.pop()
    }
    return binaryString
}

// 使用十进制转换为二进制的函数
console.log(dec2bin(100)); //1100100
console.log(dec2bin(1000));//1111101000

4、队列

4.1 概述

队列（Queue），它是一种==受限的线性表==，先进先出（FIFO First In First Out）

+ 受限之处表现在于它只允许在表的前端（front）进行删除操作
+ 而在表的后端（rear）进行插入操作

生活中的案例：优先排队的人，优先处理（买票，结账）

队列的应用

• 打印队列

  有5份文档需要打印，这些文档会按照次序放入到打印队列中

  打印机会依次从队列中取出文档，优先放入的文档，优先被取出，并且对该文档进行打印

  以此类推，直到队列中不再有新的文档

• 线程队列

  在开发中，为了让任务可以并行处理，通常会开启多个线程

  但是，我们不能让大量的线程同时运行处理任务（占用过多的资源）

  这时，如果有需要开启线程处理任务的情况，我们就会使用线程队列

  线程队列会依照次序来启动线程，并且处理对应的任务

4.2 队列结构的封装

实现方案：1、基于数组实现 ；2、基于链表实现

队列的常见操作

• enqueue（element）：向队列尾部添加一个（或多个）新的项。
• dequeue() : 移除队列的第一项（即排在队列最前面的）并返回被移除的元素
• front() : 返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动
• isEmpty() : 如果队列中不包含任何元素，返回true，否则返回false
• size() : 返回队列包含元素个数，与数组的length属性类似
• toString() : 将列队中的内容，转成字符串形式

基于数组实现

// 封装队列类
function Queue(){
    // 属性
    this.items = []

    // 1.将元素添加到队列中
    Queue.prototype.enqueue = function(element){
        this.items.push(element)
    }

    // 2.从队列删除前端元素
    Queue.prototype.dequeue = function(){
        return this.items.shift() //该方法用于把数组的第一个元素从其中删除，并返回该值
    }

    //3.查看队列的前端元素
    Queue.prototype.front = function(){
        return this.items[0]
    }

    //4.查看队列是否为空
    Queue.prototype.isEmpty = function(){
        return this.items.length == 0
    }

    //5.查看队列的元素个数
    Queue.prototype.size = function(){
        return this.items.length
    }

    // 6.toSting方法
    Queue.prototype.toString = function(){
        var resultString = '';
        for(var i =0;i<this.items.length;i++){
            resultString +=this.items[i]+''
        }
        return resultString
    }
}

利用类进行改进

//数组
class Queue {
    constructor() {
        this.queue = []
        this.count = 0
    }
    // 入队
    enQueue(element) {
        this.queue[this.count++] = element 
    }
    // 出队
    deQueue() {
        if(this.isEmpty()) return
        this.count--
        return this.queue.shift()
    }
    isEmpty() {
        return this.count === 0
    }
    top() {
        return this.queue[0]
    }
    size() {
        return this.count
    }
    clear() {
        this.queue = []
        this.count = 0
    }
}

//对象
//对象在处理出队稍有不同，需特殊处理key值
class Queue {
    constructor() {
        this.queue = {}
        this.count = 0
        // 用于记录队首的键
        this.head = 0
    }
    enQueue(element) {
        this.queue[this.count++] = element
    }

    isEmpty() {
        return this.count === 0
    }
    deQueue() {
        if(this.isEmpty()) return '队列为空'
        let headData = this.queue[this.head]
        delete this.queue[this.head]
        this.head++
        this.count--
        return headData
    }
    clear() {
        this.queeu = {}
        this.head = 0
        this.count = 0
    }
}

4.3 优先级队列

特点：

普通的队列插入一个元素，数据会被放在后端，并且需要前面所有的元素都处理完成后才会处理前面的数据。

但是优先级队列，在插入一个元素的时候会考虑该数据的优先级。和其他数据优先级进行比较，比较完成后，可以得出这个元素在队列中正确的位置，其他处理方式，和基本队列的处理方式一样。

优先队列主要考虑的问题：

1、每个元素不再只是一个数据，而是包含数据的优先级

2、在添加方式中，根据优先级放入正确的位置

优先级的应用：

• 机场的登记顺序（头等舱优先于经济舱，老年人、孕妇优先于其他乘客）
• 医院的候诊室（医生优先处理病情比较严重的患者）

封装队列优先级

// 封装优先级队列
function PriorityQueue(){
    //在PriorityQueue重新创建一个类：可以理解成内部类
    function QueueElement(element,priority){
        this.element = element
        this.priority = priority
    }

    // 封装属性
    this.items = []

    // 一、实现插入方法
    PriorityQueue.prototype.enqueue = function(element,priority){
        // 1.创建QueueElement对象
        var queueElement = new QueueElement(element,priority)

        // 2.判断对列是否为空
        if(this.items.length == 0){
            this.items.push(queueElement)
        }else{
            var added = false
            for(var i = 0;i < this.items.length;i++){
                if(queueElement.priority < this.items[i].priority){
                    this.items.splice(i,0,queueElement) 
                    //在索引为i的位置插入queueElement
                    added = true
                    break //找到则停止，提高性能
                }
            }
            if(!added){ //如果在items中找不到比自己优先级低的，则直接添加在最后
                this.items.push(queueElement)
            }
        }
    }
     // 2.从队列删除前端元素
     PriorityQueue.prototype.dequeue = function(){
        return this.items.shift() //该方法用于把数组的第一个元素从其中删除，并返回该值
    }

    //3.查看队列的前端元素
    PriorityQueue.prototype.front = function(){
        return this.items[0]
    }

    //4.查看队列是否为空
    PriorityQueue.prototype.isEmpty = function(){
        return this.items.length == 0
    }

    //5.查看队列的元素个数
    PriorityQueue.prototype.size = function(){
        return this.items.length
    }

    // 6.toSting方法
    PriorityQueue.prototype.toString = function(){
        var resultString = '';
        for(var i =0;i<this.items.length;i++){
            resultString +=this.items[i].element+'-'+this.items[i].priority+' '
        }
        return resultString
    }
}

// 测试代码
var pq = new PriorityQueue()

// enqueue方法
pq.enqueue('abc',111)
pq.enqueue('bcd',123)
pq.enqueue('weq',231)
pq.enqueue('lkj',454)
pq.enqueue('lkj',999)
alert(pq)

4.4 双端队列

双端队列是指允许同时从队尾与队首两端进行存取操作的队列，操作更加灵活

与数组的区别

双端队列与JavaScript中的数组操作十分相似，但是不允许在除了两端以外的位置进行存取操作

功能：

• addFront/ addBack
• removeFront/removeBack
• frontTop/backTop

利用对象的key可以为负数，负数代码队首，实现起来比较简单

示例： { -1 : 'a', -2 : 'b', -3 : 'c', 0: 'x', 1: 'y', 2: 'z' }

队首： -1: 'a'

队尾: 2: 'z'

class Deque{
    constructor() {
        this.queue = {} 
        this.count = 0
        this.head = 0
    }

    // 队首添加
    addFront(element) {
        this.queue[--this.head] = element
    }
    // 队尾添加
    addBack(element) {
        this.queue[this.count++] = element
    }
    // 队首删除
    removeFront() {
        if(this.isEmpty()) return
        const headData = this.queue[this.head]
        delete this.queue[this.head]
        this.head++
        return headData
    }
    // 队尾删除
    removeBack() {
        if(this.isEmpty()) return 
        const backData = this.queue[this.count - 1]
        delete this.queue[this.count -1]
        this.count--
        return backData
    }

    isEmpty() {
        return this.size() === 0
    }
    size() {
        return this.count - this.head
    }
}

5、链表结构

5.1 概述

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

不同于数组,链表中的元素在内存中不必是连续的空间，链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成

数组的缺点

1、数组的创建通常需要申请一段连续的内存空间（一整块的内存），并且大小是固定的所以当当前的数组不能满足容量需求时，就需要扩容

2、而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移

链表的优点

1、内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的动态管理

2、链表不必再创建时就确定大小，并且大小可以无限延伸下去

3、链表在插入和删除数据时，时间复杂度可以达到O（1），相对数组效率高很多

链表的缺点

1、链表访问任一位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）

2、无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素

什么是链表呢？

类似于生活中的火车：有一个火车头，火车头会连接一个节点，节点上有乘客（相当于数据），并且这个节点会连接下一个节点，以此类推。

5.2 链表结构的封装

代码解析： 1、封装LinkedList的类，用于表示我们的链表结构

2、在LinkedList类中有一个Node类，用于封装每一个节点上的信息

3、链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点

function LinkedList(){
    // 内部类：节点类
    function Node(data){
        this.data = data
        this.next = null
    }

    // 属性
    this.head = null //链表的第一个节点
    this.length = 0
}

链表常见的操作

1、append（element）：向链表尾部添加一个新的项

2、insert（position，element）：向链表的特定位置插入一个新的项

3、get（position）：获取对应位置的元素

4、indexOf（element）：返回元素在链表中的索引。如果链表中不存在该元素则返回-1

5、update（position，element）：修改某个位置的元素

6、removeAt（position）：从链表的特定位置移除一项

7、remove（element）：从链表中移除一项

8、isEmpty（）：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false

9、size（）：返回链表包含的元素个数

10、toString（）：将链表中的元素以字符串形式输出

封装append方法

向链表尾部追加数据可能有两种情况： 1、链表本身为空，新添加的数据是唯一的节点

2、链表不为空，需要向其他节点后面追加节点

function LinkedList(){
        // 内部类：节点类
        function Node(data){
            this.data = data
            this.next = null
        }

        // 属性
        this.head = null
        this.length = 0

        LinkedList.prototype.append = function(data){
            //1. 创建新的节点
            var newNode = new Node(data)

            // 2.判断添加的是否是第一个节点
            if(this.length == 0){ //2.1 是第一个节点
                this.head = newNode
            }else{ //2.2 不是第一个节点
                //找到最后一个节点
                var current = this.head //令current指向第一个节点
                while(current.next){
                    //第一个节点的next有内容则current等于这个next，所以第二次循环是while(第二个节点的next是否有内容)，为false时说明第二个节点是最后一个节点，为true，令current = current.next，进入第三个节点的循环。以此类推，最终会找到最后一个节点
                    current = current.next 
                }

                //最后的节点next指向新的节点
                current.next = newNode
            }
            // 3 length +1
            this.length+=1
        }
    }

封装toString方法

先封装该方法， 这样会方便测试上面的添加代码

ps： toString方法有一个特性是：在执行一些特殊方法的时候，比如alert或innerHTML等方法，它将由脚本解析器自动调用。

// 二、toString方法
    LinkedList.prototype.toString = function(){
        var current = this.head
        var linkString = ""

        while(current){
            linkString += current.data + " "
            current = current.next
        }
        return linkString
    }

测试

// 测试方法
// 创建实例
var list = new LinkedList()

// 1.append追加方法
list.append("第一项")
list.append("第二项")
list.append("第三项")
alert(list)
//输出 第一项 第二项 第三项

封装insert方法

在任意位置插入数据

情况1：添加到的是第一个位置，表示新添加的节点就是头，就需要将原来的头节点作为新节点的next，另外这时候的head应该指向新节点

情况2：如果添加到其他位置，就要找到这个节点位置，我们通过while循环，一点点向下找，并且在这个过程中保存上一个节点和下一个节点，找到正确的位置后，将新节点的next指向下一个节点，将上一个节点的next指向新的节点

// 三、insert方法
LinkedList.prototype.insert = function(position,data){
    // 1.对position进行越界判断
    if(position < 0 || position > this.length) return false

    // 2.根据data创建newNode
    var newNode = new Node(data)

    // 3.判断插入的位置是否是第一个
    if(position == 0){
        newNode.next = this.head
        this.head = newNode
    }else{
        var index = 0
        var current = this.head
        var previous = null	
        while(index++ < position){
            previous = current
            current = current.next
        }

        newNode.next = current
        previous.next = newNode
    }
    // 4. length+1
    this.length += 1

    return true
}

测试

list.append("第一项")
list.append("第二项")
list.append("第三项")
// alert(list)

// 2.测试insert方法
list.insert(1,"插入")
list.insert(3,"插入")
alert(list)

封装get方法

获取对应位置的元素

// get 方法获取对应位置的元素
LinkedList.prototype.get = function (position) {
    // 1. 判断越界
    if(position < 0 || position >= this.length) return null  //这里position不能等于this.length

    // 2.获取对应的data
    var current = this.head //默认指向第一项
    var index = 0
    while(index < position){ //循环，直到找到position所在的节点
        current = current.next
        index++
    }
    return current.data
}

测试代码

// 3.测试get方法
let res = list.get(1)
console.log(res);

封装indexOf方法

返回元素在链表中的索引。如果链表中不存在该元素则返回-1

// 五、inedxOf方法
LinkedList.prototype.indexOf = function (data) {
    // 1.定义变量
    var current = this.head
    var index = 0

    // 2.开始查找
    while(current){ //当current存在时
        if(current.data == data) {
            return index
        }
        current = current.next //循环
        index++
    }
    // 3.找到最后没有找到，返回-1
    return -1
}

测试

// 4.测试indexOf方法
let res2 = list.indexOf("插入")
console.log(res2);

封装update方法

// 六、update方法
LinkedList.prototype.update = function(position,newData){
    // 1. 越界判断
    if(position < 0 || position >=this.length) return false

    // 2.查找正确的节点
    var current = this.head
    var index = 0
    while(index < position){
        current = current.next
        index++
    }
    // 3.将position位置的node的data修改成newData
    current.data = newData
    return true
}

// 5.测试update方法
list.update(0,"第1项")
alert(list)

封装removeAt方法

// 七、removeAt方法
LinkedList.prototype.removeAt = function(position){
    // 1.判断是否越界
    if(position < 0 || position >= this.length) return null

    // 2.判断删除的是否是第一个节点
    var current = this.head
    if(position == 0){
        this.head = this.head.next
    }else{
        var previous = null
        var index = 0
        while(index++ <position){
            previous = current
            current = current.next
        }

        // 3. 前一个节点的next指向current的next
        previous.next = current.next    

        //length -1
        this.length -= 1
        return current.data
    }
}

测试

// 6.测试removeAt方法
list.removeAt(1)
alert(list)

封装remove方法

// 八、remove方法
LinkedList.prototype.remove = function(element){
    // 1.调用indexOf获取element的索引
    var position = this.indexOf(element) 

    // 2.根据位置信息删除节点
    return this.removeAt(position)
}
// 测试remove方法
list.remove("插入")
list.remove("第1项")
alert(list)

封装isEmpty、size方法

// 九、isEmpty方法
LinkedList.prototype.isEmpty = function(){
    // if(this.length == 0){
    //     return true
    // }else{
    //     return false
    // }
    return this.length == 0
}
// 十、size方法
LinkedList.prototype.size = function(){
    return this.length
}

测试

var list2 = new LinkedList()
list2.append("first")
list2.append("second")
console.log(list2);
console.log(list2.isEmpty());
console.log(list2.size());

5.3 改进链表封装

class LinkedNode {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

class LinkedList {
    constructor() {
        this.count = 0
        this.head = null
    }

    // 添加节点（尾部）
    addAtTail(value) {
        // 创建新节点
        const node = new LinkedNode(value)
        if(this.count === 0) {
            this.head = node
            this.count++
        }
        else {
            // 找到链表的尾部，最后一个节点的next设置为node
            let current = this.head
            while(current.next !== null) {
                current = current.next
            }
            current.next = node
            this.count++
        }
    }

    // 添加节点（首部）
    addAtHead(value) {
        const node = new LinkedNode(value)
        if(this.count === 0) {
            this.head = node
        }
        else {
            node.next = this.head
            this.head = node
        }
        this.count++
    }
    // 获取节点
    get(index) {
        if(this.count === 0 || index < 0 || index >= this.count) return 
        let current = this.head
        for(let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }

    // 添加节点（根据索引）
    addAtIndex(value, index) {
        if(this.count === 0 || index >= this.count) return 

        // 索引小于0，默认添加到头部
        if(index <= 0) {
           return this.addAtHead(value)
        }

        let prev = this.get(index - 1)
        let next = prev.next

        let node = new LinkedNode(value)
        prev.next = node
        node.next = next
        this.count++
    }
    // 删除（根据索引）
    removeAtIndex(index) {
        if(this.count === 0 || index < 0 || index >= this.count) return 
        if(index === 0) {
            this.head = this.head.next
        } 
        else {
            const prev = this.get(index - 1)
            prev.next = prev.next.next
        }
        this.count--
    }
}

5.4 双向链表

区分

1、单向链表

​ 只能从头遍历到尾或者从尾遍历到头，也就是链表相连接的过程是单向的，实现原理是上一个链表中有一个指向下一个的引用

​ 缺点：利用单向链表可以轻松到达下一个节点，但是回到前一个节点是很难的，实际开发中，经常需要回到前一个节点的情况

2、双向链表

​ 既可以从头遍历到尾，又可以从尾遍历到头，也就是链表相连的过程是双向的。原理：一个节点既有向前连接的引用，也有一个向后连接的引用

​ 缺点：每次在插入或删除某个节点时，需要处理四个引用，而不是两个，也就是实现起来更困难一些。并且相较于单向链表，占用的内存空间大一些。

双向链表的特点

1、可以使用一个head和一个tail分别指向头部和尾部的节点

2、每个节点都由三部分组成：前一个节点的指针保存（prev）、保存的元素（data）、后一个节点的指针（next）

3、双向链表的第一个节点的prev是null

4、双向链表的最后的节点的next是null

常见操作

• append(element): 向链表尾部添加一个项
• insert(position,element):向链表的特定位置插入一个新的项
• get(position): 获取对应位置的元素
• indexOf(element):返回元素在链表中的索引，如果不存在该元素，则返回-1
• update(position,element):修改某个位置的元素
• removeAt(position):从链表中移除某特定位置的元素
• remove(element) :从列表中移除一项
• isEmpty():如果链表中不包含任何元素，返回true，如果链表长度大于0，则返回false
• size():返回链表包含的元素个数
• toString():输出链表中元素的值
• forwardString():返回正在遍历的节点的字符创形式
• backwordString():返回反向遍历的节点字符创形式

5.5 双向链表的封装

// 封装双向链表
function DoublyLinkedList(){
    // 内部类
    function Node(data){
        this.data = data
        this.prev = null
        this.next = null
    }

    // 属性
    this.head = null
    this.tail = null
    this.length = 0
}

append方法

// 封装双向链表
function DoublyLinkedList(){
    // 内部类
    function Node(data){
        this.data = data
        this.prev = null
        this.next = null
    }

    // 属性
    this.head = null
    this.tail = null
    this.length = 0

    // 常见的操作：方法
    // 方法一 append
    DoublyLinkedList.prototype.append = function(data){

        // 1.创建节点
        var newNode = new Node(data)

        // 2.判断是否是第一个节点
        if(this.length ==0){
            this.head = newNode
            this.tail = newNode
        }else{
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        }

        // length +1
        this.length +=1
    }
}

转为字符串方法

包括toString、backworkString、forwardString

// 方法二 1. forwardString 从后往前遍历，并返回字符串形式
DoublyLinkedList.prototype.forwardString = function(){
    // 定义变量
    var current = this.tail
    var resultString = ""

    while(current){
        resultString +=current.data + " "
        current = current.prev
    }
    return resultString
}
// 方法二 2. backwordString 从前往后遍历，并返回字符串形式
DoublyLinkedList.prototype.backwordString = function(){
    // 定义变量
    var current = this.head
    var resultString = ""

    while(current){
        resultString += current.data + " "
        current = current.next
    }

    return resultString
}
// 方法二 3.toString 从前往后遍历，并返回字符串形式
DoublyLinkedList.prototype.toString = function(){
    return this.backwordString()
}

测试使用

// 测试代码
// 创建实例
var list = new DoublyLinkedList()
// append 方法
list.append("迪卢克")
list.append("甘雨")
list.append("温蒂")

// 转换成字符串的方法
alert(list)
alert(list.forwardString())
alert(list.backwordString())    

insert方法

// 方法三 insert方法
DoublyLinkedList.prototype.insert = function(position,data){
    // 1. 越界判断
    if(position < 0 || position >= this.length) return false

    // 2.根据Node创建新的节点
    var newNode = new Node(data)

    // 3.判断原来的链表是否为空
    if(this.length == 0){
        this.head = newNode
        this.tail = newNode
    }else{
        // 3.1 判断position是否为0
        if(position == 0){
            // 原来的第一个节点.prev = newNode
            // newNode.next  = 原来的第一个节点
            this.head.prev = newNode
            newNode.next = this.head
            this.head = newNode
        }else if(position == this.length){ // 判断添加进了链表的最后
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        }else{
            // 其他情况
            var current = this.head
            var index = 0

            while(index++ < position){
                current = current.next
            }
            // 修改指针
            newNode.next = current
            newNode.prev = current.prev
            current.prev.next = newNode
            current.prev = newNode
        }

    }
}

测试

// insert
list.insert(0,"七七")
list.insert(1,"芭芭拉")
list.insert(0,"琴")
alert(list)

get 方法

// 方法四 get方法
DoublyLinkedList.prototype.get = function (position) {
    // 1.越界判断
    if(position < 0 || position >= this.length) return null

    // 2.获取元素
    var index = 0
    var current = this.head
    while(index++ < position){
        current = current.next 
    }
    return current.data
}

index0f方法

// 方法五 indexOf
DoublyLinkedList.prototype.index0f = function (data){
    // 定义变量
    var current = this.head
    var index = 0

    while(current){
        if(current.data == data){
            return index
        }
        current = current.next
        index +=1
    }
    // 找不到data
    return -1
}

测试

// indexOf
alert(list.index0f("芭芭拉"));
alert(list.index0f("魈"))

update方法

// 方法六 update
DoublyLinkedList.prototype.update = function (position,newData){
    // 越界判断
    if(position < 0 || position >= this.length) return false

    var current = this.head
    var index = 0
    while(index++ < position){
        current = current.next
    }
    // 找到了
    current.data = newData

    return true
}

测试

// updata
list.update(2,"重云")
alert(list)

removeAt方法

// 方法七 removeAt
DoublyLinkedList.prototype.removeAt = function (position) {
    // 1.判断越界
    if(position < 0 || position >= this.length) return null

    //2. 链表有且仅有一个节点的情况
    var current = this.head
    if( this.length == 1){
        this.head = null
        this.tail = null
    }else{
        if(position == 0){ // 3.1 删除的是链表的第一个节点
            this.head.next.prev = null
            this.head = this.head.next
        }else if(position == this.length-1){   //3.2删除的是最后一个节点
            this.tail.prev.next = null
            this.tail = this.tail.prev
        }else{ //3.3 其他情况
            var index = 0
            while(index++ <position){
                current =current.next
            }
            // 找到position对应的节点
            current.prev.next = current.next
            current.next.prev = current.prev
        }
    }
    this.length -=1 
    return current.data
}

测试

// removeAt
// 删掉七七
list.removeAt(0)
alert(list)

remove方法

// 方法八
DoublyLinkedList.prototype.remove = function (data) {
    // 根据indexOf获取data的索引
    var index = this.index0f(data)

    // 根据索引调用removeAt删除元素，并返回
    return this.removeAt(index)
}

测试

// remove
var list3 = new DoublyLinkedList()
list3.append("111")
list3.append("222")
list3.append("333")
list3.append("444")
alert(list3)
list3.remove("333")
alert(list3)

双向链表其他方法

// 方法九 isEmpty
DoublyLinkedList.prototype.isEmpty = function () {
    return this.length == 0
}

// 方法十 size
DoublyLinkedList.prototype.size = function () {
    return this.length
}

// 链表常用方法：获取第一个元素
DoublyLinkedList.prototype.getHead = function () {
    return this.head.data
}

// 链表常用方法：获取最后一个元素
DoublyLinkedList.prototype.getTail = function () {
    return this.tail.data
}

测试

var list3 = new DoublyLinkedList()
list3.append("111")
list3.append("222")
list3.append("333")
list3.append("444")
alert(list3)
// 测试
alert(list3.isEmpty())
alert(list3.size())
alert(list3.getHead())
alert(list3.getTail())

5.6 链表的其他形式

循环链表

• 循环链表又称为环形链表，指的是链表最后一个节点的next指向第一个节点，形成首尾相连的循环结构，称为循环列表