十六、链表

文档参考

一、定义

链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链
由来**：**
数组其实是一种线性表的顺序存储结构，它的特点是用一组地址连续的存储单元依次存储数据元素。而它的缺点也正是其特点而造成，比如对数组做删除或者插入的时候，可能需要移动大量的元素。从而就引出了链表这种数据结构，链表不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，当然它也失去了数组在一块连续空间内随机存取的优点。

二、单向链表

特点：

• 用一组任意的内存空间去存储数据元素（这里的内存空间可以是连续的，也可以是不连续的）
• 每个节点(node)都由数据本身和一个指向后续节点的指针组成
• 整个链表的存取必须从头指针开始，头指针指向第一个节点
• 最后一个节点的指针指向空（NULL）

  代码：

  ```javascript class ListNode { constructor(key) { this.next = null; this.key = key; } }

class List { constructor() { this.head = null; this.length = 0; }

static createNode(key) { return new ListNode(key); }

// 往头部插入数据 insert(node) { // 如果head后面有指向的节点 if (this.head) { node.next = this.head; } else { node.next = null; } this.head = node; this.length++; }

find(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; }

delete(node) { if (this.length === 0) { throw ‘node is undefined’; }

if (node === this.head) {
  this.head = node.next;
  this.length--;
  return;
}
let prevNode = this.head;
while (prevNode.next !== node) {
  prevNode = prevNode.next;
}
if (node.next === null) {
  prevNode.next = null;
}
if (node.next) {
  prevNode.next = node.next;
}
this.length--;

} }

```javascript
<script>
        function Node(element) {
            this.element = element;
            this.next = null;//下一个节点
        }

        //链表类
        function LinkedList() {
            this.head = new Node("head");
        }

        //从链表中查询指定元素的方法
        LinkedList.prototype.find = function (item) {
            var currNode = this.head;
            while (currNode.next != null && currNode.element != item) {
                currNode = currNode.next;
            }
            return currNode;
        }

        //向链表里面追加元素的方法(在某个元素后面插入一个新的元素)
        LinkedList.prototype.insert = function (newElement, item) {
            var newNode = new Node(newElement);
            var current = this.find(item);
            newNode.next = current.next;
            current.next = newNode;
        }
        //找到某个item前面的元素
        LinkedList.prototype.findPrevious = function (item) {
            var currNode = this.head;
            while (currNode.next != null && currNode.next.element != item) {
                currNode = currNode.next;
            }
            return currNode;
        }
        //删除链表的某个元素
        LinkedList.prototype.remove = function (item) {
            var prevNode = this.findPrevious(item);
            if (!(prevNode.next == null)) {
                prevNode.next = prevNode.next.next;
            }
        }
        //修改链表的某个元素
        LinkedList.prototype.edit = function (item, newItem) {
            var node = this.find(item);
            node.element = newItem;
        }
        //在控制台输出链表中的元素
        LinkedList.prototype.display = function () {
            var currNode = this.head;
            console.log(currNode.element)
            while (currNode.next != null) {
                console.log(currNode.next.element);
                currNode = currNode.next;
            }
        }
        //判断链表是否有循环的方法
        LinkedList.prototype.hasCircle =  function() {
            var slowPointer = this.head;
            var fastPointer = this.head;
            while(fastPointer != null){
                slowPointer = slowPointer.next;
                fastPointer = fastPointer.next.next;
                if(slowPointer == fastPointer){
                    return true;
                }
            }
            return false;
        }

        //创建一个链表对象
        var list = new LinkedList();
        //向链表对象中追加元素
        list.insert("A");
        list.insert("B");
        list.insert("C");

        //判断链表是否有循环
        var cnode = list.find("C");
        var anode = list.find("A");
        cnode.next = anode;
        console.log(list.hasCircle())

    </script>

三、双向链表

代码：

 class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;

    if (node === this.head) {
      this.head = next;
    }

    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}

四、与数组的区别

1. 数组静态分配内存，链表动态分配内存；
2. 数组在内存中连续，链表不连续；
3. 数组元素在栈区，链表元素在堆区;
4. 数组查询快、增删慢；链表增删快、查询慢