欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构:JS封装单、双向链表

程序员文章站 2022-06-28 12:58:22
在这里我就不再介绍什么是单、双链表了,如果有不清楚定义的可以先了解再来学封装。1.单链表结构图:先来看看链表常见的操作:append(element):向列表尾部添加一个新的项insert(position, element):向列表的特定位置插入一个新的项。remove(element):从列表中移除一项。indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1。removeAt(position):从列表的特定位置移除一项。....

在这里我就不再介绍什么是单、双链表了,如果有不清楚定义的可以先了解再来学封装。

1.单链表

结构图:
数据结构:JS封装单、双向链表

先来看看链表常见的操作:

  • append(element):向列表尾部添加一个新的项

  • insert(position, element):向列表的特定位置插入一个新的项。

  • remove(element):从列表中移除一项。

  • indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1。

  • removeAt(position):从列表的特定位置移除一项。

  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false。

  • size():返回链表包含的元素个数。与数组的length属性类似。

  • toString():由于列表项使用了Node类,就需要重写继承自JavaScript对象默认的toString方法,让其只输出元素的值。

下面分析一下比较复杂的方法:

1.append():

考虑两种情况

  • 链表处于空状态
  • 链表不为空,需再其它节点后面追加节点

2.insert():

考虑两种情况

  • 在第一个位置插入。表示新添加的节点成为头节点,且新节点的next需指向之前的头结点。head也需指向新节点。
  • 在其它位置插入。首先声明两个变量记录着两个紧紧连接的节点,通过while循环,往下面找,找到正确位置后,将新节点的next指向下一个节点,将上一个节点的next指向新节点。

3.removeAt():

考虑两种情况

  • 移除第一项时:直接让head指向第二项(第一个节点没有引用指向,会被浏览器自动回收)
  • 移除其它信息项:同让使用两个变量存储前后紧紧连接的节点,通过while循环找到正确位置,直接使用previous的next指向current的next即可,current将会被自动回收。

单链表封装代码:

// 封装链表的构造函数
function LinkedList() {
    // 封装一个Node类, 用于保存每个节点信息
    function Node(element) {
        this.element = element
        this.next = null
    }

    // 链表中的属性
    this.length = 0
    this.head = null

    // 1.append方法
    LinkedList.prototype.append = function (element) {
        // 1.根据新元素创建节点
        var newNode = new Node(element)

        // 2.判断原来链表是否为空
        if (this.head === null) { // 链表尾空
            this.head = newNode
        } else { // 链表不为空
            // 2.1.定义变量, 保存当前找到的节点
            var current = this.head
            while (current.next) {
                current = current.next
            }

            // 2.2.找到最后一项, 将其next赋值为node
            current.next = newNode
        }

        // 3.链表长度增加1
        this.length++
    }

    // 2.toString方法
    LinkedList.prototype.toString = function () {
        // 1.定义两个变量
        var current = this.head
        var listString = ""

        // 2.循环获取链表中所有的元素
        while (current) {
            listString += "," + current.element
            current = current.next
        }

        // 3.返回最终结果
        return listString.slice(1)
    }

    // 3.insert方法
    LinkedList.prototype.insert = function (position, element) {
        // 1.检测越界问题: 越界插入失败
        if (position < 0 || position > this.length) return false

        // 2.定义变量, 保存信息
        var newNode = new Node(element)
        var current = this.head
        var previous = null
        index = 0

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

            newNode.next = current
            previous.next = newNode
        }

        // 4.length+1
        this.length++

        return true
    }

    // 4.removeAt方法
    LinkedList.prototype.removeAt = function (position) {
        // 1.检测越界问题: 越界移除失败, 返回null
        if (position < 0 || position >= this.length) return null

        // 2.定义变量, 保存信息
        var current = this.head
        var previous = null
        var index = 0

        // 3.判断是否是移除第一项
        if (position === 0) {
            this.head = current.next
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }

            previous.next = current.next
        }

        // 4.length-1
        this.length--

        // 5.返回移除的数据
        return current.element
    }

    // 5.indexOf方法
    LinkedList.prototype.indexOf = function (element) {
        // 1.定义变量, 保存信息
        var current = this.head
        index = 0

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

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

    // 6.remove方法
    LinkedList.prototype.remove = function (element) {
        var index = this.indexOf(element)
        return this.removeAt(index)
    }

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

    // 8.size方法
    LinkedList.prototype.size = function () {
        return this.length
    }

    // 9.getFirst方法
    LinkedList.prototype.getFirst = function () {
        return this.head.element
    }
}

2. 双向链表

结构图:
数据结构:JS封装单、双向链表
双向链表解决了单链表只能从单方向寻找元素的缺点,但双向链表的占用的空间更大。

完整代码:

// 创建双向链表的构造函数
function DoublyLinkedList() {
    // 创建节点构造函数
    function Node(element) {
        this.element = element
        this.next = null
        this.prev = null // 新添加的
    }

    // 定义属性
    this.length = 0
    this.head = null
    this.tail = null // 新添加的

    
    // 1.在尾部添加数据
    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++
    }

    // 2.在任意位置插入数据
    DoublyLinkedList.prototype.insert = function (position, element) {
        // 1.判断越界的问题
        if (position < 0 || position > this.length) return false

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

        // 3.判断插入的位置
        if (position === 0) { // 在第一个位置插入数据
            // 判断链表是否为空
            if (this.head == null) {
                this.head = newNode
                this.tail = newNode
            } else {
                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
            var previous = null

            // 查找正确的位置
            while (index++ < position) {
                previous = current
                current = current.next
            }

            // 交换节点的指向顺序
            newNode.next = current
            newNode.prev = previous
            current.prev = newNode
            previous.next = newNode
        }

        // 4.length+1
        this.length++

        return true
    }

    // 3.根据位置删除对应的元素
    DoublyLinkedList.prototype.removeAt = function (position) {
        // 1.判断越界的问题
        if (position < 0 || position >= this.length) return null

        // 2.判断移除的位置
        var current = this.head
        if (position === 0) {
            if (this.length == 1) {
                this.head = null
                this.tail = null
            } else {
                this.head = this.head.next
                this.head.prev = null
            }
        } else if (position === this.length -1) {
            current = this.tail
            this.tail = this.tail.prev
            this.tail.next = null
        } else {
            var index = 0
            var previous = null

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

            previous.next = current.next
            current.next.prev = previous
        }

        // 3.length-1
        this.length--

        return current.element
    }

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

        // 2.查找正确的信息
        while (current) {
            if (current.element === element) {
                return index
            }
            index++
            current = current.next
        }

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

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

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

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

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

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

    // 遍历方法的实现
    // 10.正向遍历的方法
    DoublyLinkedList.prototype.forwardString = function () {
        var current = this.head
        var forwardStr = ""

        while (current) {
            forwardStr += "," + current.element
            current = current.next
        }

        return forwardStr.slice(1)
    }

    // 11.反向遍历的方法
    DoublyLinkedList.prototype.reverseString = function () {
        var current = this.tail
        var reverseStr = ""

        while (current) {
            reverseStr += "," + current.element
            current = current.prev
        }

        return reverseStr.slice(1)
    }

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

本文地址:https://blog.csdn.net/weixin_43334673/article/details/109243779