Implementing Object-based Single List with JavaScript

Introduction of one-way linked list

What is a one-way list?

Unlike the index of arrays: values (which can be modified directly at the array level), the relationships between the values in the linked list tend to be de-centralized.

As shown in the figure above, each node can be divided into two parts: 1. the value of the node; 2. the direction of the next node, that is, who is the next node. For example, the first node in the list above has a value of milk and the next node has a value of Bread.

Advantages of one-way linked list

When we need to organize data, arrays are not always the best data structure (for most programming languages), because they have two obvious drawbacks: 1. The length of arrays is fixed, when the array has been filled with data, adding new data will be very troublesome; 2. When we insert or delete one of the arrays. When a value is used, other values in the array need to be moved backward or forward to reflect that the array has been added or deleted.

So when we need to add and delete data frequently, it is not so wise to choose arrays. At this time, we can use linked lists to add and delete data. Addition and deletion of linked list will be much more convenient, when adding data, only need to change its node pointing and the node pointing of the upper node; when deleting data, only need to assign the node pointing of the node to be deleted to the upper node, then the node to be deleted will disappear in the linked list (because it can not pass through the node and node). If the relationship finds it again, it can be regarded as vanishing.

For example, if we add sandwich data to milk and bread, we only need to change the node pointing of milk to sandwich, and assign the node pointing to bread to sandwich; when we need to delete sandwich, we only need to assign the node pointing to bread to milk, and sandwich disappears automatically.

Constructing a linked list

When we need to organize a certain kind of data, we only need to build a corresponding constructor (constructor), which should include the following attributes and methods: header node; add, delete, check, etc.

Node constructor

We can make the constructor of the head node first.

//We can think of a node as a box, which is divided into two parts. One part holds the value of the node, the other part holds the node pointing to the next node.
function Node(element) {
  this.element = element;
  this.next = null;
}

Link list constructor

Link List Constructor for Certain Types of Data

function LList() { //LList: linkedList linked list
  //The new node (header) with the value of header can make everything possible. The following operations are based on the header.
  this.head = new Node("head");
  
  //Find method, give find a value, you can find the corresponding node
  this.find = find;
  
  //Insertion method, which can realize the function of where to insert and what data to insert
  this.insert = insert;
  
  //Display the print function, pass in the elements of the node you want to query, and the node can be printed out, including the next node pointing to
  this.display = display;

  //If you want to delete a node, you need to find its previous node and modify its node pointing
  this.findPrevious = findPrevious;
 
  //Delete method, pass in the element you want to delete, you can achieve the delete function
  this.remove = remove; 
}

find() method

The find() method shows how to move on the list. First, create a new node and assign the header to the new node. Then loop on the list. If the element attribute of the current node is different from the value we are looking for, move from the current node to the next node. If the search is successful, return the node containing the data, fail, and return null.

function find(item) {
  
  //Appoint headers to new nodes
  var currNode = this.head;
  
  //Loop, if the value of the current node is different from the value we want to find, move to the next node. Know to find a target or move to null
  while (currNode.element !== item) {
    currNode = currNode.next;
  }
  
  //Return the corresponding node or null
  return currNode;
}

insert() method

insert() implements insertion function, passes in the value of new element and item of inserting position of new node, and modifies the point of new node and node of inserting position to complete insertion.

function insert(newElement, item) {
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}

display()

display() displays the elements in the list

function display() {
  var currNOde = this.head;
  while (currNode !== item) {
    console.log(currNode.element);
    currNode = currNode.next;
  }
}

findPrevious()

findPrevious() finds the first node to be deleted

function findPrevious(item) {
  var currNode = this.head;
  while ((currNode.next !== null) && (currNode.next.element !== item)) {
    currNode = currNode;
  }
  return currNode;
}

remove() method

function remove(item) {
  var preNode = this.findPrevious(item);
  if(preNode.next !== null) {
    preNode.next = preNode.next.next;
  }
}

Complete code

function Node(element) {
  this.element = element;
  this.next = null;
}

function LList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.findPrevious = findPrevious;
  this.remove = remove;
}

function find(item) {
  var currNode = this.head;
  while (currNode.element !== item) {
    currNode = currNode.next;
  }
  return currNode;
}

function insert(newElement, item) {
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}

function display() {
  var currNode = this.head;
  while (currNode.next !== null) {
    console.log(currNode.next.element);
    currNode = currNode.next;
  }
}

function findPrevious(item) {
  var currNode = this.head;
  while ((currNode.next.element !== item) && (currNode.next !== null)) {
    currNode = currNode.next;
  }
  return currNode;
}

function remove(item) {
  var preNode = this.findPrevious(item);
  if(preNode.next !== null) {
    preNode.next = preNode.next.next;
  }
}

test

Write data to linked list

var cities = new LList();
cities.insert("beijing", "head");
cities.insert("shanghai", "beijing");
cities.insert("guangzhou", "shanghai");
cities.insert("shenzhen", "guangzhou");

Display list

cities.display();

Delete "shanghai hai" and show it again

cities.remove("shanghai");
cities.display();

Delete successfully!

Reference

Michael McMillan, (2014). Data Structures & Algorithms with JavaScript. Beijing: O'Reilly Media, Inc. and Posts & Telecom Press.

Keywords: Javascript Programming Attribute

Added by Unforgiven on Mon, 19 Aug 2019 11:21:13 +0300

Programming VIP

Implementing Object-based Single List with JavaScript