JavaScript实现数据结构--链表、双向链表

单项链表

！单项链表的节点被分成两部分，第一部分保存或显示节点信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值null。

封装单项链表类

function Linklist() {

    //内部类，定义节点
    function Node(data) {
        this.data = data
        this.next = null
    }

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

    //        往链表追加元素的方法append()
    Linklist.prototype.append = function(data) {
        //1.创建节点
        var newNode = new Node(data)

        //2.判断链表是否为空
        if (this.length == 0) {
            //为空 head指向这个新节点
            this.head = newNode
        } else {
            //不为空 顺着head找到最后的节点(即next为null的)
            var current = this.head

            while (current.next) {
                current = current.next
            }
            //最后节点的next指向新节点
            current.next = newNode
        }

        this.length++
    }

    //toString()
    Linklist.prototype.toString = function() {
        var current = this.head
        var listString = ''

        while (current) {
            listString += current.data + ' '
            current = current.next
        }

        return listString
    }

    //往链表的指定位置插入位置insert()
    Linklist.prototype.insert = function(position, data) {
        //1.判断position是否合理
        if (position < 0 || position > this.length) return false

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

        //插入的情况
        if (position == 0) {
            newNode.next = this.head
            this.head = newNode
        } else {
            var index = 0
            var current = this.head //现指针
            var previous = null //旧指针

            //在没到position之前，一直顺着链表更新指针
            while (index++ < position) {
                previous = current
                current = current.next
            }

            newNode.next = current
            previous.next = newNode
        }

        this.length++

            return true
    }

    //获取某个位置的元素get()
    Linklist.prototype.get = function(position) {
        //判断是否越界
        if (position < 0 || position >= this.length) return null

        //获取对应位置的data
        var current = this.head
        var index = 0

        while (index++ < position) {
            current = current.next
        }

        return current.data
    }

    //获取指定元素的索引indexOf()
    Linklist.prototype.indexOf = function(data) {
        var current = this.head
        var index = 0

        while (current) {
            if (current.data == data) {
                return index
            } else {
                current = current.next
                index++
            }
        }
        return -1
    }

    //替换指定索引的元素update()
    Linklist.prototype.update = function(position, data) {
        //判断是否合理
        if (position < 0 || position >= this.length) return false

        var current = this.head
        var index = 0

        while (index++ < position) {
            current = current.next
        }
        current.data = data

        return true
    }

    //删除指定位置的元素removeAt()
    Linklist.prototype.removeAt = function(position) {

        if (position < 0 || position >= this.length) return null

        var current = this.head
        var previous = null
        var index = 0
        if (position == 0) {
            this.head = this.head.next
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }

            previous.next = current.next

        }
        this.length--
            //返回被删除的元素
            return current.data
    }

    //删除指定元素remove()
    Linklist.prototype.remove = function(data) {

        //获取索引
        var position = this.indexOf(data)

        //调用removeAt()
        return this.removeAt(position)
    }


    //判断是否为空isEmpty()
    Linklist.prototype.isEmpty = function() {
        if (this.length == 0) return true

        return false
    }

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

单项链表的使用

var link = new Linklist()

link.append('fff')
link.append('aaa')
link.append('nnn')

link.insert(2, 'bbb')

console.log(link.toString()); //fff aaa bbb nnn 

console.log(link.get(3)); //nnn

console.log(link.indexOf('nnn')); //3


link.update(2, 'ccc')
console.log(link.toString()); //fff aaa ccc nnn

console.log(link.removeAt(2)); //ccc
console.log(link.toString()); //fff aaa nnn


link.remove('fff')
console.log(link.toString()); //aaa nnn


console.log(link.isEmpty()); //false
console.log(link.size()); //2

双向链表

每个结点包含三部分，指向前一个结点的指针（prev），指向后一个节点的指针（next），以及自己的数据部分（data）

封装双向链表类

