Linked lists and arrays

Like an array, a list can be used to store a list of elements, but the implementation mechanism for lists and arrays is completely different.

An array of

  • Storing multiple elements, arrays (or lists) are probably the most commonly used data structures.

  • Almost every programming language has a default implementation of the array structure, providing a convenient [] syntax for accessing array elements.

  • Array disadvantages:

    To create an array, you need to apply for a continuous memory space (a block of memory) with a fixed size. If the current array cannot meet the capacity requirements, you need to expand it. (This is usually done by applying for a larger array, such as 2x, and then copying the elements from the original array.)

    Inserting data at the beginning or middle of an array is expensive and requires a lot of element displacement.

The list

  • Another option for storing multiple elements is to use a linked list.

  • Unlike arrays, the elements in a linked list need not be contiguic in memory.

  • Each element of a linked list consists of a node that stores the element itself and a reference (called a pointer in some languages) to the next element.

  • Linked list advantages:

    Memory space need not be continuous, can make full use of the computer’s memory, to achieve flexible memory dynamic management.

    Linked lists do not have to be sized when they are created, and can be sized indefinitely.

    When inserting and deleting data, the time complexity of linked list can reach O(1), which is much more efficient than array.

  • Linked list disadvantages:

    To access an element in any location, you need to start from scratch. (Cannot access any element without skipping the first element)

    Elements cannot be accessed directly through the subscript value, and need to be accessed from the beginning until the corresponding element is found.

    While it is easy to get to the next node, it is difficult to get back to the previous node.

Singly linked list

A unidirectional list is like a train, where you have a locomotive that connects to a node that has passengers on it, and that node connects to the next node, and so on.

  • The train structure of the linked list

  • The data structure of a linked list

The head attribute points to the first node in the list. The last node in the list points to NULL. When there are no nodes in the list, head refers to null.

  • The structure of the train with data added

Introduction to the list

Let’s treat each node of the list as an object in JS. I’ll write such a piece of code as shown below.

// Simple linked list

let node1 = { data: 1.next: null }
let node2 = { data: 2.next: null }
let node3 = { data: 3.next: null }
let node4 = { data: 4.next: null }
let node5 = { data: 5.next: null }

let head = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

console.log(head)
Copy the code

We can see the print on the browser side, 1, 2, 3, 4, 5. Is that exactly what we want.

Let’s encapsulate the list again, using class to construct the list of nodes, also can achieve the desired effect.


class Node {
  constructor(data) {
    this.data = data
    this.next = null}}let node1 = new Node(1)
let node2 = new Node(2)
let node3 = new Node(3)
let node4 = new Node(4)
let node5 = new Node(5)


let head = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

console.log(head)
Copy the code

Then use another loop to encapsulate the code and make it look less tedious. The transformation, also achieved the desired effect.


class Node {
  constructor(data) {
    this.data = data
    this.next = null}}let head = null
let vars = {}
// Build data in batches
for (let i = 1; i <= 5; i++) {
  let key = `node${i}`
  vars[key] = new Node(i)
}
// Assemble the data into a linked list
for (let i = 1; i <= 5; i++) {
  let key = `node${i}`
  let keyNext = `node${i + 1}`
  if (i === 1) {
    head = vars[key]
  }
  vars[key].next = vars[keyNext]
}
console.log(head)
Copy the code

So with that in mind, we can start thinking about the basic operations of a linked list and try to implement them,

Linked list common operations

  • append(element)Adds a new item to the end of the list.
  • insert(position, element)Inserts a new item at a specific location in the list.
  • get(position)Gets the element at the corresponding location.
  • indexOf(element)Returns the index of an element in a linked list. Returns -1 if the element is not in the list.
  • update(position, element)Modifies an element at a location.
  • removeAt(position)Removes an item from a specific location on a linked list.
  • remove(element)Removes an item from a linked list.
  • isEmpty()Return trun if the list contains no elements, false if the list is longer than zero.
  • size()Returns the number of elements in the list, similar to the length attribute of an array.
  • print()Prints the current existing nodes in the list as a stringdataThe value of the.

