假设理解 Big O 表示法。 JavaScript 中有示例。资料参考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》
链表是一种表示节点序列的数据结构。在单链表中，每个节点都指向下一个节点。
在内存中，这些节点不需要连续排序（彼此相邻），因为我们不依赖索引。当我们迭代链表时，我们会遍历节点的每个引用，直到遇到null指针。
在单链表中，每个节点通常包含两个字段：
head是对列表中第一个节点的引用。它很重要，因为它允许访问链表的开头。它有时充当哨兵节点（放置在实际头节点之前），以便更轻松地进行操作，例如在头部插入。尾部是对列表中最后一个节点的引用。它的下一个指针为空，表示列表的末尾。
与数组相比，链表在插入/删除方面具有更高的内存效率，因为这些操作不需要“移动”元素。从链表中的任意位置添加或删除元素的操作需要 O(1)时间。然而，这需要 O(n)最坏情况下遍历链表然后添加/删除元素的时间（不适用于添加/删除第一个元素）。
值得指出的是，由于每个节点中都存储了指针和数据，因此链表会产生额外的内存开销。
插入：
删除：
遍历/搜索： O(n)
class ListNode { constructor(val, nextNode = null) { this.val = val; this.next = nextNode; } } class LinkedList { constructor() { // sentinel node for easy operations on head this.head = new ListNode(-1); this.tail = this.head; } // get the value at the specified index. get(index) { let curr = this.head.next; let i = 0; while (curr !== null) { if (i === index) return curr.val; curr = curr.next; i++; } return -1; } // insert a new value at the head of the list. insertHead(val) { const newNode = new ListNode(val); newNode.next = this.head.next; this.head.next = newNode; if (newNode.next === null) { this.tail = newNode; } } // insert a new value at the tail of the list. insertTail(val) { const newNode = new ListNode(val); this.tail.next = newNode; this.tail = newNode; } // remove the node at the specified index. remove(index) { let curr = this.head; let i = 0; while (i < index && curr.next !== null) { i++; curr = curr.next; } if (curr !== null && curr.next !== null) { if (curr.next === this.tail) this.tail = curr; curr.next = curr.next.next; return true; } return false; } // get all values in the list as an array. getValues() { const values = []; let curr = this.head.next; while (curr !== null) { values.push(curr.val); curr = curr.next; } return values; } // get the length of the list. length() { let length = 0; let curr = this.head.next; while (curr !== null) { length++; curr = curr.next; } return length; } }
function ListNode(val, nextNode = null) { this.val = val; this.next = nextNode; } function LinkedList() { this.head = new ListNode(-1); // Sentinel node this.tail = this.head; } // get the value at the specified index LinkedList.prototype.get = function(index) { let curr = this.head.next; let i = 0; while (curr !== null) { if (i === index) return curr.val; curr = curr.next; i++; } return -1; }; // insert a new value at the head of the list LinkedList.prototype.insertHead = function(val) { const newNode = new ListNode(val); newNode.next = this.head.next; this.head.next = newNode; if (newNode.next === null) { this.tail = newNode; } }; // insert a new value at the tail of the list LinkedList.prototype.insertTail = function(val) { const newNode = new ListNode(val); this.tail.next = newNode; this.tail = newNode; }; // remove the node at the specified index LinkedList.prototype.remove = function(index) { let curr = this.head; let i = 0; while (i < index && curr.next !== null) { i++; curr = curr.next; } if (curr !== null && curr.next !== null) { if (curr.next === this.tail) this.tail = curr; curr.next = curr.next.next; return true; } return false; }; // get all values in the list as an array LinkedList.prototype.getValues = function() { const values = []; let curr = this.head.next; while (curr !== null) { values.push(curr.val); curr = curr.next; } return values; }; // get the length of the list LinkedList.prototype.length = function() { let length = 0; let curr = this.head.next; while (curr !== null) { length++; curr = curr.next; } return length; };
以上是实现单链表的详细内容。更多信息请关注PHP中文网其他相关文章！
