Data structures – one-way linked lists

What is a linked list

Linked list: A discontinuous, nonsequential data structure consisting of a series of nodes that store data.

• Unlike arrays, memory in linked lists need not be contiguous space.
• Each element of a linked list consists of a node that stores the element itself and a reference to the next element.

Advantages of linked lists:

• Storage space does not have to be continuous, can make full use of the computer’s memory space, can achieve flexible memory space dynamic management.
• A linked list does not have to be sized at the time of creation; it can add data indefinitely.
• The time complexity of linked lists can reach O(1) when adding and deleting data, which is much more efficient than arrays.

Disadvantages of linked lists:

• Access data anywhere from scratch. Cannot skip header element access.
• Elements cannot be accessed directly by subscript values and need to be traversed.
• It’s harder to get back to the last node.

The linked list is shown below:

What is a one-way linked list

LinkedList: A LinkedList is similar to a train, with a locomotive that connects to a node with passengers on it, and that node connects to the next node, and so on.

The unidirectional linked list is shown below:

Common operations on linked lists

• Append (data) adds data to the end of the list
• Insert (position, data) Inserts a node at the specified position
• GetData (position) Gets the list node at the specified position
• IndexOf (data) Finds the index of the data
• Update (position, data) Updates node data at the specified position
• RemoveAt (position) Deletes the specified node
• Remove (data) Deletes the node with the specified data
• IsEmpty () checks whether the list isEmpty
• Size () gets the length of the list
• ToString () prints all the elements of the list as a string

ES6 implements a one-way linked list structure

• Encapsulation of node classes inside linked lists

// Internal data class: consists of data and next. Nodes in a linked listclass Node {
  data;
  next = null;
  constructor(data) {
 this.data = data;  } } Copy the code

• Encapsulation of one-way linked list classes

class LinkedList {
  length = 0;
  head = null;
}
Copy the code

• Append (data) method implementation

// append(data) adds data to the end of the list  append(data) {
// 1. Create a new list node first    const newNode = new Node(data);
// 2. Add nodes to the list if (this.length === 0) { // If the list is empty, head points to the new node this.head = newNode;  } else { // Add to the end of the list // Get the head node let currentNode = this.head;  // loop to find the tail node while(currentNode.next ! == null) { currentNode = currentNode.next;  }  // Add a new node to the tail node currentNode.next = newNode;  } // The list length increases this.length++;  } Copy the code

• Insert (position, data) method implementation

// Insert (position, data) Inserts a node at the specified position  insert(position = 0, data) {
// position represents the insertion position// position = 0 to insert the first position
// Determine the boundary problem first if (position < 0 || position > this.length) return false;  // 1. Create new list nodes const newNode = new Node(data);  // If position is 0, insert into the head of the list, otherwise, find the corresponding position to add a node // 2. Add nodes according to position if (position === 0) { // Position is 0// First pass the header reference to next on the new node newNode.next = this.head; // Pass the reference to the new node to the head this.head = newNode;  } else { // 0 < position < this.length // Main idea: find the corresponding location to add nodes// Prepare variables letcurrentNode = this.head; // The current node letpreviousNode = null; // Last node letindex = 0; // The index of head is 0, representing the current node number // Find the position you want to insert while (index++ < position) {  previousNode = currentNode;  currentNode = currentNode.next;  }  // Add a list node// first, the next of the new node connects to the currentNode// next of the previous node connects to the newNode newNode  newNode.next = currentNode;  previousNode.next = newNode;  } // Follow the length of the new list this.length++;  return newNode;  } Copy the code

• GetData (position) method implementation

// getData(position) gets the list node at the specified position  getData(position = 0) {
// 1. Determine the boundary    if (position < 0 || position >= this.length) return false;
// Find the specified location// 2. Prepare variables letcurrentNode = this.head; // The current list node letindex = 0; // The current list node position / / to find while (index++ < position) {  currentNode = currentNode.next;  }  / / return return currentNode.data;  } Copy the code

• IndexOf (data) method implementation

// indexOf(data) Finds the index corresponding to the data  indexOf(data) {
// Return the index of the linked list    let currentNode = this.head;
    letindex = 0; // Represents the index of the current node // loop search while (currentNode) {  if (currentNode.data === data) {  return index;  }  currentNode = currentNode.next;  index++;  } // Otherwise return -1 return- 1; } Copy the code

• Update (position, data) method implementation

// update(position, data) Updates node data at the specified position  update(position, data) {
// Determine the boundary    if (position < 0 || position >= this.length) return false;

 let currentNode = this.head;  let index = 0;  // Loop to find the specified node while (index++ < position) {  currentNode = currentNode.next;  } // Update data currentNode.data = data;   return currentNode;  } Copy the code

• RemoveAt (Position) method implementation

