preface

Reading a lot of articles on the list, is also very serious back, but since there is no application layer to the understanding and usage scenario, the image is not deep, basically forgotten over time, not to mention understanding, a turn that the interviewer ask you understanding of the list How to do, fiber between nodes connect? How can queues be implemented? How can the cache area of node writable streams be implemented? I don’t want to add or delete elements by index without moving irrelevant elements, okay? So, specially to see the linked list of relevant knowledge and pseudo-code preparation, I hope that you are reading from my summary of the harvest

The list

What is the

1. Data stored in linear chained structures (linked lists) is often compared to data stored in linear sequential structures (arrays)

  • Linked list: A linked list is a discontinuous, nonsequential storage structure on a physical storage cell. The logical order of data elements is pointed to by next in the linked list. Linked lists are the opposite of arrays: they are slow to access elements and fast to add or delete them.
  • Arrays: Array order is determined by subscript, so accessing the elements of an array is fast; However, adding or deleting elements to an array requires moving other elements in the array forward or backward, which is slow
  • Linked list vs. array comparison: Arrays perform poorly in scenarios where there are many elements and elements are often added or removed, but not often accessed. In this scenario, you can use linked lists.

2. The linked list has many nodes. The first half of each node is a data field, and the second half is a pointer field (NEXT), which points to the next node

classification

  1. Unidirectional linked list: multiple nodes on which the next attribute of one node points to the next node. Next points to NULL if there is no next pointer

  2. Bidirectional linked list: the tail node’s Pre points to the previous node until the head node’s Pre points to NULL

  3. One-way circular list: On a single linked list basis the next of the last node points to the head node

  4. Bidirectional circular list: the pre of the head node points to the tail node, and the next of the tail node points to the head node

  5. Circular list: a list in which the pointer field next points to the next node, forming a ring.

Code implementation

Generate linked list nodes

/ / class Node {constructor(element, next) {this.element = element; this.next = next; }}Copy the code

Generate the list

Initialize header data. Constructor ()
/ / class LinkedList {constructor() {this.head = null; this.size = 0; Module. Exports = LinkedList;Copy the code
Add node Add ()

Ideas:

  1. When you add it, consider if it’s the first time you’re adding it,

  • Yes: Point head to the new node and next to null (next of the original head)

  • No: The next of the previous node points to itself

/** * @description * index: When you insert an element with only one argument, the default is the element to be added. Elemnt */ add(index, element) {if (arguments.length === 1) {// If (arguments. Length === 1) { Elemnt // index = this.size element = index; index = this.size; } let head = this.head; If (this.size === 0) {// If (this.size === 0) {next = null (next of original head) this.head = new Node(element, head); } else {this._node() let preNode = this._node(index-1); // The index starts at 0 and is always 1 less than the length. preNode) return; Prenode. next = new Node(element, prenode.next); } this.size++; }Copy the code
Get the previous node _node ()
_node(index) {let current = this.head; for (let i = 0; i < index; I ++) {// iterate until index current = current. Next; } return current; }Copy the code
Delete node remove()

Find the last node of the node to be deleted and make its next point to the next node (the node to which the current index points)

remove(index) { let removeNode; if (index === 0) { removeNode = this.head; if (removeNode ! == null) { this.head = this.head.next; this.size--; } } else { let preNode = this._node(index - 1); preNode.next = preNode.next.next; this.size--; } return removeNode; }Copy the code
Linked list reverse()
  • The recursive implementation
The reverse () {/ / recursion But in memory function r (head) {if (head = = = null | | head. The next = = = null) {return head; } let newHead = r(head.next); head.next.next = head; head.next = null; return newHead; } return r(this.head); }Copy the code
  • While loop implementation
reverse() { let head = this.head; if (head === null || head.next === null) { return head; } let newHead = null; while (head ! == null) { let temp = head.next; head.next = newHead; newHead = head; head = temp; } return newHead; }Copy the code
  • Summary: Having to discuss the pros and cons of both implementations recursion is a bit more memory intensive, because linked lists are often used to implement the underlying code, so performance considerations are more important, so a while loop is more appropriate

The instance test

let li = new LinkedList();
li.add(1);
li.add(2);
li.add(3);
li.add(4);
li.add(1, 200);

console.dir(li, { depth: 100 });
li.remove(2)
console.dir(li, { depth: 100 });
console.dir(li.reverse(), { depth: 100 });
Copy the code
  • The test results
  1. Print the linked list after continuous add

2. After node 2 is deleted, the size is 4. Node 2 does not exist

3. Reverse the list

Scenario Application – Queue generation

Const LinkedList = require(" list file location "); Constructor () {constructor() {// New LinkedList() = new LinkedList(); } poll() {// delete header let removeNode = this.ll.remove(0); return removeNode && removeNode.element; } offer(element) {// add this.ll.add(element); } } module.exports = Queue;Copy the code

Off topic: new(principle) constructor with () and no () difference ———

An argument with parentheses overloads the constructor. User-defined arguments passed in to the constructor are assigned to the instance’s own initialization defaults

conclusion

Common use scenarios for linked lists include

  1. LRU cache elimination algorithm
  2. Hash table for resolving hash conflicts
  3. All kinds of buffer pool and stack, queue implementation

In the next article I’ll share how to implement a writable flow in Node based on the queue implementation of the linked list

Finally, if you find this article helpful, please remember to like three times oh, thank you very much