数据结构---链表

     //封装链表类
        function LinkedList() {
            //内部的类，节点类
            function Node(data) {
                this.data = data
                this.next = null
            }
            //属性
            this.haed = null//指针最开始
            this.length = 0

        }

append方法（追加元素）

链表本身是空的, 比如这种情况下我们插入了一个15作为元素

链表中已经有元素了, 需要向最后的节点的next中添加节点.

这个时候要向链表的尾部添加一个元素, 首先我们需要找到这个尾部元素.
记住: 我们只有第一个元素的引用, 因此需要循环访问链表, 直接找到最后一个项.(见代码2.1)
找到最后一项后, 最后一项的next为null, 这个时候不让其为null, 而是指向新创建的节点即可.

向列表追加数据可能有两种情况：列表本身为空，新添加数据时唯一节点，链表不为空，需要向其他节点追加节点

             // append 向列表尾部添加一个新的项
            LinkedList.prototype.append = function (data) {
                //创建新节点
                let newNode = new Node(data)
                //判断是否添加的是第一个节点
                if (this.length == 0) {//是第一个节点
                    this.haed = newNode
                } else {
                    //找到最后一个节点
                    let current = this.haed
                    while (current.next) {
                        current = current.next
                    }
                    //最后节点的next指向新节点
                    current.next = newNode
                }
                //长度加1
                this.length += 1
            }

toString方法（转字符串）

从head开头,获取列表任意元素都必须从第一个节点开头，循环遍历每一个节点，并且取出其中的element拼接成字符串将最终字符串返回

    //toString方法
            LinkedList.prototype.toString = function () {
                //定义变量
                let current = this.haed
                let listString = ''
                //循环获取每一个节点
                while (current) {
                    listString += "," + current.data
                    current = current.next
                }
                return listString.slice(1)
            }

insert方法（插入元素）

添加到第一个位置:

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

添加到其他位置:

如果是添加到其他位置, 就需要先找到这个节点位置了.
我们通过while循环, 一点点向下找. 并且在这个过程中保存上一个节点和下一个节点.
找到正确的位置后, 将新节点的next指向下一个节点, 将上一个节点的next指向新的节点.

添加到第一个位置：表示新添加的节点是头，作为新节点的next 这个时候的next指向新节点

添加到其他位置：如果是添加到其他位置，就需要先找到这个节点的位置，通过while循环，一点点的向下找，并且在这个过程中保存上一个节点和下一个节点

找到正确位置后，将新节点的next指向下一个节点，将上一个节点的next指向新的节点

      LinkedList.prototype.insert = function (position, dada) {
                // 对position进行判断
                if (position < 0 || position > this.length) return false

                // 根据data创建newNode
                let newNode = new Node(data)

                // 判断插入的位置是否为第一个
                if (position = 0) {
                    //把指针赋值给新节点，在把指针修改为新节点的指针
                    newNode.next = this.haed
                    this.haed = newNode
                } else {
                    let index = 0
                    let previous = null
                    let current = this.haed
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    newNode.next = current
                    previous.next = newNode
                }
                //长度加1
                this.length += 1
                return true
            }

get方法（获取元素）

越界判断:当length等于0的时候直接返回最后一个的数据假如查询为2，每次index++ 重新赋值指针相等之后直接退出返回数据

          LinkedList.prototype.get = function (position) {
                //越界判断
                if (position < 0 || position >= this.length) return null
                //获取对应的data
                let current = this.haed
                let index = 0
                //position=2
                // index = 0 current=下一个指针
                // index = 1 current=下一个指针
                // index = 2 current=数据
                while (index < position) {
                    index++
                    current = current.next
                }
                return current.data
            }

indexof（获取索引）

