[Data Structure and Algorithms – small White series] the 2️ day linked list

review

The first day we learned stack and queue [data structure and algorithm – small white series] the first ️ day stack, queue today we will learn another important data structure linked list, personal feeling linked list to understand more difficult than stack and queue, but no matter what we do is over

The listandStack, queue,Is fundamentally different

In the last, we are realized through javascript array stack and queue, we know that the array is linear structure, that is to say, the data in the array is a deposit of a continuous, we can read by subscripting elements, so the stack and queue are linear to store data, and the list is not, we can remember the list is the first line of chain store Sexual table

What problems are linked lists supposed to solve?

It exists for a reason, and it is important to remember that each data structure corresponds to a typical application scenario

So what’s the problem with linked lists?

Let’s start with stacks and queues and what’s the downside of this data structure, or arrays

First of all, arrays are linear stores of data and can be read by subscript. Although it is very fast to read data, if we add or delete data to the data, the data execution efficiency is not so high. Let’s look at the process of adding data to the array

We have an array [2,4,6,8], and now we need to add a 3 between 2 and 4

It can be seen that when we insert one data, we need to change the positions of three data. If the data volume is very large, we can see that the efficiency of the array is low when adding and modifying data

Linked lists are designed to solve this problem

The structure of linked lists

The essence of a linked list is Pointers. We can call the elements in a linked list nodes

So the question is, why do we build relationships through Pointers?

We know that array storage is continuous, so we can get the value through the index of the array, while linked list storage is discrete, so how do we know what the next data of a node is? The only way to buy a pointer is to store a reference to the next node, as shown below:

Now if we want to add something we just move the pointer, so here we add a 4 between 2 and 3

The current data structure is 1->2->4->3

The principle is very simple, let’s use the code to achieve the side

Use JavaScript to implement linked lists

Singly linked list

A one-way list is a list of nodes with a reference to the next node. This reference can only be one-way, such as 1->2->3->4. First we will create a node

function Node(data){
    this.data = data
    this.next = null
}

Copy the code

We encapsulate a linked list class with the following methods:

• Append additional
• Insert to insert
• Get Gets the data of the corresponding subscript
• Indexof gets the corresponding data subscript value
• Updata and new nodes
• Remove Delete a node.
• ToString list stringing

function linkedList() {
  // List node class
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  this.head = null; // List hede can be understood as pointer
  this.length = 0; // The length of the list
  // Add method
  linkedList.prototype.append = function(data) {
    var newNode = new Node(data);
    // Check whether the current list is empty
    if (this.length == 0) {
      // Add the first node
      this.head = newNode;
    } else {
      // Not the first node, find the last node, append nodes after it
      var current = this.head;
      while (current.next) {
        current = current.next; // Go straight down
      }

      // Appends the last node
      current.next = newNode;
    }
    this.length++;
  };
  // Insert methods that can insert data anywhere in the list
  linkedList.prototype.insert = function(position, data) {
    // Judge position out of bounds
    if (position < 0 || position > this.length) {
      return false;
    }
    var newNode = new Node(data);
    // Determine whether to insert the first one
    if (position == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      var index = 0;
      var current = this.head;
      var previous = null; // Record the last node
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      newNode.next = current;
      previous.next = newNode;
    }
    this.length++;
    return true;
  };
  // Get the data at the corresponding position
  linkedList.prototype.get = function(position) {
    if (position < 0 || position >= this.length) {
      return null;
    }
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    return current.next;
  };
  // Get the subscript value of the corresponding data
  linkedList.prototype.indexOf = function(data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data == data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  };
  // Update the method
  linkedList.prototype.updata = function(position, data) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.data = data;
    return true;
  };
  // Remove elements by position
  linkedList.prototype.removeAt = function(position) {
    if (position < 0 || position >= this.length) {
      return false;
    }
    // delete the first one
    if (position == 0) {
      this.head = this.head.next;
    } else {
      var current = this.head;
      var previous = null;
      var index = 0;
      while (index++ < position) {
        position = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length -= 1;
    return true;
  };
  // string
  linkedList.prototype.toString = function() {
    var current = this.head;
    var listString = "";
    // loop through each node
    while (current) {
      listString += current.data + "";
      current = current.next;
    }
    return listString;
  };
}

Copy the code

Two-way linked list

Each node records references to its previous and next nodes, such as:

Change the method of one-way linked list to bidirectional linked list as follows:

// Two-way linked list
function DoublyList() {
  this.head = null; // The pointer points to the first
  this.tail = null; // The pointer points to the last
  this.length = 0; // The list length
  // Internal node class
  function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
  // Insert to the end of the list
  DoublyList.prototype.append = function(data) {
    // Determine whether the first node is added
    var newNode = new Node(data);
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length += 1;
  };
  / / insert
  DoublyList.prototype.insert = function(position, data) {
    if (position < 0 || position > this.length) return false;
    var newNode = new Node(data);
    // The inserted node is the first node
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    }
    if (position == 0) {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    } else if (position == this.length) {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      var current = this.head;
      var index = 0;
      while (index++ < position) {
        current = current.next;
      }
      // Change the corresponding pointer pointer
      newNode.next = current;
      newNode.prev = current.prev;
      current.prev.next = newNode;
      current.prev = newNode;
    }
    this.length += 1;
  };
  // Get the corresponding index data
  DoublyList.prototype.get = function(position) {
    if (position < 0 || position >= this.length) return false;
    // Get the element
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    return current.data;
  };
  // Get the index of the corresponding value
  DoublyList.prototype.indexOf = function(data) {
    var current = this.head;
    var index = 0;
    while (current) {
      if (current.data == data) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  };
  // Update according to subscript
  DoublyList.prototype.updata = function(position, newData) {
    if (position < 0 || position >= this.length) return false;
    // Get the element
    var current = this.head;
    var index = 0;
    while (index++ < position) {
      current = current.next;
    }
    current.data = newData;
    return true;
  };
  // Delete by subscript
  DoublyList.prototype.removeAt = function(position) {
    if (position < 0 || position > this.length) return false;
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    }

    if (position == 0) {
      this.head.next.prev = null;
      this.head = this.head.next;
    } else if (position == this.length - 1) {
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      var index = 0;
      var current = this.head;
      while(index++ < position) { current = current.next; } current.prev.next = current.next; current.next.prev = current.prev; }}; DoublyList.prototype.toString =function() {
    return this.bacckwardToString();
  };
  // traverse from back to front
  DoublyList.prototype.forwardToString = function() {
    var current = this.tail;
    var resString = "";
    while (current) {
      current = current.prev;
      resString += current.data + "";
    }
    return resString;
  };
  // go from front to back
  DoublyList.prototype.bacckwardToString = function() {
    var current = this.head;
    var resString = "";
    while (current) {
      current = current.next;
      resString += current.data + "";
    }
    return resString;
  };
}
Copy the code

The last

Click 👍 hope to make a friend with you