JavaScript实现单向链表

介绍:

1. 链表和数组一样,可以用于存储一系列的元素,但是链表和数组的实现机制完全不同的

先了解一下数组

1. 要存储多个元素,数组(或称为列表) 可能是最常用的数据结构.
2. 几乎每一种编程语言都有默认实现的数组结构
3. 但是数组也有很多的缺点

• 数组的创建通常需要申请一段连续的内存空间(一整块的内容),并且大小是固定的(大多数语言就是),所以当当前的数组不能满足容量需求时,需要扩容.
• 数组开头或者中间位置插入数据的成本很高,需要进行大量元素的位移

链表的优势

1. 不同于数组,链表中的元素在内存中不必时连续的空间
2. 链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用(有些语言称为指针或者连接)组成

所以跟数组做一下比较,我们不难发现

1. 内存空间不是必须连续的,可以充分利用计算机的内存,实现灵活的内存动态管理
2. 链表不必在创建时就确定大小,并且大小可以无限延伸下去
3. 链表在插入和删除数据时,时间复杂度可以达到O(1),相对数组效率高很多

链表的缺点:

• 链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）。
• 无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
• 虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。

链表是什么?

链表类似于火车:有一个火车头,火车头连接一个节点,节点上面有乘客(类似于数据),并且这个节点会连接下一个节点,以此类推

看下面的图 更好理解:

链表结构的封装

封装类,无非就是类上面有哪些属性,另外有哪些方法

链表中的常见操作：

添加:

• append（element）：向链表尾部添加一个新的项；
• insert（position，element）：向链表的特定位置插入一个新的项；

获取:

• get（position）：获取对应位置的元素；
• indexOf（element）：返回元素在链表中的索引。如果链表中没有该元素就返回-1；

修改:

• update（position，element）：修改某个位置的元素；

删除:

• removeAt（position）：从链表的特定位置移除一项；
• remove（element）：从链表中移除一项；

其他:

• isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false,判断是否为空链表；
• size（）：返回链表包含的元素个数，与数组的length属性类似；
• toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值；

append(element) 方法的实现

向链表尾部追加数据可能有两种情况:

• 链表本身为空,新添加的数据时唯一的节点.
• 链表不为空,需要向其他节点后面追加节点.

当添加第一个节点的时候

1. 第一步创建节点
2. 第二步将head指针指向第一个节点

当已经有节点之后,再添加节点

1. 第一步创建节点
2. 第二步将上一个节点的next指向添加的节点
3. 判断节点上的next是否为空 为空表示是最后一个节点

js

代码解读

复制代码

// 封装链表类
        function LinkedList() {
            // 属性
            // 第一个节点
            this.head = null;
            // 记录链表的长度
            this.length = 0;
            // 内部类
            /**
            @param {data} - 数据
            @param {next} - 指向下一个节点的引用
            */
            function Node(data) {
                this.data = data
                this.next = null
            }
            LinkedList.prototype.append = function (data) {
                // 1.创建节点
                let newNode = new Node(data)
                // 2. 判断添加元素是否为第一个节点
                if (this.length == 0) { //是第一个节点
                    // 2.1 调整指针指向
                    this.head = newNode
                } else {// 3.不是第一个节点
                    // 找到最后一个节点
                    let current = this.head
                    while (current.next) {//当不为空的时候,一直往下重新赋值
                        // 直到current.next为空的时候 也就表示后面没有节点了
                        current = current.next
                    }
                    // 最后节点的next指向新的节点
                    current.next = newNode
                    this.length += 1
                }
            }
        }