Make writing a habit together! This is the 10th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Hello, I’m Yang Chenggong.

We have learned about arrays, stacks, queues, and double-ended queues. Today we meet a new friend, a dynamic data structure – linked lists.

What is a linked list

A linked list is a dynamically ordered set. How to understand the “dynamic” here?

First, recall that arrays are the most basic data structures that are fixed in size in most languages. A linked list, on the other hand, is a “dynamic” array that allows elements to be added and removed at will.

At this point you may be wondering: Arrays in JavaScript are also dynamic, and elements can be added and removed at will. This is true, but JavaScript provides native methods that are easy to use but slow in performance.

Why is that? Let’s say you want to insert an element at the beginning or in the middle of the array, and from that point on, all the elements that follow move back one, so you’re not just adding one element, you’re essentially modifying all the elements that follow.

When the array is very large, the further you add it, the more elements you have to move. Thus, the larger the array, the worse the performance of manipulating array elements is likely to be.

But linked lists are different. Linked lists have the same function as arrays, but their elements are placed independently in memory and are not contiguous. Each element is made up of its own value and a reference to the next element, as follows:

If you look at this picture, it becomes even clearer. When you need to add an element at any location, you simply add a new element, modify the reference to the current element and the previous element, and leave the other elements unchanged. So regardless of the length of your list, the performance of manipulating elements is very high.

But are linked lists necessarily better than arrays? Also is not. In an array, we can access any element by index, while in a linked list, because each element is independent of each other, to find an element, we must start from the first element (table header) and search one by one until we find the target.

Implement a linked list

Above we introduced linked lists and compared them to arrays, outlining their differences and advantages and disadvantages. With that in mind, we’re ready to start implementing a linked list.

Let’s start with the basic structure:

class linkedList {
  constructor() {
    this.count = 0;
    this.head = undefined; }}Copy the code

The code above has two attributes:

  • count: indicates the length of the list, that is, the number of elements
  • head: Stores a reference to the first element (table header)

As mentioned earlier, a linked list element contains its own value and a reference to the next element. We need a quick way to create list elements when we add them, so we write a Node class to represent the list elements:

class Node {
  constructor(value) {
    this.value = value;
    this.next = undefined; }}Copy the code

With these two classes in place, you can now write methods that operate on linked list elements.

This article covers only two common methods:

  • push: Adds an element to the end of the list
  • removeAt: Removes an element from somewhere in the list

Push to realize

When adding an element to the end of a list, there are two possible situations:

  • If the list is empty, the first element is added
  • The list is not empty, adding elements after all elements
push(item) {
  let node = new Node(item)
  let current;
  if(!this.head) {
    this.head = node
  } else {
    current = this.head
    while(current.next) {
      current = current.next
    }
    current.next = node;
  }
  this.count++;
}
Copy the code

The code first checks whether the variable head, which stores the table header reference, is assigned. If no value is assigned, there is no element in the list. In this case, assign head to the newly created element.

If the variable head is assigned, there are already elements in the list. We go level by level through head.next until we find the last element, the next element with undefined.

The tail addition is completed by assigning the next attribute of the last element of the list to the new element.

Finally, don’t forget to increment the length count attribute by one.

RemoveAt implementation

Above we implemented the method to add elements, but here we show how to remove elements from somewhere.

Deleting an element from a place is similar to deleting an element with an index in an array. The removeAt method provides a numeric parameter, equivalent to an array index, indicating that the element at that location is to be removed.

The infrastructure is as follows:

removeAt(index) {
  if(index >= 0 && index < this.count) {
    // Specific logic
  }
  return undefined;
}
Copy the code

In this method, you first limit the parameter index between 0 and the length of the list, and then delete elements in two cases.

If index is equal to 0, then it’s easy to move the head attribute one bit back.

The corresponding code looks like this:

if(index == 0) {
  let current = this.head;
  this.head = current.next;
}
Copy the code

If index is greater than 0, then there are three general steps:

  1. Find the element B that corresponds to index
  2. Find the last member of B, A
  3. willA.nextPoint to theB.next

When you get to the third part, you’re bypassing the link to B directly, which means you’ve deleted element B.

The corresponding code looks like this:

if(index > 0) {
  let current = this.head;
  let previous; 
  for(let i = 0; i < index; i++) { previous = current; current = current.next; }}Copy the code

Combining the two cases, the complete code is as follows:

removeAt(index) {
  if(index >= 0 && index < this.count) {
    let current = this.head;
    / / the first item
    if(index == 0) {
      this.head = current.next;
    } else {
      let previous;
      for(let i = 0; i < index; i++) { previous = current; current = current.next; }}this.count--;
    return current.value
  }
  return undefined;
}
Copy the code

conclusion

This article introduces the concept of linked lists and their differences from arrays, and then implements push and removeAt methods.

Linked list content is relatively complex, this article introduces the two methods, you can repeatedly understand. In the next part, we will supplement other methods and test the final results.

This article source public number: programmer success. This is the ninth chapter of learning JavaScript data structures and algorithms, this series will be updated for a month, welcome to pay attention to the public account, click “add group” to join our learning team ~