index为索引 current为最开始的指针遍历查询每次索引和指针加1 如果传入的data跟数据对应的 data相等返回数据没有匹配项返回-1

   LinkedList.prototype.inexOf = function (data) {
                // 定义变量
                let current = this.haed
                let index = 0
                //开始查找
                while (current) {
                    if (current.data == data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }
                return -1
            }

update修改某个位置的元素

类似于get方法，找到指定元素修改启内容

      LinkedList.prototype.update = function (position, element) {
                //越界判断
                if (position < 0 || position >= this.length) return false
                //查找正确的节点
                let current = this.haed
                let index = 0
                while (index < position) {
                    index++
                    current = current.next
                }
                // 将position位置的node的data改为newdata
                current.data = element
                return true
            }

removeAt方法（删除元素，根据索引）

移除第一项的信息:

移除第一项时, 直接让head指向第二项信息就可以啦.
那么第一项信息没有引用指向, 就在链表中不再有效, 后面会被回收掉.

、

移除其他项的信息:

移除其他项的信息操作方式是相同的.
首先, 我们需要通过while循环, 找到正确的位置.
找到正确位置后, 就可以直接将上一项的next指向current项的next, 这样中间的项就没有引用指向它, 也就不再存在于链表后, 会面会被回收掉.

    LinkedList.prototype.removeAt = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.haed
                //判断是否删除的为第一个节点
                if (position == 0) {
                    this.haed = this.haed.next
                } else {
                    let index = 0
                    let previous = null//前一个节点
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    //前一个节点的next指向，current的next
                    previous.next = current.next
                }
                this.length -= 1
                return current.data
            }

remove(删除数据，根据元素)

//获取data在列表中的数据，根据位置信息删除数据


            // remove
            LinkedList.prototype.remove = function (data) {
                //获取data在列表中的数据
                let position = this.inexOf(data)
                //根据位置信息删除数据
                return this.removeAt(position)
            }

isEmpty&&size方法

 LinkedList.prototype.isEmpty = function (data) {
                return this.length == 0
            }
            LinkedList.prototype.size = function () {
                return this.length
            }

单想链表vs双向链表

单向链表

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

我们轻松可以到达下一个节点，但是回到前一个节点是很难的

双向链表

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

每次在插入或者删除某个节点的时候需要处理四个引用，而不是两个占用的空间更大些

封装双向链表

双向链表的特点

可以使用一个head和一个tail指向头部或者尾部的节点

每一个节点都有三个部分组成;前一个节点的指针（prev）保存元素的（item）后一个节点（next）

双向链表的第一个节点的prv是null，最后一个节点的next是null

封装链表结构

   function DoublyLinkedList() {
            // 内置类：节点类
            function Node(data) {
                this.data = data
                this.next = null
                this.prev = null // 新添加的
            }
            //属性
            this.head = null
            this.tail = null
            this.length = 0
        }

append方法（追加元素）

向列表追加数据可能有两种情况：列表本身为空，新添加数据时唯一节点，链表不为空，需要向其他节点追加节点（找到最后一个节点把指针指向新节点）

    // 在尾部追加数据
            DoublyLinkedList.prototype.append = function (element) {
                // 1.根据元素创建节点
                var newNode = new Node(element)

                // 2.判断列表是否为空列表
                if (this.head == null) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    this.tail.next = newNode
                    newNode.prev = this.tail
                    this.tail = newNode
                }

                // 3.length+1
                this.length++
            }

toString方法（转字符串）

reverseString反向遍历的方法：current获取最后一个元素每次遍历current重新赋值为上个节点的指针

forwardString：正向遍历的方法 head从第一项开始遍历 current每次为下一个节点的指针

toString转字符串默认正项遍历调用forwardString


            // 正向遍历的方法
            DoublyLinkedList.prototype.forwardString = function () {
                //定义变量
                let current = this.head
                let forwardStr = ''

                // 依次向后遍历获取每一个节点
                while (current) {
                    forwardStr += "," + current.data
                    current = current.next
                }

                return forwardStr.slice(1)
            }

            // 反向遍历的方法
            DoublyLinkedList.prototype.reverseString = function () {
                var current = this.tail
                var reverseStr = ""
                // 依次向前遍历获取每一个节点
                while (current) {
                    reverseStr += "," + current.data
                    current = current.prev
                }

                return reverseStr.slice(1)
            }

            // 实现toString方法
            DoublyLinkedList.prototype.toString = function () {
                return this.forwardString()
            }

insert 在任意位置插入数据

情况一: 将元素插入到头部(position === 0)

事实上, 将元素插入到头部是比较简单. 只是它有分成了两种情况.
情况一: 列表为空. 那么直接让head/tail指向newNode即可
情况二: 列表不为空, 这个时候需要修改原来head的prev指向新节点. 新节点的next指向原来的head. 并且head现在要指向newNode

情况二: 将元素插入到尾部(position === length)

这种情况比较简答了, 因为我们在append方法中已经处理过了.
注意: 这里不需要判断元素为空的情况, 因为在position === 0的时候, 我们已经处理过了. 所以到这里的时候, 肯定不为空.

