Small five algorithm series – linked list

Hello, brave friends, I am your strong mouth king xiao Wu, healthy body, not brain disease.

I have a wealth of hair loss techniques that will catapult you to the top.

A look will be written waste is my theme, food to pick the foot is my characteristics, humble in showing a trace of strong, stupid people have stupid blessing is the greatest comfort to me.

Welcome to the list of five’s algorithms.

preface

This series of articles to “algorithm diagram” and “Learning JavaScript algorithm” two books as the core, the rest of the materials as assistance, and with the author’s insights. Strive to simple, interesting language to bring everyone to appreciate the magic of this algorithmic world.

This article is a linked list. The author will lead you from THE JS simulation of its implementation, gradually change in order to explore other forms of the list, and finally attached a few exercises to deepen understanding and consolidate what you have learned.

Linked lists have an important application in JavaScript — prototype chains, which I will explain in detail in a separate article.

Introduction of the list

The author from “what is the list” and “what is the list used for” to give everyone vernacular vernacular

🦥 What is a linked list

The list is like a scavenger hunt, with treasures hidden all over the island. You get a clue at the beginning of the game, and you go through the clue in your hand to find the next treasure, and so on.

From this we summarize the characteristics of the linked list:

• Treasures are scattered throughout the island – elements in the list are not stored continuously in memory

• The next location is determined by clues – each node consists of storing the element itself and a pointer to the next element, and there is no way to get past one node to the next

What is 🦥 for

To store data, and at this point you have a big question mark on your little head, why don’t you use an array to store data?

Let’s compare the advantages and disadvantages of the two data structures based on their respective characteristics:

👺 Arrays are stored in contiguities, while lists are not

What happens if you insert an element in the middle of an array 🤔 The array is sequential, like cutting in line, and everyone else is one bit behind; And the list storage is discontinuous, insert the rest of the elements do not need to change, delete the same;

Therefore, we can conclude that lists have an advantage over arrays when inserting or deleting elements

The 👺 array accesses elements directly, while the linked list finds elements through Pointers

Since arrays are contiguous, we can access them directly by subscript; And a linked list needs to start from the table head one by one, until found;

Therefore, it can be concluded that an array has the advantage over a linked list when searching for elements

Linked list implementation

👇 Let’s use js to simulate a linked list and add the following methods to it:

• Append (Element) : Appends a new element to the end of the list

• Insert (element, position) : Inserts a new element into a specific position in the list

• Remove (element) : Remove an element from a linked list

• IndexOf (element) : returns the indexOf the element in the linked list, or -1 if there is no element

• RemoveAt (Position) : Removes an element from a specific position in the list

• IsEmpty () : Whether there are elements in the list

• Size () : indicates the number of elements in the list

For a linked list, both insert and delete operations are the process of changing the next pointer.

🦥 structure

First let’s define the node in the list, which contains the element itself and a pointer to the next node

class Node<T> {
  element: T | null;
  next: Node<T> | null;

  constructor(element: T | null) {
    this.element = element;
    this.next = null; }}Copy the code

To clarify the structure of the linked list, it needs to have a head node head and a record length length

class LinkedList<T> {
  head: Node<T> | null = null;
  length = 0;
}
Copy the code

🦥 append (element)

If empty, it is the head node; If it is not empty, it is the tail node of the list;

append(element: T) {
  let node = new Node<T>(element);

  if (!this.head) {
    this.head = node;
  } else {
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }

  this.length++;
}
Copy the code

🦥 insert (element, the position)

Find the insertion position and change the next point

• Position = 0, node. Next -> head

• Position > 0, previous.next -> node, node.next -> current

insert(element: T, position: number) {
  if (position < 0 || position > this.length) return false;
  
  let node = new Node<T>(element);
  let index = 0;
  let current = this.head;
  let previous: Node<T> | null = null;

  if (position === 0) {
    node.next = this.head;
    this.head = node;
  } else {
    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    (previous as Node<T>).next = node;
    node.next = current;
  }

  this.length++;
  return true;
}
Copy the code

