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

单项链表

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

alt

封装单项链表类

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） alt

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

单项链表

封装单项链表类

单项链表的使用

双向链表

封装双向链表类

双向链表的使用

全站热榜

创作者周榜