web前端算法简介之链表

发布时间：2024年01月14日

链表
JavaScript中，instanceof
环形链表
关于链表的前端算法题

链表

Javascript的原型链就是一个链表

链表是一种线性数据结构，它通过指针（在某些编程语言中可能是引用）将一系列的节点（元素）链接起来。

每个节点除了包含数据外，还包含一个指向下一个节点的指针，这样就形成了一个链式存储结构。

链表 VS 数组

相比于数组：

链表在内存中并 不需要是连续的空间，这使得它在插入和删除操作上具有一定的优势，尤其是在大数据量且频繁进行插入、删除操作的场景下。

访问链表中的元素（例如获取第k个节点的数据）通常比数组慢，因为链表需要从头节点开始逐个遍历。

链表和数组是两种基本且重要的数据结构，它们各自有各自的优点和适用场景：

数组：

存储方式：数组是在内存中连续存放的一系列元素，每个元素可以通过索引（下标）直接访问。
访问速度：由于数组的内存空间是连续的，因此可以使用索引在常量时间内（O(1)复杂度）随机访问任何位置的元素。
插入与删除：如果要在数组中间插入或删除元素，通常需要移动后续元素以保持连续性，这可能需要 O(n) 的时间复杂度，尤其是在最坏情况下（例如在数组头部插入或尾部删除时不需要移动其他元素）。
空间效率：数组预先分配了固定大小的空间，不灵活但通常比较节省空间，特别是当元素填充率高时。

链表：

存储方式：链表中的元素不必连续存储，每个节点包含数据和指向下一个节点的指针。
访问速度：链表访问任意元素的时间复杂度通常是线性的 O(n)，因为必须从头节点开始逐个遍历到目标节点。
插入与删除：链表可以在常量时间内（O(1)复杂度）进行插入和删除操作，只需要改变相应节点的指针即可。特别是在链表头部和尾部进行插入和删除操作时非常高效。
空间效率：链表在内存分配上较为灵活，可以根据需要动态添加或删除节点，但相比数组会额外消耗一些存储空间来保存指针信息。

总结来说：

如果程序需要频繁的查找操作或者对随机访问性能要求较高，数组是一个更好的选择。
当需要频繁执行插入和删除操作，尤其是列表结构变化较大时，链表由于其高效的插入删除特性更为合适。
在考虑缓存友好的场景下，数组由于其连续存储的特性更容易利用CPU缓存机制提高访问效率。

链表类型

链表主要分为以下几种类型：

单向链表：每个节点只有一个指针指向下一个节点。
双向链表：每个节点有两个指针，一个指向前一个节点，另一个指向后一个节点。
循环链表：单向或双向链表的最后一个节点的指针指向头节点，形成一个环状结构。
静态链表：在数组的基础上模拟实现链表，用数组下标表示前后节点的关系。

链表常用于实现各种高级数据结构，如栈、队列、哈希表等。

链表基本操作

链表的基本操作主要包括以下几种：

创建链表：

初始化一个空链表，即创建一个头节点（可能不存储数据，仅作为起点），并将其next指针设置为NULL（在C语言中）或None（在Python等语言中）。

插入操作：

在链表头部插入：创建新节点，将新节点的next指向原头节点，然后更新头节点为新节点。
在链表尾部插入：找到链表的尾节点（通过遍历或者维护尾指针实现），然后将尾节点的next指向新节点。
在链表中间插入：找到要插入位置的前一个节点，然后修改其next指针，使其指向新节点，新节点的next指针再指向原后继节点。

删除操作：

删除头节点：找到头节点的下一个节点，并将头节点更新为此节点。
删除尾节点：找到倒数第二个节点，将其next指针设置为NULL/None。
删除中间节点：找到待删除节点的前一个节点，将其next指针直接指向待删除节点的后继节点。

查找操作：

查找特定值：从头节点开始，逐个比较节点中的数据，直到找到匹配项或遍历完所有节点。

显示/打印链表：

从头节点开始，通过递归或循环遍历整个链表，并打印每个节点的数据。

反转链表：

可以通过迭代或递归的方式改变每个节点的next指针方向，使得链表反向。

合并两个有序链表：

