JavaScript 数据结构与算法之美 - 线性表(数组、栈、队列、链表)(下)

简介: JavaScript 数据结构与算法之美 - 线性表(数组、栈、队列、链表)(下)

5. 链表


定义


  • 链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的,它是通过 指针零散的内存块 串连起来的。
  • 每个元素由一个存储元素本身的 节点 和一个指向下一个元素的 引用(也称指针或链接)组成。


简单的链接结构图:


微信图片_20220513133130.png


其中,data 中保存着数据,next 保存着下一个链表的引用。


上图中,我们说 data2 跟在 data1 后面,而不是说 data2 是链表中的第二个元素。值得注意的是,我们将链表的尾元素指向了 null 节点,表示链接结束的位置。


特点


  • 链表是通过指针将零散的内存块串连起来的

所以链表不支持 随机访问,如果要找特定的项,只能从头开始遍历,直到找到某个项。

所以访问的时间复杂度为 O(n)。


  • 高效的插入和删除

链表中插入或者删除一个数据,我们并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的,只需要考虑相邻结点的指针改变。

所以,在链表中插入和删除一个数据是非常快速的,时间复杂度为 O(1)。


三种最常见的链表结构,它们分别是:


  • 单链表
  • 双向链表
  • 循环链表


单链表


定义


微信图片_20220513133201.png


由于链表的起始点的确定比较麻烦,因此很多链表的实现都会在链表的最前面添加一个特殊的节点,称为 头节点,表示链表的头部。


经过改造,链表就成了如下的样子:


微信图片_20220513133222.png


针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以插入与删除的时间复杂度为 O(1)。


在 d2 节点后面插入 d4 节点:


微信图片_20220513133233.png


删除 d4 节点:


微信图片_20220513133245.png


实现


  • Node 类用来表示节点。
  • LinkedList 类提供插入节点、删除节点等一些操作。

单向链表的八种常用操作:

  • append(element):尾部添加元素。
  • insert(position, element):特定位置插入一个新的项。
  • removeAt(position):特定位置移除一项。
  • remove(element):移除一项。
  • indexOf(element):返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
  • isEmpty():如果链表中不包含任何元素,返回 true,如果链表长度大于 0,返回 false。
  • size():返回链表包含的元素个数,与数组的 length 属性类似。
  • getHead():返回链表的第一个元素。
  • toString():由于链表使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString() 方法,让其只输出元素的值。
  • print():打印链表的所有元素。


具体代码:


// 单链表
function SinglyLinkedList() {
    // 节点
    function Node(element) {
        this.element = element; // 当前节点的元素
        this.next = null; // 下一个节点指针
    }
    var length = 0; // 链表的长度
    var head = null; // 链表的头部节点
    // 向链表尾部添加一个新的节点
    this.append = function(element) {
        var node = new Node(element);
        var currentNode = head;
        // 判断是否为空链表
        if (head === null) {
            // 是空链表,就把当前节点作为头部节点
            head = node;
        } else {
            // 从 head 开始一直找到最后一个 node
            while (currentNode.next) {
                // 后面还有 node
                currentNode = currentNode.next;
            }
            // 把当前节点的 next 指针 指向 新的节点
            currentNode.next = node;
        }
        // 链表的长度加 1
        length++;
    };
    // 向链表特定位置插入一个新节点
    this.insert = function(position, element) {
        if (position < 0 && position > length) {
            // 越界
            return false;
        } else {
            var node = new Node(element);
            var index = 0;
            var currentNode = head;
            var previousNode;
            // 在最前插入节点
            if (position === 0) {
                node.next = currentNode;
                head = node;
            } else {
                // 循环找到位置
                while (index < position) {
                    index++;
                    previousNode = currentNode;
                    currentNode = currentNode.next;
                }
                // 把前一个节点的指针指向新节点,新节点的指针指向当前节点,保持连接性
                previousNode.next = node;
                node.next = currentNode;
            }
            length++;
            return true;
        }
    };
    // 从链表的特定位置移除一项
    this.removeAt = function(position) {
        if ((position < 0 && position >= length) || length === 0) {
            // 越界
            return false;
        } else {
            var currentNode = head;
            var index = 0;
            var previousNode;
            if (position === 0) {
                head = currentNode.next;
            } else {
                // 循环找到位置
                while (index < position) {
                    index++;
                    previousNode = currentNode;
                    currentNode = currentNode.next;
                }
                // 把当前节点的 next 指针 指向 当前节点的 next 指针,即是 删除了当前节点
                previousNode.next = currentNode.next;
            }
            length--;
            return true;
        }
    };
    // 从链表中移除指定项
    this.remove = function(element) {
        var index = this.indexOf(element);
        return this.removeAt(index);
    };
    // 返回元素在链表的索引,如果链表中没有该元素则返回 -1
    this.indexOf = function(element) {
        var currentNode = head;
        var index = 0;
        while (currentNode) {
            if (currentNode.element === element) {
                return index;
            }
            index++;
            currentNode = currentNode.next;
        }
        return -1;
    };
    // 如果链表中不包含任何元素,返回 true,如果链表长度大于 0,返回 false
    this.isEmpty = function() {
        return length === 0;
    };
    // 返回链表包含的元素个数,与数组的 length 属性类似
    this.size = function() {
        return length;
    };
    // 获取链表头部元素
    this.getHead = function() {
        return head.element;
    };
    // 由于链表使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString() 方法,让其只输出元素的值
    this.toString = function() {
        var currentNode = head;
        var string = '';
        while (currentNode) {
            string += ',' + currentNode.element;
            currentNode = currentNode.next;
        }
        return string.slice(1);
    };
    // 打印链表数据
    this.print = function() {
        console.log(this.toString());
    };
    // 获取整个链表
    this.list = function() {
        console.log('head: ', head);
        return head;
    };
}


