Front-end advanced algorithm 4: Linked lists are so simple

The introduction

Linked lists are much more complex than arrays. First of all, linked lists do not require contiguous memory space. They are made up of a group of discrete memory blocks connected by Pointers. The most common types of linked lists are single, double, and circular.

The most important thing to learn a linked list is to draw lots of pictures and practice. There is no shortcut to follow. When faced with a linked list problem, Aquarius summarized the following five steps:

Determine the data structure to solve the problem: single, double, or circular lists, etc
Decide on the solution: How to solve the problem
Drawing realization: Drawing can help us find the loophole in our thinking (some thinking is not perfect)
Determine boundary conditions: Consider whether there are boundary problems in the solution and how to solve them
Code implementation: solve the problem to complete ✅

This article will give the common linked list (single linked list, double linked list and circular linked list) of the basic operation has been code implementation, and give the implementation ideas, these are linked list solution cornerstone, please be sure to master! ⛽ ️ ⛽ ️ ⛽ ️

A bonus leetcode question at the end!

Let’s start this section!! 👇 👇 👇

A single linked list

Single linked list structure:

function List () {
  / / the node
  let Node = function (element) {
    this.element = element
    this.next = null
  }
  // The initial head node is null
  let head = null
  
  // List length
  let length = 0
  / / operation
  this.getList = function() {return head}
  this.search = function(list, element) {}
  this.append = function(element) {}
  this.insert = function(position, element) {}
  this.remove = function(element){}
  this.isEmpty = function(){}
  this.size = function(){}}Copy the code

1. Add nodes:

** Determine the data structure to solve the problem: ** single linked list

Initialize a node (to be appended), traverse to the end of the chain, and insert the node after the end node

Drawing implementation:

Determine boundary conditions: When the linked list is null, head points directly to the node to be inserted without traversal

Code implementation:

function append (element) {
  let node = new Node(element),
      p = head
  if(! head){ head = node }else {
    while (p.next) {
      p = p.next
    }
    p.next = node
  }
  length += 1
}

/ / test
let list = new List()
for(let i = 0; i < 5; i+=1) {
  list.append(i)
}
Copy the code

Solve the problem ✅

2. Look for:

Determine the data structure to solve the problem: single linked list

If the value of the node is equal to the value to be searched, return true; otherwise, continue to traverse the next node, until the whole list is not found, return false

Drawing realization: very simple, the reader can try to draw

Determine boundary conditions: When the linked list is NULL, false can be returned

Code implementation:

// Check whether a node exists in the list
function search(element) {
  let p = head
  if(! p)return false
  while(p) {
    if (p.element === element) return true
    p = p.next
  }
  return false
}

/ / test
list.search(4) // true
list.search(11) // false
Copy the code

Solve the problem ✅

3. Insert:

Determine the data structure to solve the problem: single linked list

Initialize a node (node to be inserted), traverse to the node before position, and insert the node after the node

Drawing implementation:

Determine boundary conditions:

whenposition 为 0, the node will be inserted directlynode.nextPoint to thehead ， headPoint to thenodeOk, no need to traverse
When to insert positionposition < 0Or exceed the list lengthposition > length, are problematic, cannot be inserted, at this point directly returnnull, failed to insert

Code implementation:

// Inserts the successor node of position
function insert (position, element) {
  // Create an insert node
  let node = new createNode(element)
  if (position >= 0 && position <= length) {
    let prev = head, 
        curr = head,
        index = 0
    if(position === 0) {
      node.next = head
      head = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
    }
    length += 1
  } else {
    return null}}/ / test
list.insert(10)
Copy the code

Solve the problem ✅

4. Delete:

Determine the data structure to solve the problem: single linked list

Determine the solution idea: traverse the single linked list, find the node to be deleted, delete

Drawing implementation:

Determine boundary conditions: When the list is null, return

Code implementation:

// Delete the element node
function remove (element) {
  let p = head, prev = head
  if(! head)return
  while(p) {
    if(p.element === element) {
      p = p.next
      prev.next = p
    } else {
        prev = p
        p = p.next  
    }
  }
}
Copy the code

Solve the problem ✅

5. Complexity Analysis

Search: Search from the beginning node, time complexity O(n)