创建一个新的头节点，然后依次比较两个链表的当前节点，将较小者添加到结果链表中，并移动对应的指针到下一个节点，直到某一个链表为空，再将另一个链表剩余部分连接到结果链表末尾。

以上是链表基本操作的主要内容，每种操作的具体实现会因编程语言和链表类型（单向、双向、循环链表）的不同而有所差异。

链表基本操作示例

在JavaScript中，链表的基本操作可以通过定义链表节点类（Node）和链表类（LinkedList）来实现。以下是一些基本操作的示例：

<script type="text/javascript">
let a = {key:'aaa'};
let b = {key:'bbb'};
let c = {key:'ccc'};
let d = {key:'ddd'};

a.next = b;
b.next = c; 
c.next = d;
d.next = null;

console.log( a ); 

//遍历链表
let obj = a;
while( obj && obj.key ){
	console.log( obj.key );
	obj = obj.next;
}

//链表中插入某个元素
let m = {key:'mmmmm'};
c.next = m;
m.next = d;
console.log( a );

//删除操作
c.next = d; 
</script>

定义链表节点类（Node）

class Node {
  constructor(element) { // 创建一个新节点，传入元素值
    this.element = element; // 节点存储的数据
    this.next = null; // 指向下一个节点的指针，默认为空
  }
}

定义链表类（LinkedList）

class LinkedList {
  constructor() {
    this.head = null; // 头节点，默认为空
  }

  // 基本操作方法：

  // 在链表头部插入节点
  insertAtBeginning(element) {
    const newNode = new Node(element);
    
    newNode.next = this.head;
    this.head = newNode;
  }

  // 在链表尾部插入节点
  append(element) {
    let currentNode = this.head;

    if (!currentNode) {
      this.head = new Node(element);
      return;
    }

    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }

    currentNode.next = new Node(element);
  }

  // 查找特定值的节点
  find(element) {
    let currentNode = this.head;
    while (currentNode !== null) {
      if (currentNode.element === element) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }
    return null; // 如果未找到则返回null
  }

  // 删除指定值的节点
  remove(element) {
    if (!this.head) return false; // 如果链表为空，直接返回

    if (this.head.element === element) {
      this.head = this.head.next;
      return true;
    }

    let prevNode = this.head;
    let currentNode = this.head.next;

    while (currentNode !== null) {
      if (currentNode.element === element) {
        prevNode.next = currentNode.next;
        return true;
      }
      prevNode = currentNode;
      currentNode = currentNode.next;
    }

    return false; // 如果未找到匹配项，则返回false
  }

  // 打印链表所有节点
  printList() {
    let currentNode = this.head;
    while (currentNode) {
      console.log(currentNode.element);
      currentNode = currentNode.next;
    }
  }
}

以上代码涵盖了链表的基本操作，包括创建链表、在头尾插入节点、查找节点、删除节点以及打印链表内容等。

根据需要，还可以扩展更多的链表操作方法，如反转链表、获取链表长度等。

更多详细内容，请微信搜索“前端爱好者“， 戳我查看 。

JavaScript中，`instanceof`

在JavaScript中，instanceof 是一个运算符，用于检测某个对象是否是某个构造函数的实例。其基本语法如下：

object instanceof constructor

object: 一个具体的对象实例。
constructor: 构造函数（类）。

这个运算符的工作原理是检查给定的对象在其原型链（prototype chain）上是否存在指定构造函数的 prototype 属性。

如果 constructor.prototype 在 object 的原型链上，则返回 true，否则返回 false。

例如：

function Animal(name) {
  this.name = name;
}

let dog = new Animal('Rex');

console.log(dog instanceof Animal); // 输出: true
console.log(dog instanceof Object); // 输出: true

// 因为所有的对象都继承自Object，所以所有实例都会在其原型链上找到Object.prototype

在这个例子中，dog 是通过 Animal 构造函数创建的，因此它是一个 Animal 类型的实例，并且因为 JavaScript 中的所有对象最终都会继承自 Object，所以 dog 同样也是 Object 的实例。

js实现

const instanceofs = (target,obj)=>{
	let p = target;
	while( p ){
		if( p == obj.prototype ){
			return true;
		}

		p = p.__proto__;
	}
	return false;
}