function BothwayLinkList() {

    //内部类
    function Node(data) {
        this.prev = null
        this.next = null
        this.data = data
    }

    this.head = null
    this.tail = null
    this.length = 0

    //链表尾部增加元素append()
    BothwayLinkList.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
        }

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


    //toString()
    BothwayLinkList.prototype.toString = function() {
        return this.backwardString()
    }

    //向前遍历的读取元素forwardString
    BothwayLinkList.prototype.forwardString = function() {

            var current = this.tail
            var forwardStr = ''

            while (current) {
                forwardStr += current.data + ' '
                current = current.prev
            }

            return forwardStr

        }
        //向后遍历的读取元素backwardString
    BothwayLinkList.prototype.backwardString = function() {
        var current = this.head
        var backwardStr = ''
        while (current) {
            backwardStr += current.data + ' '
            current = current.next
        }

        return backwardStr
    }

    //向指定位置插入元素insert()
    BothwayLinkList.prototype.insert = function(position, data) {
        //判断越界
        if (position < 0 || position > this.length) return false

        var newNode = new Node(data)

        //链表为空的情况
        if (this.length == 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            //插入到头部
            if (position == 0) {
                this.head.prev = newNode
                newNode.next = this.head
                this.head = newNode
            } else if (position == this.length) {
                //插入到尾部
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            } else {
                var index = 0
                var current = this.head
                while (index++ < position) {
                    current = current.next

                }
                newNode.prev = current.prev
                current.prev.next = newNode
                current.prev = newNode
                newNode.next = current
            }
        }

        this.length++

            return true
    }

    //获取指定位置的元素get()
    BothwayLinkList.prototype.get = function(position) {
        if (position < 0 || position >= this.length) return false


        if (this.length / 2 > position) {
            //说明position靠前，从前往后遍历
            var index = 0
            var current = this.head
            while (index++ < position) {
                current = current.next
            }

            //否则position靠后，从后往前遍历
        } else {
            var index = this.length - 1
            var current = this.tail
            while (index-- > position) {
                current = current.prev
            }
        }
        return current.data

    }

    //根据元素获取索引位置indexOf()
    BothwayLinkList.prototype.indexOf = function(data) {
        var index = 0
        var current = this.head

        while (current) {
            if (current.data == data) {
                return index
            }
            current = current.next
            index++
        }

        return -1
    }

    //更改替换指定位置的元素update()
    BothwayLinkList.prototype.update = function(position, data) {
        if (position < 0 || position >= this.length) return false

        if (this.length / 2 > position) {
            //说明position靠前，从前往后遍历
            var index = 0
            var current = this.head
            while (index++ < position) {
                current = current.next
            }

            //否则position靠后，从后往前遍历
        } else {
            var index = this.length - 1
            var current = this.tail
            while (index-- > position) {
                current = current.prev
            }
        }

        current.data = data
        return true
    }

    //删除指定位置的元素removeAt()
    BothwayLinkList.prototype.removeAt = function(position) {
        if (position < 0 || position >= this.length) return false


        var current = this.head

        if (this.length == 1) {
            this.head = null
            this.tail = null
        } else {
            if (position == 0) {
                this.head.next.prev = null
                this.head = this.head.next
            } else if (position == this.length - 1) {
                this.tail.prev.next = null
                this.tail = this.tail.prev
            } else {
                var index = 0
                while (index++ < position) {
                    current = current.next
                }
                current.prev.next = current.next
                current.next.prev = current.prev
            }
        }

        this.length--

            return current.data
    }

    //isEmpty()
    BothwayLinkList.prototype.isEmpty = function(position) {
        return this.length == 0
    }

    //获取长度size()
    BothwayLinkList.prototype.size = function(position) {
        return this.length
    }

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

    //获取链表最后一个元素getHead()
    BothwayLinkList.prototype.getTail = function(position) {
        return this.tail.data
    }
}

双向链表的使用

var bothway = new BothwayLinkList()

bothway.append('aaa')
bothway.append('bbb')
bothway.append('ccc')
bothway.append('ddd')

console.log(bothway.backwardString()); //aaa bbb ccc ddd 
console.log(bothway.forwardString()); //ddd ccc bbb aaa 

bothway.insert(1, 'ok')
console.log(bothway.toString()); //aaa ok bbb ccc ddd 

console.log(bothway.get(2)); //bbb
console.log(bothway.get(3)); //ccc

console.log(bothway.indexOf('ddd')); //4

bothway.update(2, 'yes')
console.log(bothway.toString()); //aaa ok yes ccc ddd


console.log(bothway.removeAt(3)); //ccc
console.log(bothway.toString()); //aaa ok yes ddd