Singly linked list

A linked list is a non-sequential and non-sequential storage structure on a physical storage unit. The logical order of data elements is realized through the link order of Pointers in the linked list. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time. Each node consists of two parts: a data field that stores data elements and a pointer field that stores the address of the next node. Compared to the linear table sequence structure, the operation is complex. Because they do not have to be stored sequentially, linked lists can be inserted to O(1) complexity, which is much faster than another linear sequential list, but it takes O(n) time to find a node or access a node with a specific number, whereas linear and sequential lists are O(logn) and O(1) respectively.

Simply put, each element in a linked list is not stored consecutively in memory. Each element has a node that stores itself and another reference to the next element (pointer /next), which forms a chain.

Insertion and deletion of nodes in a single linked list. Since each element in the list is not stored consecutively, the next node to be connected needs to be found in advance. If two links are directly disconnected, the reference will be lost

Linked list operation code demonstration

How do I make linked lists

// constructor
function NodeList(val, next) {
  this.val = val ? val : 0
  this.next = next ? next : null
}

// Create a linked list
function generateList(array) {
  let ret = new NodeList() // Virtual head node for easy return
  let cur = ret
  for (let i = 0; i < array.length; i++) {
    cur.next = new NodeList(array[i])
    cur = cur.next
  }
  return ret.next
}

const arr = [1.2.3.4.5]
const list = generateList(arr) / / 1 = > 2 = > 3 = 4 = > > 5
Copy the code

Insert the node

/ * * *@description: Insert node *@param {Number} index
 * @param {Number|String} val* /
function insertNode(index, val){
  let head = list
  while(head.val ! == index) {// Find the node
    head = head.next
  }
  const node = new NodeList(val) // Add the node to be inserted
  node.next = head.next // the x node is connected to the next node first
  head.next = node // Disconnect from node X at position 3
}
// Insert x node after 3
insertNode(3.'x') // list: 1=>2=>3=>x=>4=>5
Copy the code

Remove nodes


/ * * *@description: Deletes the node *@param {Number|String}* /
function deleteNode(val){
  let head = new NodeList()
  head.next = list
  while(head.next && head.next.val ! == val) {// Find the previous node of the node to be deleted
    head = head.next
  }
  head.next = head.next.next ? head.next.next : null
}
// Delete controller 3
deleteNode(3) // list: 1=>2=>x=>4=>5
Copy the code

Related algorithms 707. Designing linked lists

Circular (circular) lists

A circular list is a special single linked list. The only difference between a circular list and a single linked list is that its tail points back to the head of the list, so it is called a circular linked list.

Related algorithms 141. Circular linked lists

Use a double pointer that starts at the head of the list. One pointer moves forward one step at a time, and the other pointer moves forward two steps at a time. If at some point the two Pointers meet, then there is a ring in the list. Otherwise, if the fast pointer goes to the end of the list first, then there is no ring.

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    if(! head || ! head.next)return false
    var p = q = head
    while(q && q.next) { // Boundary condition, after the last loop, the fast pointer may already be at the end of the list
        p = p.next
        q = q.next.next
        if(p === q) return true
    }
    return false
};
Copy the code

Two-way linked list

Bidirectionally linked lists take up more memory than single-linked lists for storing the same data. Although it takes up more space, bidirectional linked lists are more flexible and efficient in dealing with problems such as searching for the last node according to known nodes and searching for ordered linked lists.

Classical linked list algorithm

Reverse linked lists 25. Reverse linked lists in groups of K 138. Copy linked lists with random Pointers

Linked list applications: LRU cache elimination algorithm

LRU: Least Recently Used

Implementation approach

Maintain a linked list. The closer you are to the end of the list, the earlier the data is accessed. When a new data is accessed, the list is traversed

  • If the data is in the list, it is removed from its original position and placed in the head of the list
  • If the data is not in the list, it is added directly to the head of the list, and the tail of the list needs to be removed if the cache is full

If you’re interested, you can do it yourself

— end —