console.log( instanceofs( [1,2,3] , Object ) )

环形链表

环形链表（Circular Linked List）是一种特殊的链表结构，它与普通链表的主要区别在于最后一个节点的指针不再指向 null 或 None（在不同编程语言中表示空引用的方式不同），而是指向链表中的某个节点，形成一个闭环。

这种结构可以是 单向环形链表或 双向环形链表。

在环形链表中，如果从头节点开始沿着next指针一直遍历下去，将会无限循环地访问链表的节点，除非有一个机制来中断这个过程。

对于环形链表的操作，比如判断是否有环、找出环的入口点以及计算环长等，常常会用到如下的算法：

判断是否存在环： – 快慢指针

可以使用快慢指针（也称Floyd判圈法）。

设置两个指针，一个每次走一步（慢指针），另一个每次走两步（快指针）。如果链表中存在环，则快指针最终将追上慢指针；若不存在环，快指针将先到达终点（NULL）。

找出环的入口点：

在确认存在环之后，可以通过以下方法找到环的入口：

当快慢指针相遇时，让其中一个指针保持不动，另一个指针重新回到头节点并以相同的速度前进，再次相遇的位置即为环的入口点。

计算环长：

计算环长可以在确定了环的入口点后进行，也可以在快慢指针第一次相遇后，通过令它们按照一定的速度差继续移动，并记录下走过的步数直到再次相遇，所走的步数除以速度差即可得到环的长度。

环形链表的应用场景相对较少但也有其特点，例如在某些同步原语和数据结构实现中可能有用武之地。

关于链表的前端算法题

141. 环形链表

leetcode地址：https://leetcode.cn/problems/linked-list-cycle/description/

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

js代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
      let fast = slow = head
        while(fast && fast.next){
            fast = fast.next.next
            slow = slow.next
            if(fast === slow){
                return true
            }  
        }
        return false
};

237. 删除链表中的节点

leetcode地址： https://leetcode.cn/problems/delete-node-in-a-linked-list/description/

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将无法访问第一个节点 head。

链表的所有值都是唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。

自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
我们将构建链表，并将节点传递给你的函数。
输出将是调用你函数后的整个链表。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是 唯一 的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

分析

比如删掉 b 节点

由

{
	val:'a',
	next:{
		val:'b',
		next:{
			val:'c',
			next:{
				val:'d',
				next:null
			}
		}
	}
}

变成

{
	val:'a',
	next:{
		val:'c',
    next:{
      val:'d',
      next:null
    }
	}
}

js 实现源码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    // 原理是覆盖，后一个覆盖前一个
    node.val = node.next.val
    node.next= node.next.next
};

83. 删除排序链表中的重复元素

leetcode地址：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

js实现源码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(!head){
        return head
    }

    // 把当前的定义为一个变量
    let cur = head

    while(cur.next){
        // 如果当前值和后面值相同，则整个队列前移
        if(cur.val == cur.next.val){
            cur.next = cur.next.next
        } else {
            // 当前元素，继续向后移动
            cur = cur.next
        }
    }

    return head
};

206. 反转链表

leetcode地址：https://leetcode.cn/problems/reverse-linked-list/description/

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

js实现代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    // 定义头部和尾部
    let prev = null
    let cur = head

    while (cur) {
        const next = cur.next // 暂存后继节点 cur.next
        cur.next = prev //  修改 next 引用指向
        prev = cur // pre 暂存 cur
        cur = next // cur 访问下一节点
    }

    return prev
};

文章来源:https://blog.csdn.net/BradenHan/article/details/135541286
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

web前端算法简介之链表

链表

链表 VS 数组

链表类型

链表基本操作

创建链表：

插入操作：

删除操作：

查找操作：

显示/打印链表：

反转链表：

合并两个有序链表：

链表基本操作示例

JavaScript中，instanceof

环形链表

判断是否存在环： – 快慢指针

找出环的入口点：

计算环长：

关于链表的前端算法题

141. 环形链表

237. 删除链表中的节点

83. 删除排序链表中的重复元素

206. 反转链表

JavaScript中，`instanceof`