What is a linked list

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. You can refer to a train, which is linked by compartments. 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 Pointers, so implementing them requires extra care. We can directly access any element anywhere in the array, but to access an element in the middle of the list, we iterate through the list from the starting point (the header) until we find the desired element.

2. Create linked lists

  • 1. Skeleton of the LinkedList class
import { defaultEquals } from '.. /util'; Import {Node} from '.. /util'; Class LinkedList {// You can pass in a custom method to compare elements equal, Constructor (equalsFn = defaultEquals) {this.count = 0; This. head = undefined; // The first element his.equalsfn = equalsFn; Push (element) {} // Add a new element to the end of the list insert(Element,position) {} // add a new element to a specific position in the list getElementAt(index) {} // Remove (element) {} // remove an element from the list indexOf() {} // return the indexOf the element in the list, RemoveAt (position) {} // Remove an element from a specific position in the list isEmpty() {} size() {} // Return the number of elements in the list toString() {} // Returns a string for the entire list}Copy the code
  • DefaultEquals and Node
export function defaultEquals(a, b) { return a === b } export class Node { constructor(element) { this.element = element; this.next = undefined; }}Copy the code

Implement each method of linked list

  • 1. Add elements to the end of push
push(element) { const node = new Node(element); let current; If (this.head == null) {this.head = node; } else {current = this.head; // The current element while(current. Next! = null) {// Get last item current = current. Next; } // Assign next to a new element and create a link current-next = node; } this.count ++; }Copy the code
  • 2, insert insert elements anywhere
insert(element, index) { if (index >= 0 && index <= this.count) { const node = new Node(element); If (index === 0) {// Add const current = this.head; node.next = current; this.head = node; } else { const previous = this.getElementAt(index - 1); const current = previous.next; node.next = current; previous.next = node; } this.count ++; return true; } return false; }Copy the code
  • 3. GetElementAt finds element locations
getElementAt(index) { if (index >= 0 && index < this.count) { let node = this.head; for (let i = 0; i < index && node ! = null; i++) { node = node.next; } return node; } return undefined; }Copy the code
  • 4. RemoveAt removes elements from the specified location
RemoveAt (index) {if (index >= 0 && index < this.count) {let current = this.head; If (index === 0) {this.head = current. Next; } else { const previous = this.getElementAt(index - 1); current = previous.next; previous.next = current.next; } this.count--; return current.element; } return undefined; }Copy the code
  • 5, indexOf
IndexOf (element) {let current = this.head; for (let i = 0; i < this.count && current ! = null; i++) { if (this.equalsFn(element, current.element)) { return i; } current = current.next; } return -1; }Copy the code
  • Remove Removes the specified element
Remove (element) {const index = this.getelementat (element); return this.removeAt(index); }Copy the code
  • 7. IsEmpty checks whether the list isEmpty
isEmpty() {
  return this.size() === 0;
}

Copy the code
  • ToString converts lists to strings
toString() { if (this.head == null) { return ''; } let objString = `${this.head.element}`; let current = this.head.next; for (let i = 1; i < this.size() && current ! = null; i ++) { objString = `${objString},${current.element}`; current = current.next; } return objString; }Copy the code
  • 9, size returns the length of the list
size() {
  return this.count;
}
Copy the code
const list = new LinkedList();
list.push(12);
list.push(11);
list.push(13);
list.push(14);
list.insert(3, 3);
list.removeAt(2);
console.log(list);

Copy the code