数据结构——单向链表

一、链表

概念：

• 用于存储数据的线性结构  可存储多个元素

• 链表中的元素在内存中不必是连续的空间

• 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.

优缺点：

• 优点

  • 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.

  • 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.

  • 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.

• 缺点

  • 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).

  • 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的位置.

单向链表的结构：

二、程序封装单向链表

1.创建链表类：

//封装节点的结构
 class Lnode {
            constructor(data) {
               //保存每个节点信息
                this.data = data
                this.next = null
            }
        }
// 封装链表的结构
 class LinkList {
            constructor() {
               //链表中的属性
               this.length = 0  // 链表的长度
               this.head = null // 链表的第一个节点
            }

2.链表操作 ：

链表的常见操作：

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

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

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

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

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

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

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

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

 链表中的方法：

（1） append(element)：向列表尾部添加一个新的节点

 append(ele) {
                //创建一个新节点
                let newnode = new Lnode(ele)
                //链表为空时 新添加的节点为唯一的节点  头部直接指向新节点
                if (this.head == null) {
                    this.head = newnode
                } else {
                    //链表不为空时 向最后一个节点后面追加新节点
                     //定义变量, 保存当前找到的节点
                    let current = this.head
                    while (current.next != null) {
                        current = current.next
                    }
                    //current表示最后一个节点 将最后节点的next指向新节点 建立连接
                    current.next = newnode
                }
                //链表长度加1
                this.length++
            }

（2）insert(position, element)：向列表的特定位置插入一个新的节点

 insert(position, ele) {
                //判断位置是否合法（越界问题）
                if (position < 0 || position > this.length || Number.isInteger(position)) {
                    return false
                }
                let newnode = new Lnode(ele)
                //1.在头部插入
                if (position == 0) {
                    if (this.head == null) {
                        this.head = newnode
                    } else {
                        newnode.next = this.head
                        this.head = newnode
                    }
                    this.length++
                } else if (position == this.length) {
                  //2.在尾部插入
                    this.append(ele)
                } else {
                    //3.在中间位置插入
                    /*思路：
                      找到要插入的位置的前一个节点 position-1
                      首先先将新节点连上去 新节点next=current.next
                      将前一个的指向重新指向新节点 current.next=newnode 
                    */
                    let current = this.head
                    let index = 0
                    while (index < position - 1) {
                        current = current.next
                        index++
                    }
                    //while循环后的current就是前一个节点
                    //新节点的next指向 指向后一个节点
                    newnode.next = current.next
                    //前一个节点的next指向 指向新节点
                    current.next = newnode
                    this.length++
                }
            }

（3）removeAt(position)：从列表的特定位置移除节点

removeAt(position) {
                //判断位置是否合法（越界问题）
                if (position < 0 || position > this.length || Number.isInteger(position)) {
                    return false
                }
                if (this.head == null) {
                    return
                } else {
                    //非空链表
                    if (position == 0) {
                        //移除头部
                        this.head = this.head.next
                        this.length--
                    } else {
                        //移除任意位置(包括末尾)
                        let current = this.head,
                            index = 0
                        while (index < position - 1) {
                            current = current.next
                            index++
                        }
                        current.next = current.next.next
                    }
                    this.length--
                }
            }

（4）indexOf(element)：返回元素在列表中的索引  如果列表中没有该元素则返回-1

indexOf(ele) {
                let current = this.head,
                    index = 0
                while (index < this.length) {
                    if (current.data == ele) {
                        return index
                    } else {
                        current = current.next
                        index++
                    }
                }
                //找完了都没有 
                return -1
            }

（5）remove(element)：从列表中移除一个节点

remove(ele) {
                let index = this.indexOf(ele)
                return this.removeAt(index)
            }

（6）toString()： 将链表中的数据链接为字符串

   toString() {
                let current = this.head(),
                    index = 0,
                    res = ""
                while (index < this.length) {
                    res += "-" + current.data
                    current = current.next
                    index++
                }
                return res.slice(1)
            }

（7）isEmpty()：链表为空时返回true，链表长度大于0则返回false

isEmpty() {
                return this.length == 0
            }

（8）size()：返回链表包含的元素个数。与数组的length属性类似

size() {
                return this.length
            }