1.认识链表

 

 

 

 

 

 

 

2.封装链表结构

 

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>单项链表</title>
</head>
<body>
    
    <script>
        // 封装链表类
        function LinkedList(){
            // 内部的类，节点类
            function Node(data){
                this.data=data
                this.next=null
            }
            // 属性
            this.head=null
            this.length=0
        }
    </script>
</body>
</html>

 

 

 

 

3.链表常见的操作

 

 

 

 

 

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    // 封装链表的构造函数
    function LinkedList() {
        // 封装一个Node类, 用于保存每个节点信息
        function Node(element) {
            this.element = element
            this.next = null
        }

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

        // 链表尾部追加元素方法
        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++
        }

        // 链表的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)
        }

        // 根据下标删除元素
        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
        }

        // 根据位置移除节点
        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
        }

        // 根据元素获取链表中的位置
        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
        }

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

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

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

        // 获取第一个节点
        LinkedList.prototype.getFirst = function () {
            return this.head.element
        }
    }

    // 测试链表
    // 1.创建链表
    var list = new LinkedList()

    // 2.追加元素
    list.append(15)
    list.append(10)
    list.append(20)

    // 3.打印链表的结果
    alert(list) // 15,10,20

    // 4.测试insert方法
    list.insert(0, 100)
    list.insert(4, 200)
    list.insert(2, 300)
    alert(list) // 100,15,300,10,20,200

    // 5.测试removeAt方法
    list.removeAt(0)
    list.removeAt(1)
    list.removeAt(3)
    alert(list)

    // 6.测试indexOf方法
//    alert(list.indexOf(15))
//    alert(list.indexOf(10))
//    alert(list.indexOf(20))
//    alert(list.indexOf(100))

    // 7.测试remove方法
    list.remove(15)
    alert(list)

    // 8.测试其他方法
    alert(list.isEmpty())
    alert(list.size())
    alert(list.getFirst())
</script>
</body>
</html>

 

 

 

双向链表

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>双向链表</title>
</head>
<body>
<script>
    // 创建双向链表的构造函数
    function DoublyLinkedList() {
        // 创建节点构造函数
        function Node(element) {
            this.element = element
            this.next = null
            this.prev = null // 新添加的
        }

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

        // 定义相关操作方法
        // 在尾部追加数据
        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.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
        }

        // 根据位置删除对应的元素
        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
        }

        // 根据元素获取在链表中的位置
        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
        }

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

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

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

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

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

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

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

            return forwardStr.slice(1)
        }

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

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

            return reverseStr.slice(1)
        }

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

    // 1.创建双向链表对象
    var list = new DoublyLinkedList()

    // 2.追加元素
    list.append("abc")
    list.append("cba")
    list.append("nba")
    list.append("mba")

    // 3.获取所有的遍历结果
    alert(list.forwardString()) // abc,cba,nba,mba
    alert(list.reverseString()) //
    alert(list) // abc,cba,nba,mba

    // 4.insert方法测试
    list.insert(0, "100")
    list.insert(2, "200")
    list.insert(6, "300")
    alert(list) // 100,abc,200,cba,nba,mba,300

    // 5.removeAt方法测试
    alert(list.removeAt(0)) // 100
    alert(list.removeAt(1)) // 200
    alert(list.removeAt(4)) // 300
    alert(list) // abc,cba,nba,mba

    // 6.indexOf方法测试
    alert(list.indexOf("abc")) // 0
    alert(list.indexOf("cba")) // 1
    alert(list.indexOf("nba")) // 2
    alert(list.indexOf("mba")) // 3

    // 7.remove方法测试
    alert(list.remove("abc")) // abc
    alert(list) // cba,nba,mba

    // 8.测试最后四个方法
    alert(list.getHead())
    alert(list.getTail())
    alert(list.isEmpty())
    alert(list.size())
    document.write('\u66f4\u591a\u6559\u7a0b\u8bf7\u8bbf\u95ee\u0020\u0069\u0074\u006a\u0063\u0038\u002e\u0063\u006f\u006d');
</script>
</body>
</html>

 

原文地址：http://www.cnblogs.com/hechunfeng/p/16812171.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性