Insert or delete: The time complexity of inserting or deleting a node (successor node) after a node is O(1)

Linked list five steps is not very easy to use 😊, the following look at the double linked list 👇

Double linked lists

As the name implies, a singly linked list has only one direction, from the beginning node to the end node. Then a doubly linked list has two directions, from the end node to the end node:

function DoublyLinkedList() {
    let Node = function(element) {
        this.element = element
        // Precursors
        this.prev = null
        // Next pointer
        this.next = null
    }
    // The initial head node is null
  	let head = null
    // Add a tail node
    let tail = null
  
  	// List length
  	let length = 0
    / / operation
    this.search = function(element) {}
    this.insert = function(position, element) {}
    this.removeAt = function(position){}
    this.isEmpty = function(){ return length === 0 } 
    this.size = function(){ return length }
}
Copy the code

1. Insert node in position:

Determine the data structure to solve the problem: double linked lists

Initialize a node (node to be inserted), traverse the linked list to the node before position, and insert the node after the node position

Drawing implementation:

Determine boundary conditions:

If the position to be inserted is position < 0 or exceeds the length of the linked list position > length, the insert cannot be inserted. In this case, null is returned directly, and the insert fails

Code implementation:

// Inserts the successor node of position
function insert (position, element) {
  // Create an insert node
  let node = new Node(element)
  if (position >= 0 && position < length) {
    let prev = head, 
        curr = head,
        index = 0
    if(position === 0) {
      // Add in the first position
        if(! head) {// Note that this is different from singly linked lists
          head = node
          tail = node
        } else {
          / / the bidirectional
          node.next = head
          head.prev = node
          // head points to the new head node
          head = node
        }
    } else if(position === length) {
      // Insert to the tail node
      curr = tial
      curr.next = node
      node.prev = curr
      // tail points to the new tail node
      tail = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      // Insert after prev and before curr
      prev.next = node
      node.next = curr
      curr.prev = node
      node.prev = prev
    }
    length += 1
    return true
  } else {
    return false}}/ / test
list.insert(10)
Copy the code

Solve the problem ✅

2. Delete the:

Determine the data structure to solve the problem: double linked lists

Determine the solution idea: traverse the double-linked list, find the node to be deleted, delete

Drawing implementation:

Determine boundary conditions: When the list is null, return

Code implementation:

// Delete the node in position
function removeAt (position) {
  if (position >= 0 && position < length && length > 0) {
    let prev = head, 
        curr = head,
        index = 0
    if(position === 0) {
      // Remove the head node
        if(length === 1) { // There is only one node
          head = null
          tail = null
        } else {
          head = head.next
          head.prev = null}}else if(position === length- 1) {
      // Remove the tail node
      curr = tial
      tail = curr.prev
      tail.next = null
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      / / remove the curr
      prev.next = curr.next
      curr.next.prev = prev
    }
    length -= 1
    return curr.element
  } else {
    return null}}Copy the code

Solve the problem ✅

3. Look for:

A double-linked list lookup is similar to a single-linked list in that it iterates through the list and returns true if found, false if not found.

4. Complexity Analysis

Search: Search forerunner node or successor node time complexity is O(1), other nodes are still O(n)

Insert or delete: Insert or delete the time complexity of precursor node or successor node is O(1).

Circular singly linked lists

A circular singly linked list is a special singly linked list. The only difference between a singly linked list and a singly linked list is that the tail of the singly linked list points to NULL, while the tail of a circular singly linked list points to the head, which forms a end to end loop:

Since there are cyclic singly linked lists, there are also cyclic doubly linked lists, and the difference between a cyclic doubly linked list and a doubly linked list is:

Double linked listtail.next(tailIs the successor pointer tonullCircular double linked listtail.next 为 head
Double linked listhead.prev(headIs the precursor pointer tonullCircular double linked listhead.prev 为 tail

Take a circular single column table as an example

function CircularLinkedList() {
    let Node = function(element) {
        this.element = element
        // Next pointer
        this.next = null
    }
    // The initial head node is null
  	let head = null
  
  	// List length
  	let length = 0
    / / operation
    this.search = function(element) {}
    this.insert = function(positon, element) {}
    this.removeAt = function(position){}
    this.isEmpty = function(){ return length === 0 } 
    this.size = function(){ return length }
}
Copy the code

1. Insert after positon:

Determine the data structure for the solution: circular singly linked lists

Initialize a node (node to be inserted), traverse to the node before position, and insert the node after the node

Drawing implementation:

Determine boundary conditions:

whenposition 为 0, you need to traverse to the tail node, and then insert the node after the tail node, and change theheadPoint to the
When to insert positionposition < 0Or exceed the list lengthposition > length, are problematic, cannot be inserted, at this point directly returnnull, failed to insert

Code implementation:

// Inserts the successor node of position
function insert (position, element) {
  // Create an insert node
  let node = new createNode(element)
  if (position >= 0 && position <= length) {
    let prev = head, 
        curr = head,
        index = 0
    if(position === 0) {
      // Different from single linked list inserts
      while(index < length) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
      head = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
    }
    length += 1
  } else {
    return null}}/ / test
list.insert(10)
Copy the code

Solve the problem ✅

2. Look for:

This is similar to single-linked lists except that index++ < length is the end of the loop condition

// Check whether a node exists in the list
function search(element) {
  if(! head)return false
  let p = head, index = 0
  // The difference between a single list and a single list
  while(index++ < length) {
    if (p.element= = =element) return true
    p = p.next
  }
  return false} / / testlist.search(4) / /true
list.search(11) / /false
Copy the code

Solve the problem ✅

3. Delete:

This is similar to single-linked lists except that index++ < length is the end of the loop condition

// Delete the element node
function remove (element) {
  let p = head, prev = head, index = 0
  / / an empty list
  if(! head || )return
  // There is only one node and element is the same
  if(length === 1 && head.element === element){  
    head = null
    length-- 
    return  
  }
  while(index++ < length) {
    if(p.element= = =element) {
      p = p.next
      prev.next = p
      length --
    } else {
        prev = p
        p = p.next}}}Copy the code

Solve the problem ✅

4. Complexity analysis

Search: The circular list starts from any node to find the target node in O(n) time.

Insert or delete: It is the same as a single linked list, and the time complexity of insert and delete of subsequent nodes is O(1).

Leetcode21: merge two ordered lists

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example:

Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the code

Please submit your answers to github.com/sisterAn/Ja… “, so that more people can see, Aquarius will post his own solution tomorrow.

Five, past series

Front-end advanced algorithm 3: Learning the LRU algorithm from the browser cache elimination strategy and Vue’s keep-alive

Bottle jun front-end advanced algorithm camp first week summary

Front-end advanced algorithm 2: JavaScript array from Chrome V8 source code

Front-end advanced algorithm 1: How to analyze and count the execution efficiency and resource consumption of algorithms?

Six, know more front-end road friends, together with advanced front-end development

The first phase of front-end algorithm training camp is free 🎉🎉🎉, free yo!

Here, you can advance the front-end algorithm with like-minded friends (200+), from 0 to 1 to build a complete data structure and algorithm system.

Here, I not only introduce algorithms, but also combine algorithms with various front-end areas, including browsers, HTTP, V8, React, Vue source code, and so on.

Here, you can learn a big factory algorithm (Ali, Tencent, Baidu, byte, etc.) or leetcode every day, Aquarius will solve it the next day!

More benefits waiting for you to unlock 🔓🔓🔓!

Scan code to join [front-end algorithm exchange group exchange group], if the number of TWO-DIMENSIONAL code has reached the upper limit, you can scan the bottom two-dimensional code, in the public number “front-end bottle jun” reply “algorithm” automatically pull you into the group learning

Front-end advanced algorithm 4: Linked lists are so simple

The introduction

A single linked list

1. Add nodes:

2. Look for:

3. Insert:

4. Delete:

5. Complexity Analysis

Double linked lists

1. Insert node in position:

2. Delete the:

3. Look for:

4. Complexity Analysis

Circular singly linked lists

1. Insert after positon:

2. Look for:

3. Delete:

4. Complexity analysis

Leetcode21: merge two ordered lists

Five, past series

Six, know more front-end road friends, together with advanced front-end development

Related Posts

2021 Year-end Summary

Mysql base +select5 clause + subquery

Thoroughly understand BFC in CSS | More on The Challenge in August