育贤网站建设,国外的设计网站app,盐山建网站,建网站培训学校链表简介
1.多个元素组成的列表。 2.元素的存储不连续#xff0c;用next指针连在一起。
数组 vs 列表
数组#xff1a;增删非手尾元素时往往需要移动元素。如果要在数组中增加一个元素#xff0c;数组后面的所有元素需要往后面移动一位。如果在数组中删除一个元素#x…链表简介
1.多个元素组成的列表。 2.元素的存储不连续用next指针连在一起。
数组 vs 列表
数组增删非手尾元素时往往需要移动元素。如果要在数组中增加一个元素数组后面的所有元素需要往后面移动一位。如果在数组中删除一个元素后面的元素都要往前移动一位。链表增删非首尾元素不需要移动元素只需要更改next指针。javascript中是没有链表数据结构但是可以使用Object模拟一个链表。
模拟链表数据结构(其实就是一个嵌套的Object)
const a {value: a}
const b {value: b}
const c {value: c}
const d {value: d}a.next b
b.next c
c.next d链表的操作
// 构建链表
const a {value: a}
const b {value: b}
const c {value: c}
const d {value: d}a.next b
b.next c
c.next d// 遍历链表
// 声明一个指针ppoint然后在循环里面更改pp.next,然后在这个位置就可以访问链表里面的元素了。
let p a
while(p) {console.log(p.value)p p.next
}// 插入(在cd中间插入一个e元素)
const e { value: e }
c.next e
e.next d// 删除e改变next指针
c.next dleetCode 237.删除链表中的节点
请编写一个函数使其可以删除某个链表中给定的非末尾节点。 var deleteNode function (node) {// 将被删除节点的值改为下一个节点的值。node.value node.next.val// 删除下个节点。node.next node.next.next
}时间复杂度O(1)
空间复杂度O(1)leetCode206.反转链表
反转一个单链表。 什么双指针遍历链表一个指针指向2一个指向1下一次指向2的指向3指向1的指向2
var reverseList function (head) {// p1指向头部p2指向nulllet p1 head;let p2 null;while(p1) {console.log(p1.val, p2 p2.val)// 临时保存p1, const temp p1.nextp1.next p2p2 p1p1 temp}return p2
}时间复杂度O(n)
空间复杂度O(1)因为循环过程中只有单个值既不是数组也不是矩阵leetCode 2.两数相加?
题目 var addTwoNumbers function (l1, l2) {const l3 new ListNode(0)let p1 l1;let p2 l2;let p3 l3;let carry 0while(p1 || p2) {const v1 p1 ? p1.val : 0;const v2 p2 ? p2.val : 0const val v1 v2 carrycarry Math.floor(val / 10)p3.next new ListNode(val % 10)if (p1) p1 p1.nextif (p2) p2 p2.nextp3 p3.next}if (carry) {p3.next new ListNode(carry)}return l3.next
}时间复杂度 O(n)n是两个链表的较大者
空间复杂度 O(n)没有数组矩阵但是存在链表所以也是O(n)n是两个链表的较大者leetCode 83.删除有序链表中重复的元素 const deleteNode function (head) {let p head;while(p p.next) {if(p.val p.next.val) {p.next p.next.next} else {p p.next}}return head
}
leetCode 141.环形链表
如何判断链表有环
var hasCycle function (head) {let p1 head;let p2 head;while(p1 p2 p2.next) {p1 p1.nextp2 p2.next.nextif (p1 p2) {return true}}return false
}js中的原型链
原型链本质上是一个链表原型链上的节点是各种原型对象例如Function.prototype, Object.prototype, …原型链通过__proto__属性连接各种原型对象。
原型链长什么样
obj -- Object.prototype -- null
func -- Function.prototype -- Object.prototype -- null
arr -- Array.prototype -- Object.prototype -- null
num -- Number.prototype -- Object.prototype -- null
str -- String.prototype -- Object.prototype -- null
func代表函数实例 obj代码对象实例 arr: 代码数组实例 num: 代码数字实例 str: 代码字符串实例
// 查看下面的原型链长什么样
const obj {}
obj.__proto__ Object.prototype
obj.__proto__: Object.prototype -- nullconst func () {}
obj.__proto__ Function.prototype
obj.__proto__: Function.prototype -- Object.prototype -- nullconst arr []
obj.__proto__ Array.prototype
obj.__proto__ : Array.prototype -- Object.prototype -- null原型链知识点
如果A沿着原型链能找到B.prototype那么A instanceof B 为true。如果在A对象上没有找到x属性那么就会沿着A的原型链找x属性。简述instanceof的原理遍历A的原型链如果找到B.prototype,返回true否则返回false
const instaceof function (A, B) {var p A;// 遍历原型链while(p) {if (p B.prototype) {return true}p p.__proto__}return false
} value a undefined value a value b
var foo {}
var F function () {};
Object.prototype.a value a
Function.prototype.a value a
console.log(foo.a)
console.log(foo.b)
console.log(F.a)
console.log(F.b)使用链表指针获取json的节点值
const json {a: {b: {c: 1}},d: {e: 2},
}
// 求根据path组成的路径的惊悚的值。
const path [a, b, c]// 解答
let p json
path.forEach((k) {p p[k]
})
console.log(p, p) // 1
总结
1.链表元素的存储不连续用next指针连在一起。 2.javascript中是没有链表数据结构但是可以使用Object模拟一个链表。 3.链表的常用操作修改next遍历链表。
技术要点 1.js中的原型链也是一个链表他是根据prototype指针走的。 2.使用链表指针可以获取json的节点值。