测试:


// 创建单向链表实例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0)); // false
console.log(singlyLinked.isEmpty()); // true
singlyLinked.append('Tom');
singlyLinked.append('Peter');
singlyLinked.append('Paul');
singlyLinked.print(); // "Tom,Peter,Paul"
singlyLinked.insert(0, 'Susan');
singlyLinked.print(); // "Susan,Tom,Peter,Paul"
singlyLinked.insert(1, 'Jack');
singlyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(singlyLinked.getHead()); // "Susan"
console.log(singlyLinked.isEmpty()); // false
console.log(singlyLinked.indexOf('Peter')); // 3
console.log(singlyLinked.indexOf('Cris')); // -1
singlyLinked.remove('Tom');
singlyLinked.removeAt(2);
singlyLinked.print(); // "Susan,Jack,Paul"
singlyLinked.list(); // 具体控制台


整个链表数据在 JavaScript 里是怎样的呢 ?


为了看这个数据,特意写了个 list 函数:


// 获取整个链表
    this.list = function() {
        console.log('head: ', head);
        return head;
    };


重点上上面的最后一行代码: singlyLinked.list() ,打印的数据如下:


微信图片_20220513133408.png


所以,在 JavaScript 中,单链表的真实数据有点类似于对象,实际上是 Node 类生成的实例。


双向链表


单向链表只有一个方向,结点只有一个后继指针 next 指向后面的结点。

而双向链表,它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点。


微信图片_20220513133428.png


微信图片_20220513133441.png


微信图片_20220513133451.png


单向链表与又向链表比较


  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。

所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。

虽然两个指针比较浪费存储空间,但可以支持双向遍历,这样也带来了双向链表操作的灵活性。

  • 双向链表提供了两种迭代列表的方法:从头到尾,或者从尾到头

我们可以访问一个特定节点的下一个或前一个元素。

  • 在单向链表中,如果迭代链表时错过了要找的元素,就需要回到链表起点,重新开始迭代。
  • 在双向链表中,可以从任一节点,向前或向后迭代,这是双向链表的一个优点。
  • 所以,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。


实现


具体代码:


// 创建双向链表 DoublyLinkedList 类
function DoublyLinkedList() {
  function Node(element) {
    this.element = element; //当前节点的元素
    this.next = null; //下一个节点指针
    this.previous = null; //上一个节点指针
  }
  var length = 0; // 链表长度
  var head = null; // 链表头部
  var tail = null; // 链表尾部
  // 向链表尾部添加一个新的项
  this.append = function(element) {
    var node = new Node(element);
    var currentNode = tail;
    // 判断是否为空链表
    if (currentNode === null) {
      // 空链表
      head = node;
      tail = node;
    } else {
      currentNode.next = node;
      node.prev = currentNode;
      tail = node;
    }
    length++;
  };
  // 向链表特定位置插入一个新的项
  this.insert = function(position, element) {
    if (position < 0 && position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;
      if (position === 0) {
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.prev = node;
          head = node;
        }
      } else if (position === length) {
        this.append(element);
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = node;
        node.next = currentNode;
        node.prev = previousNode;
        currentNode.prev = node;
      }
      length++;
      return true;
    }
  };
  // 从链表的特定位置移除一项
  this.removeAt = function(position) {
    if ((position < 0 && position >= length) || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;
      if (position === 0) {
        // 移除第一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.prev = null;
        }
      } else if (position === length - 1) {
        // 移除最后一项
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.prev;
          tail.next = null;
        }
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        previousNode = currentNode.next.prev;
      }
      length--;
      return true;
    }
  };
  // 从链表中移除指定项
  this.remove = function(element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };
  // 返回元素在链表的索引,如果链表中没有该元素则返回 -1
  this.indexOf = function(element) {
    var currentNode = head;
    var index = 0;
    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }
      index++;
      currentNode = currentNode.next;
    }
    return -1;
  };
  // 如果链表中不包含任何元素,返回 true ,如果链表长度大于 0 ,返回 false
  this.isEmpty = function() {
    return length == 0;
  };
  // 返回链表包含的元素个数,与数组的 length 属性类似
  this.size = function() {
    return length;
  };
  // 获取链表头部元素
  this.getHead = function() {
    return head.element;
  };
  // 由于链表使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString() 方法,让其只输出元素的值
  this.toString = function() {
    var currentNode = head;
    var string = '';
    while (currentNode) {
      string += ',' + currentNode.element;
      currentNode = currentNode.next;
    }
    return string.slice(1);
  };
  this.print = function() {
    console.log(this.toString());
  };
  // 获取整个链表
  this.list = function() {
    console.log('head: ', head);
    return head;
  };
}


测试:


// 创建双向链表
var doublyLinked = new DoublyLinkedList();
console.log(doublyLinked.isEmpty()); // true
doublyLinked.append('Tom');
doublyLinked.append('Peter');
doublyLinked.append('Paul');
doublyLinked.print(); // "Tom,Peter,Paul"
doublyLinked.insert(0, 'Susan');
doublyLinked.print(); // "Susan,Tom,Peter,Paul"
doublyLinked.insert(1, 'Jack');
doublyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(doublyLinked.getHead()); // "Susan"
console.log(doublyLinked.isEmpty()); // false
console.log(doublyLinked.indexOf('Peter')); // 3
console.log(doublyLinked.indexOf('Cris')); // -1
doublyLinked.remove('Tom');
doublyLinked.removeAt(2);
doublyLinked.print(); // "Susan,Jack,Paul"
doublyLinked.list(); // 请看控制台输出


整个链表数据在 JavaScript 里是怎样的呢 ?


// 获取整个链表
  this.list = function() {
    console.log('head: ', head);
    return head;
  };


调用 doublyLinked.list(); .


控制台输出如下:


微信图片_20220513133555.png


链表代码实现的关键是弄清楚:前节点与后节点与边界。


循环链表


循环链表是一种特殊的单链表。


循环链表和单链表相似,节点类型都是一样。


唯一的区别是,在创建循环链表的时候,让其头节点的 next 属性指向它本身

即:


head.next = head;


这种行为会导致链表中每个节点的 next 属性都指向链表的头节点,换句话说,也就是链表的尾节点指向了头节点,形成了一个循环链表。如下图所示:


微信图片_20220513133623.png


循环链表:在单链表的基础上,将尾节点的指针指向头结点,就构成了一个循环链表。环形链表从任意一个节点开始,都可以遍历整个链表。


代码:


