谈谈前端对链表的理解
概念
链表是一种常见的基础数据结构，它由一系列节点（Node）组成，用于存储一连串的数据。
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
}
前端角度理解概念
将链表比作前端开发中的DOM（文档对象模型）树。
链表的每个节点就像是一个DOM元素。每个节点通常包含两部分：
- 数据部分（data）：就像DOM元素的内容或者属性，比如一个文本节点的内容或者一个元素的类名。
- 指针部分（next）：就像DOM元素的childNodes属性或者nextSibling属性，指向下一个节点。
链表的特点
-
动态大小： 链表的大小不是固定的，可以随时添加或者删除节点，就像随时在DOM中添加或移除元素一样。
-
顺序访问：链表的访问必须按顺序访问，不能直接访问中间的节点，需要从头部开始遍历，就像在DOM中，想要访问一个深层嵌套的元素，需要从根元素开始遍历。
-
内存分配：
链表的节点可以分散在内存中，它们不必连续存储，与数组不同，数组的元素必须连续存储。就好像DOM元素可以分布在HTML文档的不同位置。
链表与数组的不同
链表与数组在很多方面相似，但也有一些关键的区别：
- 链表： 大小动态，元素不连续存储，只能顺序访问元素。
- 数组： 具有固定的大小，元素连续存储在内存中，可以通过索引直接访问任何元素。
链表的基础操作,代码如下：
class ListNode{
constructor(value) {
this.value = value;
this.next = null;
}
}
let head = new ListNode(1)
head.next = new ListNode(2)
head.next.next = new ListNode(3)
head.next.next.next = new ListNode(4)
head.next.next.next.next = new ListNode(5)
// 遍历打印每一个节点
let current = head;
while(current !== null) {
console.log(current.value)// 1 2 3 4 5
current = current.next
}
// 新增节点
let newNode = new ListNode(6)
current = head;
while(current.next !== null) {
current = current.next
}
current.next = newNode
// 删除值为3的节点
current = head;
while(current.next !== null) {
if(current.next.value === 3) {
current.next = current.next.next
break;
}
current = current.next
}
数组的基本操作，代码如下：
let array = [1, 2, 3]
console.log(array[2])// 3
array[2] = 6;
console.log(array)// [ 1, 2, 6 ]
array.push(8)
console.log(array)// [ 1, 2, 6, 8 ]
array.pop()
console.log(array)// [ 1, 2, 6 ]
从代码示例上展示了链表和数组在操作上的主要区别：
- 数组通过索引直接访问元素，而链表需要从头开始遍历。
- 数组的大小是固定的，而链表的大小是动态的，可以根据需要添加和删除节点。
- 数组元素在内存中是连续存储的，链表元素则可能分散在内存中。
链表的经典案例：两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
代码实现：
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
}
function addTwoNumbers(l1: ListNode | null, l2 : ListNode | null): ListNode | null {
let dummy: ListNode = new ListNode(0)
let current: ListNode = dummy;
let carry: number = 0;
while(l1 !== null || l2 !== null || carry !== 0) {
// 计算当前位的和以及进位
let val1: number = l1 ? l1.val : 0;
let val2: number = l2 ? l2.val : 0;
let sum_val: number = val1 + val2 + carry;
carry = Math.floor(sum_val / 10)
// 将当前和的个位数添加到结果链表中
current.next = new ListNode(sum_val % 10);
current = current.next;
// 移动链表指针
if(l1) l1 = l1.next;
if(l2) l2 = l2.next;
}
return dummy.next;
}