【金秋打卡】第5天 JavaScript版数据结构与算法- 数据结构之“链表”

本文主要是介绍【金秋打卡】第5天 JavaScript版数据结构与算法- 数据结构之“链表”，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

课程名称: JavaScript版数据结构与算法
课程章节：第5章数据结构之“链表”
课程讲师： lewis
课程内容：

课程介绍
第5章数据结构之“链表”
5-1 链表简介(08:42)
5-2 LeetCode：237.删除链表中的节点(04:48)
5-3 LeetCode：206.反转链表(08:52)
5-4 LeetCode：2. 两数相加(12:39)
5-5 LeetCode：83. 删除排序链表中的重复元素(07:08)
5-6 LeetCode：141. 环形链表(09:05
5-7 前端与链表：JS 中的原型链(22:02)
5-8 前端与链表：使用链表指针获取 JSON 的节点值
5-9 链表-章节总结

一、什么是链表

链表
作为一名JAVA开始编程的产品，对链表还好有清晰的认识：
数组是连续存储在内存中的数据结构，因此它的优势是可以通过下标迅速的找到元素的位置，而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动，为了解决和平衡此问题于是就有了链表这种数据类型。
链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。
链表由一个个数据节点组成的，它是一个递归结构，要么它是空的，要么它存在一个指向另外一个数据节点的引用。

单纯看定义会觉得云里雾里不知所以,所以这里我们借用下面的一张图片直观的感受一下什么是链表。如下示范:

JS中不存在链表的数据结构，可以使用OBJECT进行模拟

二、链表的类型

2.1 分类

链表通常会分为以下三类：

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

1.单向链表

链表中最简单的一种是单向链表，或叫单链表，它包含两个域，一个数据域和一个指针域，指针域用于指向下一个节点，而最后一个节点则指向一个空值，如下图所示：

单链表的遍历方向单一，只能从链头一直遍历到链尾。它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。

接下来，我们用代码来实现一下单向链表的节点：

private static class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

2.双向链表

双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：

接下来，我们用代码来实现一下双向链表的节点：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}