JS基础--链表

链表

链表优于数组?

数组的缺点

书上是这样说的

JavaScript 中数组的主要问题是,它们被实现成了对象,与其他语言(比如 C++ 和 Java) 的数组相比,效率很低(请参考 Crockford 那本书的第 6 章)。

如果你发现数组在实际使用时很慢,就可以考虑使用链表来替代它。除了对数据的随机访 问,链表几乎可以用在任何可以使用一维数组的情况中。如果需要随机访问,数组仍然是更好的选择。

什么是链表?

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链

  • 数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用
  • 遍历链表,就是跟着 链接,从链表的首元素一直走到尾元素(但这不包含链表的头节点,头节点常常用来作为 链表的接入点)
  • 链表的尾元素指向一个 null 节点
  • 标识出链表的起始节点是在链表最前面有一个特殊节点,叫做头节点
  • 向链表中插入一个节点,需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点
  • 链表中删除元素,待删除元素的前驱节点指向待删除元素的后继节点,同时将待删除元素指向 null
链表的操作

设计的对象包含两个类

  • Node 类用来表示节点
  • LinkedList 类提供了插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法

Node类

  • element 用来保存节点上的数据,
  • next 用来保存指向下一个节点的链接
function Node(element) {
        this.element = element;
        this.next = null;
}

//head 节点的 next 属性被初始化为 null,当有新元素插入时,next 会指向新的元素,所以在这里没有修改 next 的值

LinkedList类

function List() {
    this.head = new Node("head"); 
    this.find = find;
    this.insert = insert; 
    this.remove = remove; 
    this.display = display;
}

  • 插入新节点

向链表中插入新节点 时,需要明确指出要在哪个节点前面或后面插入

在一个已知节点后面插入元素时,先要找到“后面”的节点。为此,创建一个辅助方法 find(),该方法遍历链表,查找给定数据。如果找到数据,该方法就返回保存该数据的节点

 function find(item) {
        var currNode = this.head;
        while (currNode.element != item) {
           currNode = currNode.next;
        }
        return currNode;
     }

find函数的原理:创建一个新节点,并将链表的头节点赋 给这个新创建的节点。然后在链表上进行循环,如果当前节点的 element 属性和要找的信息不符,就从当前节点移动到下一个节点。如果查找成功,该方法返回包含该数据的节点;否则返回 null

找到之后开始写插入

function insert(newElement, item) { 
    var newNode = new Node(newElement); 
    var current = this.find(item); 
    newNode.next = current.next; 
    current.next = newNode;
}

insert原理:将新节点的 next 属性设 置为“后面”节点的 next 属性对应的值。然后设置“后面”节点的 next 属性指向新节点

再写一个显示链表中的元素的方法

function display() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
           print(currNode.next.element);
           currNode = currNode.next;
        }
}

display方法先将列表的头节点赋给一个变量,然后循环遍历链表,当前节点的 next 属性为 null 时循环结束。

为了只显示包含数据的节点(换句话说,不显示头节点),程序只访问当前节点的下一个节点中保存的数据:

currNode.next.element
  • 删除节点

从链表中删除节点时,需要先找到待删除节点前面的节点。找到这个节点后,修改它的 next 属性,使其不再指向待删除节点,而是指向待删除节点的下一个节点,定义 一个方法 findPrevious(),来做这件事。该方法遍历链表中的元素,检查每一个节点的下 一个节点中是否存储着待删除数据。如果找到,返回该节点(即“前一个”节点),这样 就可以修改它的 next 属性了

function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == null) &&
       (currNode.next.element != item)) {
           currNode = currNode.next;
    }
    return currNode;
}

function remove(item) {
        var prevNode = this.findPrevious(item);
        if (!(prevNode.next == null)) {
            prevNode.next = prevNode.next.next;
        }
}

该方法中最重要的一行代码: prevNode.next = prevNode.next.next 跳过了待删除节点,让“前一个”节点指向了待删除节点的后一个节点。

双向链表

从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历则没那么简单。通过 给 Node 对象增加一个属性,该属性存储指向前驱节点的链接,这样就容易多了。此时向链 表插入一个节点需要更多的工作,需要指出该节点正确的前驱和后继。但是在从链表 中删除节点时,效率提高了,不需要再查找待删除节点的前驱节点了

为 Node 类增加一个 previous 属性

function Node(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
}

双向链表的 insert() 方法和单向链表的类似,但是需要设置新节点的 previous 属性,使 其指向该节点的前驱


function insert(newElement, item) { 
    var newNode = new Node(newElement); 
    var current = this.find(item); 
    newNode.next = current.next; 
    newNode.previous = current; 
    current.next = newNode;
}

双向链表删除节点,原理:首先需要在链表中找出存储待删除数据的节点,然后设置该节点前驱的 next 属性,使其指向待删 除节点的后继;设置该节点后继的 previous 属性,使其指向待删除节点的前驱

function remove(item) {
    var currNode = this.find(item); 
    if (!(currNode.next == null)) {
           currNode.previous.next = currNode.next;
           currNode.next.previous = currNode.previous;
           currNode.next = null;
           currNode.previous = null;
    } 
}

为了完成以反序显示链表中元素这类任务,需要给双向链表增加一个工具方法,用来查找最后的节点,增加findLast方法找出了链表中的最后一个节点

function findLast() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
           currNode = currNode.next;
        }
        return currNode;
     }

有了这个工具方法,就可以写一个方法,反序显示双向链表中的元素。dispReverse

function dispReverse() {
    var currNode = this.head;
    currNode = this.findLast();
    while (!(currNode.previous == null)) {
           print(currNode.element);
           currNode = currNode.previous;
        }
}
  • 循环链表

循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身 head.next = head ,这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。换 句话说,链表的尾节点指向头节点,形成了一个循环链表

从后向前遍历链表,但是又不想付出额外代价来创建一个双向链表,那么就需要使用循环链表,从循环链表的尾节点向后移动,就等于从后向前遍历链表

创建循环链表,只需要修改 LList 类的构造函数:


function LList() {
    this.head = new Node("head"); 
    this.head.next = this.head; 
    this.find = find;
    this.insert = insert; 
    this.display = display; 
    this.findPrevious = findPrevious; 
    this.remove = remove;
}

只需要修改一处,就将单向链表变成了循环链表。但是其他一些方法需要修改才能工作正 常。比如,display() 就需要修改,原来的方式在循环链表里会陷入死循环。while 循环的 循环条件需要修改,需要检查头节点,当循环到头节点时退出循环

display修改如下:

     function display() {
        var currNode = this.head;
        while (!(currNode.next == null) &&
               !(currNode.next.element == "head")) {
           print(currNode.next.element);
           currNode = currNode.next;
         }
    }