🦥 removeAt (position)

Find the insert position and change the next point

• Position = 0, head -> head.next

• Position > 0, previous.next -> current.next

removeAt(position: number) {
  if (!this.head || position < 0 || position >= this.length) return false;

  let index = 0;
  let current: Node<T> | null = this.head;
  let previous: Node<T> | null = null;

  if (position === 0) {
    this.head = this.head.next;
  } else {
    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    (previous asNode<T>).next = current? .next ||null;
  }

  this.length--;
  return true;
}
Copy the code

🦥 indexOf (element)

Just go through the list from the beginning

indexOf(element: T) {
  let current = this.head;
  let index = 0;

  while (current) {
    if (typeof current.element === 'object') {
      if (JSON.stringify(element) === JSON.stringify(current.element)) return index;
    } else {
      if (element === current.element) return index;
    }

    current = current.next;
    index++;
  }

  return -1;
}
Copy the code

🦥 remove (element)

Integrate removeAt and indexOf

remove(element: T) {
  let position = this.indexOf(element);
  return this.removeAt(position);
}
Copy the code

Two-way linked list

The literal meaning says it all, a linked list that is connected in both directions; You can choose “go from start to end” or “go from end to head”;

So we append a prev pointer to the Node class, add a tail attribute to the list, and rewrite the append, INSERT, and removeAt methods

🦶tips: Just pay attention to the connection of the pointer, do not lose four connections in one direction

🦥 append (element)

• If the value is empty, head = node and tail = node

• Next = node, node.prev = tail; Then update tail

append(element: T) {
  let node = new Node<T>(element);

  if (!this.head || !this.tail) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }

  this.length++;
}
Copy the code

🦥 insert (element, the position)

• Insert the header or the tail, the same way you append an element, just consider the boundary value

• Next = node -> node.next = nextNode; Prev: nextnode. prev = node -> node.prev = prevNode;

insert(element: T, position: number) {
  if (position < 0 || position > this.length) return false;

  let node = new Node<T>(element);
  
  if (position === 0) {
    if (this.head) {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    } else {
      this.head = node;
      this.tail = node; }}else if (position === this.length) {
    (this.tail as Node<T>).next = node;
    node.prev = this.tail;
    this.tail = node;
  }
  
  else {
    let current = this.head;
    let previous: Node<T> | null = null;
    let index = 0;

    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }

    (previous as Node<T>).next = node;
    node.next = current;
    (current as Node<T>).prev = node;
    node.prev = previous;
  }

  this.length++;
}
Copy the code

🦥 removeAt (position)

Basically the same idea as insert

• If the list has only one node, assign NULL to the first and last nodes respectively

• Delete the head: head = head.next, head.prev = null, and the tail is the same

• Delete intermediate prenode. next = nextNode and nextNode.prev = preNode

removeAt(position: number) {
  if (!this.head || position < 0 || position >= this.length) return false;

  if (position === 0) {
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      (this.head as Node<T>).prev = null; }}else if (position === this.length - 1) {
    this.tail = (this.tail as Node<T>).prev;
    (this.tail as Node<T>).next = null;
  }

  else {
    let current: Node<T> | null = this.head;
    let previous: Node<T> | null = null;
    let index = 0;
    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    if(! previous || ! current)return false;
    previous.next = current.next;
    (current.next as Node<T>).prev = previous;
  }

  this.length--;
  return true;
}
Copy the code

Circular linked list

Tailnode. next = head; tailnode. next = head; When implementing, pay attention to the processing of boundary values, especially when dealing with the first and last elements; Thought with the above realization of the basic consistent, we may wish to try it.

👺 feet with a single loop linked list of code links: single loop linked list

A profound

The following questions are from LeetCode, and the author will provide a solution for each question. This way of thinking is not the best. You are welcome to think positively and leave your own unique opinions.

Since the questions are long, please click the title to see the specific questions.

All listNodes below are in the following format:

class ListNode {
  val: number
  next: ListNode | null
  constructor(val? :number, next? : ListNode |null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}
Copy the code

LeetCode 141. Circular linked list

👺

The input parameter is the head node to determine whether the ring can be formed.

👺

To determine whether there is a loop, the first idea is to borrow the length, if the length can still be recycled, then there is a loop.

let index = 0;
let current = head;
while (current) {
  if (index > size) return true;
  current = current.next;
  index++;
}
return false;
Copy the code

But this problem takes only the head node, so we have to think differently; A pointer must not work, there is no condition to break the loop, the loop is not an infinite loop; Then we use two Pointers, a fast and a slow, can not understand the analogy under the clock or running pressure ring, if there is a ring, a fast and slow must meet.

👺 Code implementation

const hasCycle = (head: ListNode | null) :boolean= > {
  let slow = head;
  let fast = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true; }}return false;
};
Copy the code

LeetCode 2. Add two numbers

👺

Below are two lists stored in reverse order, representing: 342 + 465 = 807

Input: the heads of the two lists l1, l2, to generate a list (list form of sum)

👺

The author saw this problem, the first thought is, respectively through the two linked lists, take the corresponding number, add and store the new list; After the author submitted it with great interest, we got the big numbers. If we can deal with the big numbers in the project, such as big.js, after all, this is a practice problem, we try to change our thinking.

Traverse L1 -> Get342Traverse l2 -> Obtain465
342 + 465 = 807
807In the list7 -> 0 -> 8
Copy the code

So this is a handwritten addition operation, so we add the bits, so 2 + 5 = 7,4 + 6 = 10 which is 0 carry 1, 3 + 4 + 1 = 8

• Go through L1, L2, add by bit

• The new variable indicates whether to carry. If carry, add 1

• Note that if there is still carry at the end, 1 should be added, such as:

89 + 13 = 102
-------------
9 8
3 1
-----
2 0 1
Copy the code

👺 Code implementation

const addTwoNumbers = (
  l1: ListNode | null.l2: ListNode | null,
): ListNode | null= > {
  let current1 = l1;
  let current2 = l2;
  let carryOver = 0; / / carry
  let sum: ListNode = new ListNode(); // add the sum chain to the default header and end with next
  let current: ListNode | null = sum;

  while (current1 || current2) {
    // Two lists may not be the same length as 999 + 1
    letcurrentSum = (current1? .val ||0) + (current2? .val ||0) + carryOver;
    carryOver = 0;

    if (currentSum >= 10) {
      carryOver = 1;
      currentSum -= 10;
    }

    current.next = newListNode(currentSum); current1 = current1? .next ||null; current2 = current2? .next ||null;
    current = current.next;
  }

  if (carryOver > 0) current.next = new ListNode(carryOver);

  return sum.next;
};
Copy the code

LeetCode 24. Switch nodes in a linked list in pairs

👺

Given a linked list, swap the adjacent nodes in pairs and return the swapped list

Input parameter: list head node

👺

The essence of linked list problems is to fiddle with the pointer. Take 1, 3, 4 as an example

[1.next: 3] [3.next: 4], [4.next: null] -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -1.next: 3] - > [1.next: 4]
[4.next: null] - > [4.next: 3]
[3.next: 4- > [3.next: null]
Copy the code

Note the lower boundary value, the first loop handles only two nodes and records the new head value

👺 Code implementation

const swapPairs = (head: ListNode | null): ListNode | null= > {
  let previous: ListNode | null = null;
  let current = head;
  let index = 0; // Record whether it is the first loop
  while (current && current.next) {
    previous = current;
    current = current.next;

    if (index === 0) {
      previous.next = current.next;
      current.next = previous;
      head = current; // Change the header value after the swap
    }

    if (index > 0 && current.next) {
      let node = current;
      current = current.next;
      node.next = current.next;
      previous.next = current;
      current.next = node;
    }

    current = current.next;
    index++;
  }

  return head;
}
Copy the code

Afterword.

🔗 This article code Github link: linked list

🔗 Links to other articles in this series: Starter – Sorting algorithms, Stacks, and queues