情况三: 将元素插入到中间位置

情况三是比较复杂一些的, 但是我们理清楚它的逻辑关系也就比较简单了.
首先, 我们需要找到正确的插入位置. 通过while循环, 这个并不难, 因为我们在单向链表的时候已经找过了.
查找正确的位置后, 需要进行插入操作.
首先, 你的newNode的next/prev必然要指向前后的节点, 也就是current和previous
其次, 而current的prev需要指向newNode, 而previous的next需要指向newNode.
逻辑搞定, 并没有想象中的复杂, 详细看图解.

代码解析

判断列表为空head，tail 等于茶插入的节点
在第一个位置插入数据：原来的第一个节点的prev=指向改变之后的第一个节点，插入节点的下一个节点是当前节点，改变头部的节点为新插入的节点
插入到最后的情况：新节点的前一个节点，等于最后一个节点，原来的最后一个节点=插入的节点，改变指向尾部的节点为新节点
任意位置插入： //插入节点的下一个节点指针为查询到的下一个节点，插入节点的上一个节点指针为查询到的上一个节点，上一个节下一个指针=当前节点，查询到的上一个节指针=插入的节点

          DoublyLinkedList.prototype.insert = function (position, element) {
                // 1.判断越界的问题
                if (position < 0 || position > this.length) return false
                //根据data创建新节点
                var newNode = new Node(element)
                //判断列表是否为空
                if (this.length == 0) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    //判断position是否为0
                    if (position == 0) {//第一个节点
                        //原来的第一个节点的prev指向改变之后的第一个节点
                        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 {//其他情况
                        let current = this.head
                        let index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        //插入节点的下一个节点指针为查询到的下一个节点
                        newNode.next = current
                        //插入节点的上一个节点指针为查询到的上一个节点
                        newNode.prev = current.prev
                        // 上一个节下一个指针=当前节点  
                        current.prev.next = newNode
                        //查询到的上一个节指针=插入的节点
                        current.prev = newNode
                    }
                    this.length += 1
                    return true
                }
            }

get （根据索引查询数据）

index 和 current 每次加1 当索引相等之后返回数据


            DoublyLinkedList.prototype.get = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.head
                let inde = 0
                while (inde++ < position) {
                    current = current.next
                }
                return current.data
            }

indexof（获取索引）

index为索引 current为最开始的指针遍历查询每次索引和指针加1 如果传入的data跟数据对应的 data相等返回数据没有匹配项返回-1

undefined null false 0 NaN ""或''（空字符串）转布尔为false

            DoublyLinkedList.prototype.indexOf = function (element) {
                // 1.定义变量, 保存信息
                let current = this.head
                let index = 0

                // 2.找到元素所在的位置
                while (current) {
                    if (current.element === element) {
                        return index
                    }
                    index++
                    current = current.next
                }

                // 3.来到这个位置, 说明没有找到, 则返回-1
                return -1
            }

update修改某个位置的元素

类似于get方法，找到指定元素修改启内容

 DoublyLinkedList.prototype.updata = function (position, data) {
                // 1.判断越界的问题
                if (position < 0 || position >= this.length) return false
                //寻找正确的节点
                let current = this.head
                let inde = 0
                while (inde++ < position) {
                    current = current.next
                }
                current.data = data
                return true

            }

removeAt方法（删除元素，根据索引）

情况一: 删除头部的元素

删除头部的元素也分成两种情况.
情况一: 链表只有一个元素, 那么将head/tail直接设置为null即可
情况二: 链表有多个元素, 这个时候删除头部的元素. head = head.next. head.prev = null

情况二: 删除尾部的元素

删除尾部的元素和删除头部有多个元素的情况比较相似. (也不需要考虑个数为1的情况, 因为上一种情况已经考虑了)
将tail设置为tail的prev. tail的next设置为null即可.

情况三: 删除中间位置的元素

