web前端算法简介之链表

发布时间:2024年01月14日

链表

Javascript的原型链就是一个链表

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

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

链表 VS 数组

相比于数组:

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

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

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

数组

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

链表

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

总结来说:

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

链表类型

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

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

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

链表基本操作

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

创建链表
  • 初始化一个空链表,即创建一个头节点(可能不存储数据,仅作为起点),并将其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.prototypeobject 的原型链上,则返回 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)是一种特殊的链表结构,它与普通链表的主要区别在于最后一个节点的指针不再指向 nullNone(在不同编程语言中表示空引用的方式不同),而是指向链表中的某个节点,形成一个闭环。

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

在环形链表中,如果从头节点开始沿着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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。