链表(Linked List)是一种基础的数据结构,由一系列节点(Node)组成,每个节点包含数据和指向下一个节点的引用。链表在插入和删除操作中具有较高的效率,广泛应用于实际开发中。
链表是一种线性数据结构,它的每个元素都是一个节点。每个节点包含两部分:
链表的类型
单向链表(Singly Linked List):每个节点只包含指向下一个节点的指针。
双向链表(Doubly Linked List):每个节点包含指向前一个节点和下一个节点的指针。
循环链表(Circular Linked List):单向或双向链表的最后一个节点指向头节点,形成一个环。
下面是一个简单的单向链表的实现,包括节点定义和基本操作:
// 定义节点类 class ListNode { constructor(value) { this.value = value; // 节点的值 this.next = null; // 指向下一个节点的指针,初始为 null } } // 定义单向链表类 class LinkedList { constructor() { this.head = null; // 链表头节点,初始为 null } // 在链表末尾添加节点 append(value) { const newNode = new ListNode(value); // 创建一个新的节点 if (this.head === null) { // 如果链表为空,新的节点作为头节点 this.head = newNode; } else { let current = this.head; while (current.next !== null) { // 遍历链表找到最后一个节点 current = current.next; } current.next = newNode; // 将新的节点添加到最后一个节点的 next } } // 在链表头部添加节点 prepend(value) { const newNode = new ListNode(value); // 创建一个新的节点 newNode.next = this.head; // 新节点的 next 指向当前的头节点 this.head = newNode; // 新节点作为头节点 } // 删除指定值的节点 delete(value) { if (this.head === null) return; // 如果链表为空,直接返回 // 如果头节点就是要删除的节点 if (this.head.value === value) { this.head = this.head.next; return; } let current = this.head; while (current.next !== null) { if (current.next.value === value) { // 找到要删除的节点 current.next = current.next.next; // 将要删除的节点移出链表 return; } current = current.next; } } // 打印链表 print() { let current = this.head; while (current !== null) { process.stdout.write(`${current.value} -> `); // 输出当前节点的值 current = current.next; } console.log('null'); // 表示链表结束 } } // 示例:使用单向链表 const list = new LinkedList(); list.append(1); list.append(2); list.append(3); list.prepend(0); list.print(); // 输出 0 -> 1 -> 2 -> 3 -> null list.delete(2); list.print(); // 输出 0 -> 1 -> 3 -> null
'运行
下面是一个简单的双向链表的实现,包括节点定义和基本操作:
// 定义双向节点类 class DoublyListNode { constructor(value) { this.value = value; // 节点的值 this.next = null; // 指向下一个节点的指针,初始为 null this.prev = null; // 指向前一个节点的指针,初始为 null } } // 定义双向链表类 class DoublyLinkedList { constructor() { this.head = null; // 链表头节点,初始为 null this.tail = null; // 链表尾节点,初始为 null } // 在链表末尾添加节点 append(value) { const newNode = new DoublyListNode(value); // 创建一个新的节点 if (this.tail === null) { // 如果链表为空,新的节点作为头和尾节点 this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; // 将新的节点添加到尾节点的 next newNode.prev = this.tail; // 新节点的 prev 指向当前的尾节点 this.tail = newNode; // 新节点作为新的尾节点 } } // 在链表头部添加节点 prepend(value) { const newNode = new DoublyListNode(value); // 创建一个新的节点 if (this.head === null) { // 如果链表为空,新的节点作为头和尾节点 this.head = newNode; this.tail = newNode; } else { this.head.prev = newNode; // 头节点的 prev 指向新的节点 newNode.next = this.head; // 新节点的 next 指向当前的头节点 this.head = newNode; // 新节点作为新的头节点 } } // 删除指定值的节点 delete(value) { if (this.head === null) return; // 如果链表为空,直接返回 // 如果头节点就是要删除的节点 if (this.head.value === value) { this.head = this.head.next; if (this.head !== null) { this.head.prev = null; } else { this.tail = null; // 如果链表为空,更新尾节点 } return; } let current = this.head; while (current !== null) { if (current.value === value) { // 找到要删除的节点 if (current.next !== null) { current.next.prev = current.prev; } else { this.tail = current.prev; // 更新尾节点 } current.prev.next = current.next; return; } current = current.next; } } // 打印链表 print() { let current = this.head; while (current !== null) { process.stdout.write(`${current.value} <-> `); // 输出当前节点的值 current = current.next; } console.log('null'); // 表示链表结束 } } // 示例:使用双向链表 const dList = new DoublyLinkedList(); dList.append(1); dList.append(2); dList.append(3); dList.prepend(0); dList.print(); // 输出 0 <-> 1 <-> 2 <-> 3 <-> null dList.delete(2); dList.print(); // 输出 0 <-> 1 <-> 3 <-> null
'运行
问题描述:反转一个单向链表。
/**
* 反转单向链表
* @param {LinkedList} list - 单向链表
* @returns {LinkedList} - 反转后的链表
*/
function reverseLinkedList(list) {
let prev = null;
let current = list.head;
while (current !== null) {
let next = current.next; // 暂存下一个节点
current.next = prev; // 将当前节点的 next 指向前一个节点
prev = current; // 更新前一个节点为当前节点
current = next; // 继续遍历下一个节点
}
list.head = prev; // 更新头节点为最后一个非空节点
return list;
}
// 示例:反转链表
const rList = new LinkedList();
rList.append(1);
rList.append(2);
rList.append(3);
rList.print(); // 输出 1 -> 2 -> 3 -> null
reverseLinkedList(rList);
rList.print(); // 输出 3 -> 2 -> 1 -> null
问题描述:合并两个有序链表,使结果链表仍然有序。
/**
* 合并两个有序链表
* @param {LinkedList} l1 - 第一个有序链表
* @param {LinkedList} l2 - 第二个有序链表
* @returns {LinkedList} - 合并后的有序链表
*/
function mergeTwoLists(l1, l2) {
let dummy = new ListNode(0); // 创建一个哨兵节点
let current = dummy;
let p1 = l1.head;
let p2 = l2.head;
// 遍历两个链表
while (p1 !== null && p2 !== null) {
if (p1.value < p2.value) {
current.next = p1; // 将较小值的节点添加到结果链表中
p1 = p1.next;
} else {
current.next = p2;
p2 = p2.next;
}
current = current.next;
}
// 将剩余的节点连接到结果链表中
if (p1 !== null) {
current.next = p1;
}
if (p2 !== null) {
current.next = p2;
}
let mergedList = new LinkedList();
mergedList.head = dummy.next; // 哨兵节点的 next 为合并后的头节点
return mergedList;
}
// 示例:合并两个有序链表
const list1 = new LinkedList();
list1.append(1);
list1.append(3);
list1.append(5);
const list2 = new LinkedList();
list2.append(2);
list2.append(4);
list2.append(6);
const mergedList = mergeTwoLists(list1, list2);
mergedList.print(); // 输出 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
链表是一种灵活的线性数据结构,适用于需要频繁插入和删除操作的场景。通过理解链表的基本操作和进阶操作,我们可以更好地应用链表来解决实际问题。在本文中,我们介绍了单向链表和双向链表的基本操作,以及链表的进阶操作,如反转链表和合并有序链表。希望通过本文的介绍,大家能够更好地理解和应用链表。