JavaScript 原生提供了 Array 作为高效的动态顺序表实现，但为了理解底层原理，通常需要手动实现。链表则需要完全手动实现，因为 JavaScript 无内置链表结构。
以下分别提供两种数据结构的完整实现，包括基本操作（插入、删除、查找、遍历等），并附带说明。
1. 顺序表（基于数组的动态顺序表）
顺序表的核心是连续存储，使用数组实现
// 创建顺序表
const seqList = [];
// 添加元素
seqList.push(10);
seqList.push(20);
seqList.push(30);
// 在索引 1 处插入 15
seqList.splice(1, 0, 15); // [10, 15, 20, 30]
// 修改索引 2 处的元素
seqList[2] = 25; // [10, 15, 25, 30]
// 删除索引 0 处的元素
seqList.splice(0, 1); // [15, 25, 30]
// 输出长度和内容
console.log('长度:', seqList.length); // 3
console.log('内容:', seqList); // [15, 25, 30]
手动实现如下：
class SequentialList {
constructor(capacity = 10) {
this.data = new Array(capacity); // 存储元素
this.size = 0; // 当前元素个数
this.capacity = capacity; // 当前容量
}
// 获取长度
getSize() {
return this.size;
}
// 判断是否为空
isEmpty() {
return this.size === 0;
}
// 扩容（当 size === capacity 时）
resize(newCapacity) {
const newData = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
this.capacity = newCapacity;
}
// 在索引 index 处插入元素
add(index, element) {
if (index < 0 || index > this.size) {
throw new Error('索引越界');
}
if (this.size === this.capacity) {
this.resize(this.capacity * 2); // 扩容为两倍
}
// 从后向前移动元素
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
this.data[index] = element;
this.size++;
}
// 在末尾添加元素
append(element) {
this.add(this.size, element);
}
// 删除索引 index 处的元素并返回
remove(index) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
const removed = this.data[index];
// 从前向后移动元素
for (let i = index + 1; i < this.size; i++) {
this.data[i - 1] = this.data[i];
}
this.size--;
// 可选：缩容（避免频繁缩容，通常当 size == capacity / 4 时缩为一半）
if (this.size > 0 && this.size === Math.floor(this.capacity / 4)) {
this.resize(Math.floor(this.capacity / 2));
}
return removed;
}
// 获取索引处元素
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
return this.data[index];
}
// 设置索引处元素
set(index, element) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
this.data[index] = element;
}
// 遍历打印
print() {
let str = 'SequentialList: [';
for (let i = 0; i < this.size; i++) {
str += this.data[i];
if (i !== this.size - 1) str += ', ';
}
str += ']';
console.log(str);
}
}
// 使用示例
const seqList = new SequentialList();
seqList.append(1);
seqList.append(2);
seqList.add(1, 3);
seqList.print(); // SequentialList: [1, 3, 2]
2. 链表（单向链表）
链表使用节点分散存储，支持高效的插入和删除（O(1)），但随机访问较慢（O(n)）
// 节点类
class ListNode {
constructor(val = null, next = null) {
this.val = val;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = new ListNode(); // 虚拟头结点，便于操作
this.size = 0;
}
getSize() {
return this.size;
}
isEmpty() {
return this.size === 0;
}
// 在索引 index 处插入元素
add(index, element) {
if (index < 0 || index > this.size) {
throw new Error('索引越界');
}
let prev = this.head;
for (let i = 0; i < index; i++) {
prev = prev.next;
}
const node = new ListNode(element);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 在链表头部添加元素
addFirst(element) {
this.add(0, element);
}
// 在链表末尾添加元素
addLast(element) {
this.add(this.size, element);
}
// 获取索引处元素
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
let cur = this.head.next;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
// 设置索引处元素
set(index, element) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
let cur = this.head.next;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
cur.val = element;
}
// 删除索引处元素并返回
remove(index) {
if (index < 0 || index >= this.size) {
throw new Error('索引越界');
}
let prev = this.head;
for (let i = 0; i < index; i++) {
prev = prev.next;
}
const removedNode = prev.next;
prev.next = removedNode.next;
removedNode.next = null;
this.size--;
return removedNode.val;
}
// 遍历打印
print() {
let str = 'LinkedList: [';
let cur = this.head.next;
while (cur) {
str += cur.val;
if (cur.next) str += ' -> ';
cur = cur.next;
}
str += ']';
console.log(str);
}
}
// 使用示例
const linkedList = new LinkedList();
linkedList.addLast(1);
linkedList.addLast(2);
linkedList.add(1, 3);
linkedList.print(); // LinkedList: [1 -> 3 -> 2]
LRU 缓存的实现（使用双向链表 + HashMap）
LRU（Least Recently Used）缓存是一种常见的数据结构，用于实现固定容量缓存，当容量满时淘汰最近最少使用的元素。在 JavaScript 中，最高效的实现方式是结合双向链表（控制访问顺序）和Map（或对象）作为哈希表（实现 O(1) 访问）
JS实现：
class LRUCache {
/**
* 构造函数
* @param {number} capacity - 缓存的最大容量
*/
constructor(capacity) {
this.capacity = capacity; // 缓存容量
this.cache = new Map(); // 使用 Map 作为哈希表，保持插入顺序并支持 O(1) 操作
this.head = {}; // 双向链表的虚拟头节点
this.tail = {}; // 双向链表的虚拟尾节点
this.head.next = this.tail; // 初始化链表：head <-> tail
this.tail.prev = this.head;
}
/**
* 将节点移动到链表头部（表示最近使用）
* @private
* @param {Object} node - 要移动的节点
*/
_moveToHead(node) {
// 先从当前位置移除
node.prev.next = node.next;
node.next.prev = node.prev;
// 插入到头部
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
/**
* 从链表尾部移除节点（淘汰最久未使用的）
* @private
* @returns {Object} 被移除的节点
*/
_removeTail() {
const lastNode = this.tail.prev;
lastNode.prev.next = this.tail;
this.tail.prev = lastNode.prev;
return lastNode;
}
/**
* 获取缓存值
* @param {any} key - 键
* @returns {any} 值，如果不存在返回 -1
*/
get(key) {
const node = this.cache.get(key);
if (!node) {
return -1; // 未找到
}
// 刷新访问顺序：将节点移到头部
this._moveToHead(node);
return node.value;
}
/**
* 放入缓存
* @param {any} key - 键
* @param {any} value - 值
*/
put(key, value) {
const existingNode = this.cache.get(key);
if (existingNode) {
// 已存在：更新值并移到头部
existingNode.value = value;
this._moveToHead(existingNode);
} else {
// 不存在：创建新节点
const newNode = { key, value, prev: null, next: null };
this.cache.set(key, newNode);
// 插入到头部
newNode.next = this.head.next;
newNode.prev = this.head;
this.head.next.prev = newNode;
this.head.next = newNode;
// 检查容量是否超出
if (this.cache.size > this.capacity) {
const tailNode = this._removeTail(); // 移除尾部节点
this.cache.delete(tailNode.key); // 从哈希表中删除
}
}
}
// 可选：打印当前缓存顺序（用于调试）
printCache() {
const result = [];
let current = this.head.next;
while (current !== this.tail) {
result.push(`${current.key}:${current.value}`);
current = current.next;
}
console.log('LRU Cache (most recent -> least recent):', result.join(' -> '));
}
}
// 使用示例
const cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.printCache(); // 3:3 -> 2:2 -> 1:1
console.log(cache.get(2)); // 2（刷新顺序）
cache.printCache(); // 2:2 -> 3:3 -> 1:1
cache.put(4, 4); // 容量满，淘汰最久未使用的 1
cache.printCache(); // 4:4 -> 2:2 -> 3:3
TS实现
使用双向链表结合 Map（Map 在 TypeScript 中天然支持泛型）实现 O(1) 时间复杂度的 get 和 put 操作
// 双向链表节点接口
interface Node<K, V> {
key: K;
value: V;
prev: Node<K, V> | null;
next: Node<K, V> | null;
}
class LRUCache<K = number, V = number> {
private capacity: number; // 缓存容量
private cache: Map<K, Node<K, V>>; // 哈希表：键到节点的映射
private head: Node<K, V>; // 虚拟头节点
private tail: Node<K, V>; // 虚拟尾节点
constructor(capacity: number) {
this.capacity = capacity;
this.cache = new Map<K, Node<K, V>>();
this.head = { key: null as any, value: null as any, prev: null, next: null };
this.tail = { key: null as any, value: null as any, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 将节点移动到头部（最近使用）
private moveToHead(node: Node<K, V>): void {
// 从当前位置移除
node.prev!.next = node.next;
node.next!.prev = node.prev!;
// 插入头部
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
// 移除尾部节点（最久未使用）
private removeTail(): Node<K, V> {
const lastNode = this.tail.prev!;
lastNode.prev!.next = this.tail;
this.tail.prev = lastNode.prev;
return lastNode;
}
// 获取值
get(key: K): V | -1 {
const node = this.cache.get(key);
if (!node) {
return -1;
}
this.moveToHead(node); // 刷新访问顺序
return node.value;
}
// 放入键值对
put(key: K, value: V): void {
const existingNode = this.cache.get(key);
if (existingNode) {
existingNode.value = value; // 更新值
this.moveToHead(existingNode);
} else {
const newNode: Node<K, V> = { key, value, prev: null, next: null };
this.cache.set(key, newNode);
// 插入头部
newNode.next = this.head.next;
newNode.prev = this.head;
this.head.next!.prev = newNode;
this.head.next = newNode;
// 超出容量时淘汰
if (this.cache.size > this.capacity) {
const tailNode = this.removeTail();
this.cache.delete(tailNode.key);
}
}
}
// 调试：打印缓存顺序（最近 -> 最久）
printCache(): void {
const result: string[] = [];
let current = this.head.next;
while (current !== this.tail) {
result.push(`${current!.key}:${current!.value}`);
current = current!.next;
}
console.log('LRU Cache:', result.join(' -> '));
}
}
// 使用示例
const cache = new LRUCache<number, number>(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.printCache(); // 3:3 -> 2:2 -> 1:1
console.log(cache.get(2)); // 2
cache.printCache(); // 2:2 -> 3:3 -> 1:1
链表反转的实现
单向链表的反转实现，包括迭代和递归两种方式
JS实现
// 单向链表节点定义
class ListNode {
constructor(val = null, next = null) {
this.val = val;
this.next = next;
}
}
// 创建链表的辅助函数
function createLinkedList(arr) {
if (arr.length === 0) return null;
let head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
// 打印链表的辅助函数
function printLinkedList(head) {
const result = [];
let current = head;
while (current) {
result.push(current.val);
current = current.next;
}
console.log('LinkedList:', result.join(' -> '));
}
// 方法一：迭代反转（推荐，空间复杂度 O(1)）
function reverseListIterative(head) {
let prev = null; // 前驱指针
let current = head; // 当前指针
let next = null; // 临时存储下一节点
while (current !== null) {
next = current.next; // 保存下一节点
current.next = prev; // 反转指针
prev = current; // 前驱前进
current = next; // 当前前进
}
return prev; // prev 成为新头节点
}
// 方法二：递归反转
function reverseListRecursive(head) {
// 递归终止条件：空链表或只有一个节点
if (head === null || head.next === null) {
return head;
}
// 递归反转后续链表
const newHead = reverseListRecursive(head.next);
// 反转当前节点与下一节点的指向
head.next.next = head;
head.next = null;
return newHead; // 新头节点始终是原链表的尾节点
}
// 使用示例
const list = createLinkedList([1, 2, 3, 4, 5]);
printLinkedList(list); // 1 -> 2 -> 3 -> 4 -> 5
const reversedIterative = reverseListIterative(list);
printLinkedList(reversedIterative); // 5 -> 4 -> 3 -> 2 -> 1
const list2 = createLinkedList([6, 7, 8]);
printLinkedList(list2); // 6 -> 7 -> 8
const reversedRecursive = reverseListRecursive(list2);
printLinkedList(reversedRecursive); // 8 -> 7 -> 6
TS实现
// 单向链表节点类型
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode) {
this.val = val ?? 0
this.next = next ?? null
}
}
// 创建链表辅助函数
function createLinkedList(arr: number[]): ListNode | null {
if (arr.length === 0) return null
const head = new ListNode(arr[0])
let current = head
for (let i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i])
current = current.next
}
return head
}
// 打印链表辅助函数
function printLinkedList(head: ListNode | null): void {
const result: number[] = []
let current = head
while (current) {
result.push(current.val)
current = current.next
}
console.log('LinkedList:', result.join(' -> '))
}
// 迭代反转（推荐，空间 O(1)）
function reverseListIterative(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null
let current: ListNode | null = head
while (current !== null) {
const next = current.next // 保存下一节点
current.next = prev // 反转指针
prev = current // 前驱前进
current = next // 当前前进
}
return prev // 新头节点
}
// 递归反转
function reverseListRecursive(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) {
return head
}
const newHead = reverseListRecursive(head.next)
head.next.next = head
head.next = null
return newHead
}
// 使用示例
const list = createLinkedList([1, 2, 3, 4, 5])
printLinkedList(list) // 1 -> 2 -> 3 -> 4 -> 5
const reversedIter = reverseListIterative(list)
printLinkedList(reversedIter) // 5 -> 4 -> 3 -> 2 -> 1
const list2 = createLinkedList([6, 7, 8])
const reversedRec = reverseListRecursive(list2)
printLinkedList(reversedRec) // 8 -> 7 -> 6
DFA:
- 顺序表：适合随机访问（O(1)），插入/删除较慢（O(n)），实现简单，内存连续
- 链表：适合频繁插入/删除（O(1)），随机访问慢（O(n)），内存分散，支持动态扩展, 链表常用于特定算法（如 LRU 缓存、链表反转等）