这种情况就需要先找到正确的位置, 还是使用while循环.
将previous的next直接设置成current的next, 将current.next的prev设置成previous即可

   DoublyLinkedList.prototype.removeAt = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.head
                //判断是否只有一个节点
                if (this.length == 1) {
                    this.head = null
                    this.tail = null
                } else {
                    //判断是否删除的是第一个节点
                    if (position == 0) {
                        //第一个节点的下一个节点的prev引用
                        this.head.next.prev = null
                        // 将指向头部的指向第二个节点
                        this.head = this.head.next
                    } else if (position == this.length - 1) { //最后的节点
                        current = this.tail
                        // 最后一个节点的前一个节点的next引用赋值null
                        this.tail.prev.next = null
                        // 最后一个节点为前一个节点
                        this.tail = this.tail.prev
                    } else {
                        let index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        //查询到的上一个节点的next指针等于查询到的下一个节点
                        current.prev.next = current.next
                        //查询到的下一个节点的prev等于查询到的上一个节点
                        current.next.prev = current.prev
                    }
                    this.length -= 1
                }
                return current.data
            }

remove(删除数据，根据元素)

//获取data在列表中的数据，根据位置信息删除数据indexOf

  DoublyLinkedList.prototype.remove = function (element) {
                var index = this.indexOf(element)
                return this.removeAt(index)
            }

isEmpty&&size方法

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

            // 获取链表长度
            DoublyLinkedList.prototype.size = function () {
                return this.length
            }

获取第一个元素&&获取最后一个元素

        // 获取第一个元素
            DoublyLinkedList.prototype.getHead = function () {
                return this.head.data
            }

            // 获取最后一个元素
            DoublyLinkedList.prototype.getTail = function () {
                return this.tail.data
            }

完整代码

单向

    function LinkedList() {
            //内部的类，节点类
            function Node(data) {
                this.data = data
                this.next = null
            }
            //属性
            this.haed = null//指针最开始
            this.length = 0
            // append 向列表尾部添加一个新的项
            LinkedList.prototype.append = function (data) {
                //创建新节点
                let newNode = new Node(data)
                //判断是否添加的是第一个节点
                if (this.length == 0) {//是第一个节点
                    this.haed = newNode
                } else {
                    //找到最后一个节点
                    let current = this.haed
                    while (current.next) {
                        current = current.next
                    }
                    //最后节点的next指向新节点
                    current.next = newNode
                }
                //长度加1
                this.length += 1
            }

            //toString方法
            LinkedList.prototype.toString = function () {
                //定义变量
                let current = this.haed
                let listString = ''
                //循环获取每一个节点
                while (current) {
                    listString += "," + current.data
                    current = current.next
                }
                return listString.slice(1)
            }

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

                // 根据data创建newNode
                let newNode = new Node(data)

                // 判断插入的位置是否为第一个
                if (position == 0) {
                    //把指针赋值给新节点，在把指针修改为新节点的指针
                    newNode.next = this.haed
                    this.haed = newNode
                } else {
                    let index = 0
                    let previous = null
                    let current = this.haed
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    newNode.next = current
                    previous.next = newNode
                }
                //长度加1
                this.length += 1
                return true
            }

            // get方法
            LinkedList.prototype.get = function (position) {
                //越界判断
                if (position < 0 || position >= this.length) return null
                //获取对应的data
                let current = this.haed
                let index = 0
                //position=2
                // index = 0 current=下一个指针
                // index = 1 current=下一个指针
                // index = 2 current=数据
                while (index < position) {
                    index++
                    current = current.next
                }
                return current.data
            }

            // inexof方法
            LinkedList.prototype.inexOf = function (data) {
                // 定义变量
                let current = this.haed
                let index = 0
                //开始查找
                while (current) {
                    if (current.data == data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }
                return -1
            }

            //update
            LinkedList.prototype.update = function (position, element) {
                //越界判断
                if (position < 0 || position >= this.length) return false
                //查找正确的节点
                let current = this.haed
                let index = 0
                while (index < position) {
                    index++
                    current = current.next
                }
                // 将position位置的node的data改为newdata
                current.data = element
                return true
            }

            //removeAt
            LinkedList.prototype.removeAt = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.haed
                //判断是否删除的为第一个节点
                if (position == 0) {
                    this.haed = this.haed.next
                } else {
                    let index = 0
                    let previous = null//前一个节点
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    //前一个节点的next指向，current的next
                    previous.next = current.next
                }
                this.length -= 1
                return current.data
            }

            // remove
            LinkedList.prototype.remove = function (data) {
                //获取data在列表中的数据
                let position = this.inexOf(data)
                //根据位置信息删除数据
                return this.removeAt(position)
            }
            LinkedList.prototype.isEmpty = function (data) {
                return this.length == 0
            }
            LinkedList.prototype.size = function () {
                return this.length
            }
        }

