JavaScript数据结构之双向链表的封装

JavaScript数据结构之双向链表的封装

function DoublyLinkedList() {
    function Node(data) {
        this.next = null this.prev = null this.data = data
    }
    this.head = null this.tail = null this.length = 0 DoublyLinkedList.prototype.append = function(data) {
        var newNode = new Node(data) if (this.length === 0) {
            this.head = newNode this.tail = newNode
        } else {
            newNode.prev = this.tail this.tail.next = newNode this.tail = newNode
        }
        this.length++
    }
    DoublyLinkedList.prototype.toString = function() {
        return this.forwardString()
    }
    DoublyLinkedList.prototype.backwardString = function() {
        var current = this.tail
        var listString = ''
        while (current) {
            listString += current.data + ''current = current.prev
        }
        return listString
    }
    DoublyLinkedList.prototype.forwardString = function() {
        var current = this.head
        var listString = ''
        while (current) {
            listString += current.data + ''current = current.next
        }
        return listString
    }
    DoublyLinkedList.prototype.insert = function(data, position) {
        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) {
                newNode.next = this.head this.head.prev = newNode 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 previous = null
                var index = 0
                while (index++<position) {
                    previous = current current = current.next
                }
                newNode.next = current current.prev = newNode previous.next = newNode newNode.prev = previous
            }
        }
        this.length++
    }
    DoublyLinkedList.prototype.get = function(position) {
        if (position < 0 || position >= this.length) return null
        var index = 0
        var current = this.head
        while (index++<position) {
            current = current.next
        }
        return current
    }
    DoublyLinkedList.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
    }
    DoublyLinkedList.prototype.update = function(data, position) {
        if (position < 0 || position >= this.length) return false
        var index = 0
        var current = this.head
        while (index++<position) {
            current = current.next
        }
        current.data = data
        return true
    }
    DoublyLinkedList.prototype.removeAt = function(position) {
        if (position < 0 || position >= this.length) return null
        var index = 0
        var current = this.head
        var previous = null
        if (this.length === 1) {
            this.head = null this.tail = null
        } else {
            if (position === 0) {
                this.head = this.head.next this.head.next.prev = null
            } else if (position == this.length - 1) {
                current = this.tail this.tail = this.tail.prev this.tail.prev.next = null
            } else {
                while (index++<position) {
                    current = current.next
                }
                current.prev.next = current.next current.next.prev = current.prev
            }
        }
        this.length--
        return current.data
    }
    DoublyLinkedList.prototype.remove = function(data) {
        var position = this.indexOf(data) return this.removeAt(position)
    }
    DoublyLinkedList.prototype.isEmpty = function() {
        if (this.length) return true
        return false
    }
    DoublyLinkedList.prototype.size = function() {
        return this.length
    }
}

「点点赞赏,手留余香」

0

给作者打赏,鼓励TA抓紧创作!

微信微信 支付宝支付宝

还没有人赞赏,快来当第一个赞赏的人吧!

声明:
1. 本站所有文章教程及资源素材均来源于网络与用户分享或为本站原创,仅限用于学习和研究。
2. 如果内容损害你的权益请联系客服QQ:1642748312给予处理。
码云笔记 » JavaScript数据结构之双向链表的封装

发表评论

IT互联网行业相关广告投放 更专业 更精准

立即查看 联系我们