JS implementation of data structure – single linked list

1. The singly linked list

• A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list.
• Features: Insert time complexity O(1), much faster than linear tables, but lookup requires O(n), while linear tables and sequential tables have time complexity O(logn) and O(1) respectively.

// Insert O(1) to find O(n)

// Create a node, element, to store information, and next to point to the next node
class Node {
  constructor(element) {
    this.element = element;
    this.next = null}}class LinkList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  // append the element
  append(element) {
    // Create a node
    const node = new Node(element)
    // Record the current position
    let current = null;
    if(this.head === null) {
      // Assign node directly to head
      this.head = node
    }else {
      // Start the loop from head and find that the last next is null, then assign current. Next to
      current = this.head;
      while(current.next) {
        current = current.next
      }
      current.next = node;
    }
    this.length++
  }

  // Find the position of the list element index = -1
  indexOf(elemet) {
    let index = -1;
    let current = this.head;
    while(current.next) {
      if(elemet === current.element) {
        return index + 1
      }
      index++;
      current = current.next
    }
    return -1
  }

  // Find the element where postion is located
  getElementAt(position) {
    if(position < 0 || position >= this.length) {
      return null
    }
    let current = this.head
    for(let i = 0; i < position; i++) {
      current = current.next
    }
    return current;
  }

  // Insert the specific location
  insert(position, element) {
    // Create a node
    const node = new Node(element);
    // Prevent trespassing
    if(position < 0 || position > this.length) {
      return null;
    }
    // If position is 0, insert it directly into this.head
    if (position === 0) {
      node.next = this.head;
      this.head = node
    } else {
      let previous = this.getElementAt(position - 1);
      node.next = previous.next;
      previous.next = node;
    }
    this.length++
  }

  // Delete the specified position
  removeAt(position) {
    if(position < 0 || position > this.length) {
      return null
    }
    / / get
    let current = this.head
    if(position === 0) {
      this.head = current.next;
    }else {
      let previous = this.getElementAt(position - 1)
      current = previous.next;
      previous.next = current.next;
    }
    this.length--
  }

  // Remove the specified element
  remove(element) {
    const position = this.indexOf(element)
    this.removeAt(position); }}let list = new LinkList()
list.append('name')
list.append('age')
list.append('leng')
list.append('last')
console.log(list);

// const index = list.indexOf('leng');
// console.log(index); / / 2

// console.log(list.indexOf('where'))

// console.log(list.getElementAt(2))

list.insert(2.'man')

console.log(list)

list.removeAt(2)

list.remove('age')
console.log(list)
Copy the code