Stage Poetry

The most serious injury is the cold weather in the evening, and the haggard companions are beyond words.
Invite the wine to destroy the intestines three cups of drunkenness. Seek fragrance and frighten dreams five colder.
Chai-tou Fengxieqing has tears, tea stamps my fate;
The small building is lonely and rainy. It's hard to get round as well as hook.

Preface

This chapter is a re-reading of the series "Learning JavaScript Data Structure and Algorithms". This chapter mainly describes the data structure-linked list, as well as the process and principle of implementing the linked list.

linked list

Linked list, why do we have this data structure? Of course, there must be a reason!

Array - The most common and convenient data structure, But, when we insert or move items from the beginning or middle of an array, the cost is high because we need to move array elements.

A linked list is an orderly collection of elements stored. Elements in a linked list are not placed continuously in memory. Each element consists of an element node that stores itself and a reference (pointer or link) to the next element.

Implementing linked list

We need to implement the structure of the linked list and the corresponding methods, roughly as follows: element insertion, removal, get the length of the linked list, query elements, whether empty, and so on... More details can be seen in the code implementation logic.

/**
 * Node Node class for generating references to its own nodes and the next element
 */
class Node {
  constructor(element) {
    this.element = element
    this.next = undefined
  }
}

/**
 * defaultEquals() Used to compare two non-object classes to see if the values are equal
 */
function defaultEquals (a, b) {
  return a === b
}

/**
 * LinkedList linked list
 * Features: The linked list stores an orderly set of elements, but elements are not stored continuously in memory. Each element has a node that stores the element itself and a reference to the next element.
 */
class LinkedList {
  constructor (equalsFn = defaultEquals) {
    // Link List Length
    this.count = 0
    // First element reference
    this.head = undefined
    // Used to compare whether elements are equal, defaultEquals is default by default, allowing custom functions to be passed in to compare whether two objects are equal.
    this.equalsFn = equalsFn
  }
}

push()

/**
 * push() Add elements to the list
 * @param {*} element Elements to be added
 */
push (element) {
  let node = new Node(element)
  let current
  // Judging whether the list is empty
  if (this.head == null) {
    this.head = node
  } else {
    // Query the last element - feature current. next = null
    current = this.head
    while (current.next != null) {
      current = current.next
    }
    // Reference the next element of the last element to node
    current.next = node
  }
  this.count++
} 

getElementAt()

/**
 * getElementAt() Returns the index location element
 * @param {Number} index Index location
 * @returns {*} node
 */
getElementAt (index) {
  // Judging whether the index is valid
  if (index < 0 || index > this.count) {
    return undefined
  }
  let node = this.head
  for (let i = 0; i < index && node != null; i++) {
    node = node.next
  }
  return node
}

insert()

/**
 * insert() Insert elements anywhere
 * @param {*} element Elements to be inserted
 * @param {Number} index Specified index location
 * @returns {Boolean}
 */
insert (element, index) {
  // Judging whether it is a legal index
  if (index < 0 || index > this.count) {
    return false
  }
  // Instance node
  let node = new Node(element)
  // Insert - first position
  if (index === 0) {
    let current = this.head
    node.next = current
    this.head = node
  } else {
    // Find the previous element at the specified index location
    let previous = this.getElementAt(index - 1)
    let current = previous.next

    // The insertion is completed by pointing the next reference of the previous element to the currently added node and the next reference of the node to the current.
    previous.next = node
    node.next = current
  }
  // List length + 1
  this.count++
  return true
}

removeAt()

/**
 * removeAt() Remove elements at specified locations
 * @param {Number} index
 * @returns {*} element Removed elements
 */
removeAt (index) {
  // Judging whether it is a legal index
  if (index < 0 || index > this.count) {
    return undefined
  }

  let current = this.head

  // Consider whether it's the first item in the list
  if (index === 0) {
    this.head = current.next
  } else {
    // Method 1. Use for loop iteration to get the element at the specified index position
    // Used to retrieve the previous location element
    // let previous
    // for (let i = 0; i < index; i++) {
    //   previous = current
    //   current = current.next
    // }
    // // Skip the current element and point next from the previous element to the next element
    // previous.next = current.next

    // Method 2. With the help of getElementAt() method
    // Query the last element of the index location
    let previous = this.getElementAt(index - 1)
    // Skip the intermediate element and point the next of the previous element to the next element
    current = previous.next
    previous.next = current.next
  }
  this.count--
  return current.element
}

indexOf()

/**
 * indexOf() Index Location of Query Elements
 * @param {*} element Elements to be queried
 * @returns {Number} index Index location, return - 1 if nonexistent
 */
indexOf (element) {
  let current = this.head
  for (let i = 0; i < this.count && current != null; i++) {
    // Determine whether two elements are identical
    if (this.equalsFn(element, current.element)) {
      return i
    }
    current = current.next
  }
  return - 1
}

remove()

/**
 * remove() Removing Elements
 * @param {*} element Elements to be removed
 * @returns {*} element Removed elements
 */
remove (element) {
  // Get the index location
  let index = this.indexOf(element)
  // Remove the element at the specified index location
  return this.removeAt(index)
}

size()

/**
 * size() Return list length
 * @returns {Number} Link List Length
 */
size () {
  return this.count
}

isEmpty()

/**
 * isEmpty() Judging whether the list is empty
 * @returns {Boolean}
 */
isEmpty () {
  return this.count === 0
}

getHead()

/**
 * getHead() Get the first element of the list
 * @returns {*}
 */
getHead () {
  if (this.head != null) {
    return this.head.element
  }
  return undefined
}

clear()

/**
 * clear() Clear the list
 */
clear () {
  this.count = 0
  this.head = undefined
}

toString()

/**
 * toString() String display of linked list
 * @returns {String}
 */
toString () {
  // Judge whether it is empty
  if (this.isEmpty()) {
    return ''
  }
  let objStr = `${this.head.element}`
  let current = this.head.next
  for (let i = 1; i < this.count; i++) {
    objStr = `${objStr},${current.element}`
    current = current.next
  }
  return objStr
}

Use linked lists

let linkedList = new LinkedList()

console.log(linkedList.isEmpty()) // true

// push tail pressing element
linkedList.push(15)
linkedList.push(20)
/*
  LinkedList {
    count: 2,
    head: Node {
      element: 15,
      next: Node {
        element: 20,
        next: undefined
      }
    },
    equalsFn: [Function: defaultEquals]
  }
*/
console.log(linkedList)

console.log(linkedList.isEmpty()) // false

// getElementAt() Elements that specify the location of the index
let node = linkedList.getElementAt(1)
console.log(node)

// insert() insert elements at any index position
linkedList.insert(22, 1)
linkedList.insert(33, 1)
console.log(linkedList.toString()) // 15,33,22,20

// removeAt() removes the element at the specified index location
console.log(linkedList.removeAt(1)) // 33

// remove() removes elements
console.log(linkedList.remove(15)) // 15

console.log(linkedList.toString()) // 22,20

console.log(linkedList.getHead()) // 22

console.log(linkedList.size()) // 2
console.log(linkedList.toString()) // 22,20

console.log(linkedList.isEmpty()) // false

linkedList.clear()
console.log(linkedList.isEmpty()) // true

Epilogue

Above is what Huge shares with you today. My favorite buddies remember to collect, forward, click the button in the lower right corner to see. I recommend it to more buddies. Welcome to leave more messages for communication.

Long press sweep code attention, more handsome and more beautiful yo! Pay attention to Hu Ge's public address, but continue to have in-depth exchanges with Hu Ge.