1688购物平台模版网站利于优化

当前位置： 首页 > news >正文

1688购物平台,模版网站利于优化,陕西网站备案代理,苏州市企业排名100强链表 链表 VS 数组链表类型链表基本操作 创建链表#xff1a;插入操作#xff1a;删除操作#xff1a;查找操作#xff1a;显示/打印链表#xff1a;反转链表#xff1a;合并两个有序链表#xff1a;链表基本操作示例 JavaScript中#xff0c;instanceof环形链表 判断…链表 链表 VS 数组链表类型链表基本操作 创建链表插入操作删除操作查找操作显示/打印链表反转链表合并两个有序链表链表基本操作示例 JavaScript中instanceof环形链表 判断是否存在环 – 快慢指针找出环的入口点计算环长 关于链表的前端算法题 141. 环形链表237. 删除链表中的节点83. 删除排序链表中的重复元素206. 反转链表 链表 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 typetext/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 constructorobject: 一个具体的对象实例。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。 找出环的入口点 在确认存在环之后可以通过以下方法找到环的入口 当快慢指针相遇时让其中一个指针保持不动另一个指针重新回到头节点并以相同的速度前进再次相遇的位置即为环的入口点。 计算环长 计算环长可以在确定了环的入口点后进行也可以在快慢指针第一次相遇后通过令它们按照一定的速度差继续移动并记录下走过的步数直到再次相遇所走的步数除以速度差即可得到环的长度。 环形链表的应用场景相对较少但也有其特点例如在某些同步原语和数据结构实现中可能有用武之地。 关于链表的前端算法题

1. 环形链表 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 headwhile(fast fast.next){fast fast.next.nextslow slow.nextif(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.valnode.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 (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }/ /** param {ListNode} head* return {ListNode}/ var deleteDuplicates function(head) {if(!head){return head}// 把当前的定义为一个变量let cur headwhile(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 (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }/ /** param {ListNode} head* return {ListNode}*/ var reverseList function (head) {// 定义头部和尾部let prev nulllet cur headwhile (cur) {const next cur.next // 暂存后继节点 cur.nextcur.next prev // 修改 next 引用指向prev cur // pre 暂存 curcur next // cur 访问下一节点}return prev };