This is the 5th day of my participation in the August More Text Challenge

1. Introduction

A linked list stores an ordered collection of elements, but unlike an array, the elements in a linked list are not placed consecutively in memory. Each element consists of a node that stores the element itself and a reference (also known as a pointer or link) to the next element.

One advantage of linked lists over traditional arrays is that you don’t need to move other elements when you add or remove them. However, linked lists require the use of Pointers, so implementing lists requires extra care. Another detail of arrays is that you can directly access any element at any location, whereas to access an element in the middle of a linked list, you need to iterate through the list from the starting point (the header) until you find the desired element.

2. The basic structure of linked lists

A linked list is composed of nodes, each of which contains basic units called data fields (value) and pointer fields (Next). It is also a recursive data structure. It maintains a logical order between data, but storage space does not have to be stored sequentially.

2.1 Basic elements of linked lists

  • Node: Each node has two parts. The data domain (value) stores user data. The pointer field (next) holds a pointer to the next element.
  • Head: The head node always points to the first node
  • Tail: Tail always points to the last node
  • None: The pointer field of the last node in the list is None

2.2 Linked list method

  • Append (Element) : Adds a new item to the end of the list.
  function append (element) {
    let node = new Node(element)
    let head = this.head
    let current
    // The linked list is empty
    if (this.head === null) {
      this.head = node
    } else {
      current = this.head
      while(current.next && current.next ! == head) { current = current.next } current.next = node }// Keep end to end
    node.next = head
    this.length ++
  }
Copy the code
  • Insert (position, element) : Inserts a new item into a specific position in the list.
  function insert (element, point) {
    if (point >=0 && point <= this.length) {
      let node = new Node(element)
      let current = this.head
      let previous
      let index = 0
      if (point === 0) {
        node.next = current
        while(current.next && current.next ! = =this.head) {
          current = current.next
        }
        this.head = node
        current.next = this.head
      } else {
        while (index++ < point) {
          previous = current
          current = current.next
        }
        previous.next = node
        // end to end
        node.next = current === null ? head : current
      }
      this.length++
      return true
    } else {
      return false}}Copy the code
  • Remove (element) : Removes an item from a list.
  function remove (element) {
    let index = this.find(element)
    // The deleted node is returned after deletion
    return this.removeAt(index)
  }
Copy the code
  • IndexOf (element) : returns the indexOf an element in a list. Returns -1 if the element is not in the list.
  • RemoveAt (position) : Removes an item from a specific position in the list.
  function removeAt (point) {
    if (point > -1 && point < this.length) {
      let current = this.head
      let index = 0
      let previous
      if (point === 0) {
        this.head = current.next
        while(current.next && current.next ! = =this.head) {
          current = current.next
        }
        current.next = this.head
      } else {
        while (index++ < point) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length--
      return current.element
    } else {
      return null}}Copy the code
  • IsEmpty () : Returns true if the list contains no elements, false if the list length is greater than zero.
  function isEmpty () {
    return this.length === 0
  }
Copy the code
  • Size () : Returns the number of elements in the list. Similar to the length property of an array.
  function size () {
    return this.length
  }
Copy the code

2.3 Linked list code structure

class Node {
  constructor (element) {
    this.element = element
    this.next = null}}class List {
  constructor () {
    // Initializes the list length
    this.length = 0
    // Initializes the first node in the list
    this.head = null
  }

  find (element) {
    let current = this.head
    let index = 0
    if (element == current.element){
        return 0;
    }
    while(current.next && current.next ! = =this.head) {
      if(current.element === element) {
        return index
      }
      index++
      current = current.next
    }
    if (element == current.element){
        return index;
    }
    return -1
  }

  print () {
    let current = this.head
    let result = ' '
    while(current.next && current.next ! = =this.head) {
      result += current.element + (current.next ? '- >' : ' ')
      current = current.next
    }
    result += current.element
    return result
  }
}
Copy the code

The above is linked list learning record, to be continued.