數據結構教程網盤鏈接_數據結構101：鏈接列表

數據結構教程網盤鏈接

by Kevin Turney

凱文·特尼(Kevin Turney)

Like stacks and queues, Linked Lists are a form of a sequential collection. It does not have to be in order. A Linked list is made up of independent nodes that may contain any type of data. Each node has a reference to the next node in the link.

像堆棧和隊列一樣，鏈接列表是順序集合的一種形式。它不一定是有序的。鏈接列表由可能包含任何類型的數據的獨立節點組成。每個節點都有對鏈接中下一個節點的引用。

We can emulate stacks and queues with linked lists. We can as well use it as a base to create or augment other data structures. With linked lists, our primary concerns are with fast insertions and deletions, which are more performant over arrays.

我們可以使用鏈接列表來模擬堆棧和隊列。我們也可以將其用作創建或擴充其他數據結構的基礎。對于鏈表，我們的主要關注點是快速插入和刪除，它們在數組上的性能更高。

The building block of this structure is a Node.

此結構的構建塊是節點。

const Node = function(value) {  this.value = value;  this.next = null;};

Our Node is built with two properties, a value to hold data, and next, a reference initially set to null. The next property is used to “point” to the next Node in the linking. One of the disadvantages of linked lists is that each reference requires a larger memory overhead than an array.

我們的Node具有兩個屬性，一個用于保存數據的value ， next是最初設置為null的引用。 next屬性用于“指向”鏈接中的下一個節點。鏈表的缺點之一是每個引用比數組需要更大的內存開銷。

實作 (Implementation)

const LinkedList = function(headvalue) {  // !! coerces a value to a Boolean  if (!!headvalue) {    return "Must provide an initial value for the first node"  } else {    this._head = new Node(headvalue);    this._tail = this.head;  }};

In our second constructor, we test for a value to provide for the first Node. If true, we proceed to create a new Node with the value passed and set the head to tail initially.

在第二個構造函數中，我們測試要提供給第一個Node的值。如果為true，我們將繼續使用傳遞的值創建一個新的Node，并將head最初設置為tail。

插入 (Insertion)

LinkedList.prototype.insertAfter = function(node, value) {  let newNode = new Node(value);  let oldNext = node.next;  newNode.next = oldNext;  node.next = newNode;  if (this._tail === node) {    this._tail = newNode;  }  return newNode;};

For this method, we create a new Node and adjust the references. The former next reference of the original node is now directed to newNode. The newNode’s next reference is “pointed” to what the previous node’s next was referring to. Finally, we check and reset the tail property.

對于此方法，我們創建一個新的Node并調整引用。現在將原始節點的前一個下一個引用定向到newNode。 newNode的下一個引用“指向”上一個節點的下一個引用。最后，我們檢查并重置tail屬性。

LinkedList.prototype.insertHead = function(value) {  let newHead = new Node(value);  let oldHead = this._head  newHead.next = oldHead;  this._head = newHead;  return this._head;};

LinkedList.prototype.appendToTail = function(value) {  let newTail = new Node(value);  this._tail.next = newTail;  this._tail = newTail;  return this._tail;};

Insertion at the beginning or end of a linked list is fast, operating in constant time. For this, we create a new node with a value and rearrange our reference variables. We reset the node which is now the head with insertHead or the tail with appendToTail.

快速插入鏈表的開頭或結尾，并且操作時間固定。為此，我們創建一個具有值的新節點，并重新排列參考變量。我們將節點重置為現在的頭，其頭為insertHead或尾部為appendToTail 。

These operations represent fast insertions for collections, push for stacks, and enqueue for queues. It may come to mind that unshift for arrays is the same. No, because with unshift all members of the collection must be moved one index over. This makes it a linear time operation.

這些操作表示對集合的快速插入，對堆棧的推送以及對隊列的排隊。可能會想到，數組的不變移位是相同的。不可以，因為在取消移位時，必須將集合的所有成員移到一個索引上。這使其成為線性時間操作。

刪除中 (Deletion)

LinkedList.prototype.removeAfter = function(node) {  let removedNode = node.next;  if (!!removedNode) {    return "Nothing to remove"  } else {    let newNext = removedNode.next    node.next = newNext;    removedNode.next = null; // dereference to null to free up memory    if (this._tail === removedNode) {      this._tail = node;    }  }  return removedNode;};

Starting with a test for a node to remove, we proceed to adjust the references. Dereferencing the removedNode and setting it to null is important. This frees up memory and avoids having multiple references to the same object.

從測試要刪除的節點開始，我們繼續調整引用。 removedNode引用removedNode并將其設置為null很重要。這樣可以釋放內存，并避免對同一對象有多個引用。

LinkedList.prototype.removeHead = function() {  let oldHead = this._head;  let newHead = this._head.next;  this._head = newHead;  oldHead.next = null;  return this._head;};

Deletion of a head and of a specified node in, removeAfter, are constant time removals. In addition, if the value of the tail is known, then tail removal can be done in O(1). Else we have to move linearly to the end to remove it, O(N);

刪除頭和指定節點中的removeAfter是恒定時間刪除。另外，如果知道尾巴的值，則可以在O(1)中進行尾巴去除。否則，我們必須線性移動到最后才能將其刪除，O(N);

循環播放 (Looping and forEach)

We use the following to iterate through a linked list or to operate on each node value.

我們使用以下內容迭代鏈接列表或對每個節點值進行操作。

LinkedList.prototype.findNode = function(value) {  let node = this._head;  while(node) {    if (node.value === value) {      return node;    }    node = node.next;  }  return `No node with ${value} found`;};

LinkedList.prototype.forEach = function(callback) {  let node = this._head;  while(node) {    callback(node.value);    node = node.next;  }};

LinkedList.prototype.print = function() {  let results = [];  this.forEach(function(value) {    result.push(value);  });  return result.join(', ');};

The main advantage of Linked Lists is fast insertions and deletions without rearranging items or reallocation of space. When we use an array, the memory space is contiguous, meaning we keep it all together. With linked lists, we can have memory spaces all over the place, non-contiguous storage through the use of references. For arrays, that locality of references means that arrays have better caching of values for faster lookup. With linked lists, caching is not optimized and access time takes longer.

鏈接列表的主要優點是快速插入和刪除，而無需重新排列項目或重新分配空間。當我們使用數組時，內存空間是連續的，這意味著我們將它們保持在一起。使用鏈表，我們可以在各處擁有存儲空間，通過使用引用可以實現非連續存儲。對于數組，引用的局部性意味著數組可以更好地緩存值以加快查找速度。使用鏈接列表時，無法優化緩存，并且訪問時間會更長。

Another aspect of linked lists is different types of configuration. Two primary examples are circularly linked, where the tail has a reference to the head and the head to the tail. Doubly linked is when, in addition to the node having a reference to the next node, also has a reference looking back to the previous node.

鏈表的另一方面是不同類型的配置。兩個主要的示例是循環鏈接的，其中，尾部引用了頭部，頭部引用了尾部。雙鏈接是指除了該節點具有對下一個節點的引用之外，還具有回溯到前一個節點的引用。