双向

    function DoublyLinkedList() {
            // 内置类：节点类
            function Node(data) {
                this.data = data
                this.next = null
                this.prev = null // 新添加的
            }
            //属性
            this.head = null
            this.tail = null
            this.length = 0
            // 定义相关操作方法
            // 在尾部追加数据
            DoublyLinkedList.prototype.append = function (element) {
                // 1.根据元素创建节点
                var newNode = new Node(element)

                // 2.判断列表是否为空列表
                if (this.head == null) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    this.tail.next = newNode
                    newNode.prev = this.tail
                    this.tail = newNode
                }

                // 3.length+1
                this.length++
            }

            // 正向遍历的方法
            DoublyLinkedList.prototype.forwardString = function () {
                //定义变量
                let current = this.head
                let forwardStr = ''

                // 依次向后遍历获取每一个节点
                while (current) {
                    forwardStr += "," + current.data
                    current = current.next
                }

                return forwardStr.slice(1)
            }

            // 反向遍历的方法
            DoublyLinkedList.prototype.reverseString = function () {
                var current = this.tail
                var reverseStr = ""
                // 依次向前遍历获取每一个节点
                while (current) {
                    reverseStr += "," + current.data
                    current = current.prev
                }

                return reverseStr.slice(1)
            }

            // 实现toString方法
            DoublyLinkedList.prototype.toString = function () {
                return this.forwardString()
            }

            // insert方法
            DoublyLinkedList.prototype.insert = function (position, element) {
                // 1.判断越界的问题
                if (position < 0 || position > this.length) return false
                //根据data创建新节点
                var newNode = new Node(element)
                //判断列表是否为空
                if (this.length == 0) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    //判断position是否为0
                    if (position == 0) {//第一个节点
                        //原来的第一个节点的prev=指向改变之后的第一个节点
                        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 {//其他情况
                        let current = this.head
                        let index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        //插入节点的下一个节点指针为查询到的下一个节点
                        newNode.next = current
                        //插入节点的上一个节点指针为查询到的上一个节点
                        newNode.prev = current.prev
                        // 上一个节下一个指针=当前节点  
                        current.prev.next = newNode
                        //查询到的上一个节指针=插入的节点
                        current.prev = newNode
                    }
                    this.length += 1
                    return true
                }
            }

            DoublyLinkedList.prototype.get = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.head
                let inde = 0
                while (inde++ < position) {
                    current = current.next
                }
                return current.data
            }

            // 根据元素获取链表中的位置
            DoublyLinkedList.prototype.indexOf = function (element) {
                // 1.定义变量, 保存信息
                let current = this.head
                let index = 0

                // 2.找到元素所在的位置
                while (current) {
                    if (current.element === element) {
                        return index
                    }
                    index++
                    current = current.next
                }

                // 3.来到这个位置, 说明没有找到, 则返回-1
                return -1
            }

            DoublyLinkedList.prototype.updata = function (position, data) {
                // 1.判断越界的问题
                if (position < 0 || position >= this.length) return false
                //寻找正确的节点
                let current = this.head
                let inde = 0
                while (inde++ < position) {
                    current = current.next
                }
                current.data = data
                return true

            }

            DoublyLinkedList.prototype.removeAt = function (position) {
                if (position < 0 || position >= this.length) return null
                let current = this.head
                //判断是否只有一个节点
                if (this.length == 1) {
                    this.head = null
                    this.tail = null
                } else {
                    //判断是否删除的是第一个节点
                    if (position == 0) {
                        //第一个节点的下一个节点的prev引用
                        this.head.next.prev = null
                        // 将指向头部的指向第二个节点
                        this.head = this.head.next
                    } else if (position == this.length - 1) { //最后的节点
                        current = this.tail
                        // 最后一个节点的前一个节点的next引用赋值null
                        this.tail.prev.next = null
                        // 最后一个节点为前一个节点
                        this.tail = this.tail.prev
                    } else {
                        let index = 0
                        while (index++ < position) {
                            current = current.next
                        }
                        //查询到的上一个节点的next指针等于查询到的下一个节点
                        current.prev.next = current.next
                        //查询到的下一个节点的prev等于查询到的上一个节点
                        current.next.prev = current.prev
                    }
                    this.length -= 1
                }
                return current.data
            }

            // 根据元素删除
            DoublyLinkedList.prototype.remove = function (element) {
                var index = this.indexOf(element)
                return this.removeAt(index)
            }
        }

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

前端技能

前端

数据结构