Code implementation

Before we do that, let’s write the basic structure of the list in code

// List node node
class Node {
  constructor(data) {
    this.data = data
    this.next = null}}class LinkedList {
  constructor() {
    // The header of the list
    this.head = null
    // Record the length of the list
    this.length = 0}}Copy the code

Append () method

  / / insert
  append(data) {
    // 1. If there is no data in the linked list, directly execute the new node
    // 2. If there is data in the list, find the last node and point next to the new node
    let newNode = new Node(data)
    if (this.length === 0) {
      this.head = newNode
    } else {
      // Iterate through the list to find the last node
      let current = this.head
      // If the next node exists, the next node is traversed
      while (current.next) {
        current = current.next
      }
      current.next = newNode
    }
    this.length++
  }
Copy the code

Process diagram

  • First, letcurrentNodeIt points to the first node.

  • throughwhileCycle to makecurrentPoint to the last node, and then pass throughcurrent.next = newNodeTo make the last node point to the new nodenewNode.

The test code

We also get the same result that we did manually.

const LinkedList = require('./linked-list')
const linkedList = new LinkedList()

linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.append(4)
console.log(linkedList)

console.log(linkedList.print())
Copy the code

Insert () method

  insert(position, data) {
    // Check the insertion position
    if (position < 0 || position > this.length) {
      return false
    }

    // Create a new node
    let newNode = new Node(data)
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else {
      // Find the previous node
      let index = 0
      let prevNode = null
      let current = this.head
      // Update currentNode and previousNode by iterating between 0 and position
      // Until the insertion position is found
      while (index < position) {
        prevNode = current
        current = current.next
        index++
      }
      prevNode.next = newNode
      newNode.next = current
    }
    this.length++
  }
Copy the code

The test code

const LinkedList = require('./linked-list')


const linkedList = new LinkedList()


linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.append(4)

linkedList.insert(0.100)

linkedList.insert(4.99)
console.log(linkedList.print())
Copy the code

getData()

  getData(position) {
    // 1
    if (position < 0 || position >= this.length) return null;

    // 2, obtain the data of the specified position node
    let currentNode = this.head;
    let index = 0;

    while (index++ < position) {
      currentNode = currentNode.next;
    }
    // 3, return data
    return currentNode.data;
  }
Copy the code

indexOf()

  indexOf(data) {

    let currentNode = this.head;
    let index = 0;

    while (currentNode) {
      if (currentNode.data === data) {
        return index;
      }
      currentNode = currentNode.next;
      index++;
    }

    return -1;
  }
Copy the code

update()

  update(position, data) {
    // Make an out-of-bounds judgment when it comes to position
    // 1
    if (position < 0 || position >= this.length) return false;

    // 2. Iterate through the loop to find the node of the specified position
    let currentNode = this.head;
    let index = 0;
    while (index++ < position) {
      currentNode = currentNode.next;
    }

    // 3. Modify node data
    currentNode.data = data;

    return currentNode;
  }
Copy the code

removeAt()

  removeAt(position) {
    // 1
    if (position < 0 || position >= this.length) return null;

    // 2. Delete the specified position node
    let currentNode = this.head;
    if (position === 0) {
      // Position = 0
      this.head = this.head.next;

    } else {
      // Position > 0
      // Loop through the node to find the specified position, and assign the value to currentNode

      let previousNode = null;
      let index = 0;

      while (index < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
        index++
      }

      // The next of the previous node refers to the next of the current node, which is equivalent to removing the current node.
      previousNode.next = currentNode.next;
    }

    // 3. Update the list with length -1
    this.length--;

    return currentNode;
  }

Copy the code

remove()

remove(data) {
    this.removeAt(this.indexOf(data));
}

Copy the code

isEmpty()

isEmpty() {
    return this.length === 0;
}

Copy the code

size()

size() {
    return this.length;
}
Copy the code

So, in a while loop, whether we’re going to determine current or current. Next is whether we’re going to do current after the loop. If we’re going to do current, we’re going to take current.