// 循环链表
function CircularLinkedList() {
    // 节点
    function Node(element) {
        this.element = element; // 当前节点的元素
        this.next = null; // 下一个节点指针
    }
    var length = 0,
        head = null;
    this.append = function(element) {
        var node = new Node(element),
            current;
        if (!head) {
            head = node;
            // 头的指针指向自己
            node.next = head;
        } else {
            current = head;
            while (current.next !== head) {
                current = current.next;
            }
            current.next = node;
            // 最后一个节点指向头节点
            node.next = head;
        }
        length++;
        return true;
    };
    this.insert = function(position, element) {
        if (position > -1 && position < length) {
            var node = new Node(element),
                index = 0,
                current = head,
                previous;
            if (position === 0) {
                // 头节点指向自己
                node.next = head;
                head = node;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = node;
                node.next = current;
            }
            length++;
            return true;
        } else {
            return false;
        }
    };
    this.removeAt = function(position) {
        if (position > -1 && position < length) {
            var current = head,
                previous,
                index = 0;
            if (position === 0) {
                head = current.next;
            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return false;
        }
    };
    this.remove = function(element) {
        var current = head,
            previous,
            indexCheck = 0;
        while (current && indexCheck < length) {
            if (current.element === element) {
                if (indexCheck == 0) {
                    head = current.next;
                    length--;
                    return true;
                } else {
                    previous.next = current.next;
                    length--;
                    return true;
                }
            } else {
                previous = current;
                current = current.next;
                indexCheck++;
            }
        }
        return false;
    };
    this.remove = function() {
        if (length === 0) {
            return false;
        }
        var current = head,
            previous,
            indexCheck = 0;
        if (length === 1) {
            head = null;
            length--;
            return current.element;
        }
        while (indexCheck++ < length) {
            previous = current;
            current = current.next;
        }
        previous.next = head;
        length--;
        return current.element;
    };
    this.indexOf = function(element) {
        var current = head,
            index = 0;
        while (current && index < length) {
            if (current.element === element) {
                return index;
            } else {
                index++;
                current = current.next;
            }
        }
        return -1;
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this.size = function() {
        return length;
    };
    // 由于链表使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString() 方法,让其只输出元素的值
    this.toString = function() {
        var current = head,
            string = '',
            indexCheck = 0;
        while (current && indexCheck < length) {
            string += ',' + current.element;
            current = current.next;
            indexCheck++;
        }
        return string.slice(1);
    };
    // 获取链表头部元素
    this.getHead = function() {
        return head.element;
    };
    // 打印链表数据
    this.print = function() {
        console.log(this.toString());
    };
    // 获取整个链表
    this.list = function() {
        console.log('head: ', head);
        return head;
    };
}


测试:


// 创建单向链表实例
var circularLinked = new CircularLinkedList();
console.log(circularLinked.removeAt(0)); // false
console.log(circularLinked.isEmpty()); // true
circularLinked.append('Tom');
circularLinked.append('Peter');
circularLinked.append('Paul');
circularLinked.print(); // "Tom,Peter,Paul"
circularLinked.insert(0, 'Susan');
circularLinked.print(); // "Susan,Tom,Peter,Paul"
circularLinked.insert(1, 'Jack');
circularLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(circularLinked.getHead()); // "Susan"
console.log(circularLinked.isEmpty()); // false
console.log(circularLinked.indexOf('Peter')); // 3
console.log(circularLinked.indexOf('Cris')); // -1
circularLinked.remove('Tom');
circularLinked.removeAt(2);
circularLinked.print(); // "Susan,Jack,Paul"
circularLinked.list(); // 具体控制台


整个链表数据在 JavaScript 里是怎样的呢 ?


// 获取整个链表
  this.list = function() {
    console.log('head: ', head);
    return head;
  };


调用 circularLinked.list() 。


控制台输出如下:


微信图片_20220513133736.png


你知道大家发现没有,为什么从 1 - 4 - 1 了,还有 next 节点,而且是还可以一直点 next ,重复的展开下去,这正是 循环 的原因。


链表总结


  • 写链表代码是最考验逻辑思维能力的,要熟练链表,只有 多写多练,没有捷径
  • 因为,链表代码到处都是指针的操作、边界条件的处理,稍有不慎就容易产生 Bug。
  • 链表代码写得好坏,可以看出一个人写代码是否够细心,考虑问题是否全面,思维是否缜密。
  • 所以,这也是很多面试官喜欢让人手写链表代码的原因。
  • 一定要自己写代码实现一下,才有效果。
相关文章
|
2天前
|
算法 C++
c++算法学习笔记 (14) 栈与队列
c++算法学习笔记 (14) 栈与队列
|
2天前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
3天前
|
算法 测试技术
【数据结构与算法 | 基础篇】环形数组模拟队列
【数据结构与算法 | 基础篇】环形数组模拟队列
|
3天前
|
算法 测试技术
【数据结构与算法 | 基础篇】单向循环链表实现队列
【数据结构与算法 | 基础篇】单向循环链表实现队列
|
3天前
|
存储 算法
【数据结构与算法 | 基础篇】[数组专题]力扣88
【数据结构与算法 | 基础篇】[数组专题]力扣88
|
3天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣82
【数据结构与算法 | 基础篇】[链表专题]力扣82
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
|
11天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)