Linked list of JavaScript data structures and algorithms

Introduction of the list

A linked list is a common data structure that is also a linear table, but does not store data in a linear order. Instead, in each node, the pointer to the next node is stored. You can see it in the picture. (Those with C language basics may be easier to understand).
Using the linked list structure can overcome the disadvantage that the array needs to know the data size in advance (the C language array needs to define the length in advance). The linked list structure can make full use of the computer memory space and realize flexible dynamic memory management.
The next step is to introduce two common types of linked lists: one-way linked lists and two-way linked lists in JavaScript.

Singly linked list

The simplest form of a linked list is a one-way list. Each node in the list contains two parts. Part 1 stores information about itself, and part 2 stores a pointer to the next node. The last node points to NULL:

Realization of unidirectional linked list in JavaScipt

First, create a constructor.

/**
 *  Unidirectional linked list constructor 
 */
function LinkedList() {
 /**
  *  A constructor for a node in a unidirectional linked list 
  * @param {Any} element  The node to pass in the linked list 
  */
 var Node = function(element) {
  this.element = element;
  // The address of the next node 
  this.next = null;
 }

 // The length of a one-way list 
 var length = 0;
 // The head of a one-way linked list, initialized to NULL
 var head = null;
}

As you can see, the unidirectional linked list constructor is much more complex than the stack and queue.
One-way linked lists require the following methods:

append(element): Adds elements to the end of the list insert(position,element): Inserts elements to a location in a one-way linked list indexOf(element): Finds the location of an element in a unidirectional linked list remove(element): Removes the given element removeAt(position): Removes an element at a location in a one-way linked list getHead(): Gets the head of a one-way linked list isAmpty(): Check whether the one-way linked list is empty, and return true if it is toString(): Outputs the contents of the linked list as a string size(): Returns the one-way list length

append method:

Description: Adds elements to the end of a one-way linked list.
Implementation:

/**
 *  Adds an element to the end of a one-way list 
 * @param {Any} element  Nodes to join the list 
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  //  The current item is equal to the header element of the list .
  // while Loop to the end 1 , thus adding the node to the end of the list. 
  current = head;
  //  when next for null Is determined as false . Exit the loop. 
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

insert method:

Inserts elements to a location in a unidirectional linked list.
Implementation:

/**
 *  Inserts an element into a unidirectional linked list 
 * @param {Number} position  The position to insert 
 * @param {Any} element  The element to insert 
 * @return {Boolean}      Insert successful return true , return after failure false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

indexOf method:

Description: Find the location of an element in a unidirectional linked list.
Implementation:

/**
 *  Find the location of an element in a unidirectional linked list 
 * @param {Any} element  The element to look for 
 * @return {Number}      The return value >=0 It means find the appropriate location 
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

remove method:

Description: Removes a given element.
Implementation:

/**
 *  Removes the given element 
 * @param {Any} element  The element to remove 
 * @return {Number}      The return value >=0 Indicates successful removal 
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

removeAt method:

Description: Removes elements at a location in a unidirectional linked list.
Implementation:

/**
 *  Removes a from a unidirectional linked list 1 An element 
 * @param {Number} position  To remove the location of the element 
 * @return {Any}      Removal returns the removed element successfully or unsuccessfully NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   //  Because before head Pointing to the first 1 Three elements. Now let's put head Change to point to a control 2 An element. 
   //  The core concept is that lists are linked by Pointers, not arrays 1 A. 
   //  So it just needs to change head The element. 
   head = current.next;
  } else {
   while (index++ < position) {
    // previous The element before you want to manipulate the element position, current Represents the next element. 
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

getHead method:

Gets the head of a one-way linked list.
Implementation:

/**
 *  Gets the head of a one-way linked list 
 * @return {Any}  The head of a one-way list 
 */
this.getHead = function() {
 return head;
}

Methods isAmpty, toString and size

Implementation:

/**
 *  Determines whether a one-way linked list is empty 
 * @return {Boolean}  Returns if null true , returns if it is not empty false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 *  Outputs the contents of the linked list as a string 
 * @return {String}  The string to output 
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 *  Returns the one-way list length 
 * @return {Number}  The length of a one-way list 
 */
this.size = function() {
 return length;
};

Two-way linked list

A two-way linked list is much like a one-way linked list. In a one-way linked list, there are only links to the next node. But in a bi-directional list, there's also a link to the previous node, which is bi-directional.

Realization of bidirectional linked list in JavaScipt

First, the constructor remains:

/**
 *  Constructor for a bidirectional linked list 
 */
function DoublyLinkedList() {
 /**
  *  A constructor for a node in a bidirectional linked list 
  * @param {Any} element  To pass in the elements of the list 
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 // The length of a bidirectional list 
 var length = 0;
 // The head of a bidirectional linked list, initialized to NULL
 var head = null;
 // The end of a bidirectional list, initialized to NULL
 var tail = null;
}

Bidirectional linked lists require the following methods:

append(element): Adds elements to the end of a bi-directional linked list insert(position,element): Inserts elements to a location in a bi-directional linked list removeAt(position): Removes an element at a location in a bidirectional linked list showHead(): Gets the head of a bi-directional linked list showLength(): Gets the length of the bi-directional linked list showTail(): Gets the end of a bi-directional linked list

append method:

Description: Add elements to the end of a bi-directional list
Implementation:

/**
 *  Adds an element to the end of the list 
 * @param {Any} element  Nodes to join the list 
 * @return {Any}      Nodes that join the list 
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

insert method:

Description: Inserts elements to a location in a bi-directional linked list.
Implementation:

/**
 *  Adds an element to the end of a one-way list 
 * @param {Any} element  Nodes to join the list 
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  //  The current item is equal to the header element of the list .
  // while Loop to the end 1 , thus adding the node to the end of the list. 
  current = head;
  //  when next for null Is determined as false . Exit the loop. 
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

0

removeAt method:

Description: Removes elements at a location in a bidirectional linked list.
Implementation:

/**
 *  Adds an element to the end of a one-way list 
 * @param {Any} element  Nodes to join the list 
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  //  The current item is equal to the header element of the list .
  // while Loop to the end 1 , thus adding the node to the end of the list. 
  current = head;
  //  when next for null Is determined as false . Exit the loop. 
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

1

showHead, showLength, showTail methods

Implementation:

/**
 *  Adds an element to the end of a one-way list 
 * @param {Any} element  Nodes to join the list 
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  //  The current item is equal to the header element of the list .
  // while Loop to the end 1 , thus adding the node to the end of the list. 
  current = head;
  //  when next for null Is determined as false . Exit the loop. 
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

2

feeling

This 1 section of the linked list, basically all is to write the code according to the requirements, after writing and then compare with the book. It turns out to be a split-second thing. I wrote a lot of dark holes, the logic is also very confusing. It still looks too young.