// removeAt(position) Deletes the specified node  removeAt(position) {
/ / boundary    if (position < 0 || position >= this.head) return false;

 let currentNode = this.head;  / / position if (position === 0) {  this.head = this.head.next;  } else { // Last node let previousNode = null; // The current node index let index = 0;  // Find the list node while (index++ < position) {  previousNode = currentNode;  currentNode = currentNode.next;  } // Next of the previous node is directly connected to next of the current node// Delete the specified node previousNode.next = currentNode.next;  }  // The node length is -1 this.length--;  return currentNode;  } Copy the code

• Remove (data) method implementation

// remove(data) Deletes the node of the specified data  remove(data) {
    return this.removeAt(this.indexOf(data));
  }
Copy the code

• An implementation of isEmpty()

// isEmpty() checks if the list isEmpty  isEmpty() {
    return this.length === 0;
  }
Copy the code

• An implementation of the size() method

// size() gets the length of the list  size() {
    return this.length;
  }
Copy the code

• Implementation of the toString() method

  toString() {
    let currentNode = this.head;
    let result = "";

// Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) {  result += currentNode.data + "";  currentNode = currentNode.next;  }   return result;  } Copy the code

The general code of a one-way linked list

// Internal data class: consists of data and next. Nodes in a linked listclass Node {
  data;
  next = null;
  constructor(data) {
 this.data = data;  } }  class LinkedList {  length = 0;  head = null;  // append(data) adds data to the end of the list append(data) { // 1. Create a new list node first const newNode = new Node(data); // 2. Add nodes to the list if (this.length === 0) { // If the list is empty, head points to the new node this.head = newNode;  } else { // Add to the end of the list // Get the head node let currentNode = this.head;  // loop to find the tail node while(currentNode.next ! == null) { currentNode = currentNode.next;  }  // Add a new node to the tail node currentNode.next = newNode;  } // The list length increases this.length++;  }  // Insert (position, data) Inserts a node at the specified position insert(position = 0, data) { // position represents the insertion position// position = 0 to insert the first position // Determine the boundary problem first if (position < 0 || position > this.length) return false;  // 1. Create new list nodes const newNode = new Node(data);  // If position is 0, insert into the head of the list, otherwise, find the corresponding position to add a node // 2. Add nodes according to position if (position === 0) { // Position is 0// First pass the header reference to next on the new node newNode.next = this.head; // Pass the reference to the new node to the head this.head = newNode;  } else { // 0 < position < this.length // Main idea: find the corresponding location to add nodes// Prepare variables letcurrentNode = this.head; // The current node letpreviousNode = null; // Last node letindex = 0; // The index of head is 0, representing the current node number // Find the position you want to insert while (index++ < position) {  previousNode = currentNode;  currentNode = currentNode.next;  }  // Add a list node// first, the next of the new node connects to the currentNode// next of the previous node connects to the newNode newNode  newNode.next = currentNode;  previousNode.next = newNode;  } // Follow the length of the new list this.length++;  return newNode;  }  // getData(position) gets the list node at the specified position getData(position = 0) { // 1. Determine the boundary if (position < 0 || position >= this.length) return false; // Find the specified location// 2. Prepare variables letcurrentNode = this.head; // The current list node letindex = 0; // The current list node position / / to find while (index++ < position) {  currentNode = currentNode.next;  }  / / return return currentNode.data;  }  // indexOf(data) Finds the index corresponding to the data indexOf(data) { // Return the index of the linked list let currentNode = this.head;  letindex = 0; // Represents the index of the current node // loop search while (currentNode) {  if (currentNode.data === data) {  return index;  }  currentNode = currentNode.next;  index++;  } // Otherwise return -1 return- 1; }  // update(position, data) Updates node data at the specified position update(position, data) { // Determine the boundary if (position < 0 || position >= this.length) return false;   let currentNode = this.head;  let index = 0;  // Loop to find the specified node while (index++ < position) {  currentNode = currentNode.next;  } // Update data currentNode.data = data;   return currentNode;  }  // removeAt(position) Deletes the specified node removeAt(position) { / / boundary if (position < 0 || position >= this.head) return false;   let currentNode = this.head;  / / position if (position === 0) {  this.head = this.head.next;  } else { // Last node let previousNode = null; // The current node index let index = 0;  // Find the list node while (index++ < position) {  previousNode = currentNode;  currentNode = currentNode.next;  } // Next of the previous node is directly connected to next of the current node// Delete the specified node previousNode.next = currentNode.next;  }  // The node length is -1 this.length--;  return currentNode;  }  // remove(data) Deletes the node of the specified data remove(data) {  return this.removeAt(this.indexOf(data));  }  // isEmpty() checks if the list isEmpty isEmpty() {  return this.length === 0;  }  // size() gets the length of the list size() {  return this.length;  }   toString() {  let currentNode = this.head;  let result = "";  // Iterate over all nodes, concatenating them into strings until the node is null while (currentNode) {  result += currentNode.data + "";  currentNode = currentNode.next;  }   return result;  } } Copy the code