Data structure – Learning notes integration
Data Structures – Stacks (Study Notes)
Data Structures – Queues (Study Notes)
Data Structures – Linked Lists (Study Notes)
Data Structures – Collections (Study Notes)
| dictionary and hash table data structure (front end call it objects)
Data structures – binary trees and binary search trees
| binary heap data structure
What is a linked list
A linked list is a basic data structure. It is a linear list. In a linked list, data is stored in scattered locations in memory, and multiple values can be stored. Because the data is stored in different locations, each data can only be accessed through the Pointers provided by its linked list entry, and data can be added by replacing the Pointers on either side.
Real-life lists: trains, chains, scavenger hunts, lots of people holding hands
Common linked list structures
- Singly linked list
- Two-way linked list
- Circular linked list
- Order list
advantage
- In contrast to an array, adding or removing elements does not require moving other elements, making it more efficient to add or remove elements.
- Memory utilization is high and memory space is created only when needed.
disadvantage
It is inefficient to find elements in a linked list, and you must traverse backwards from the first or last node of the list
Singly linked list
concept
Singly linked list is one-way link direction, read access to singly linked list to order from the head start, namely can singly linked list node from scratch is access the next node traversal, until the end, singly linked list node, tail, singly linked list of nodes to forever is null, singly linked list cannot reverse traversal in front of the singly linked list of nodes.
disadvantage
- Finding a linked list element is inefficient, and you have to start at the first node of the list and traverse backwards
Code implementation
/** * Node helper class, representing the item you want to add *@param {*} Element requires the value */ of the linked list element
export class Node{
constructor(element) {
this.element = element; // The item to add to the list
this.next = null; // A pointer to the next node item in the list}}/ / list
export class LinkedList{
constructor() {
this.head = null; // The first node in the list
this.length = 0; // The length of the list
}
/** * adds a new item * to the end of the list@param {*} Element The item to add */
push(element) {
const node = new Node(element); // Create a Node item by passing in the element to be added as a value
let current;
// If head is null, add the first node of the list (add an element to an empty list)
if (this.head === null) {
this.head = node; // Point the item to be added to head
} else {
// If head is not null, the list is not empty (adding elements to the end of a list that is not empty)
Since we only have a reference to the first element, we need a current reference, assign the reference to the first element to current, and loop through the list until we find the last item. * /
// Set the first element of the list to current
current = this.head;
// Loop through the list until the current. Next element is null, at which point you have reached the end of the list and found the last item
while (current.next) {
current = current.next;
}
// Step 2: Find the last item, assign its next to node(the node you currently want to add to the list), and establish a link
current.next = node;
}
// Increments the list length
this.length++; // Update the length of the list
}
/** * Removes an item * from a specific position in the list@param {Number} Index The position from which to remove the linked entry */
removeAt(index) {
// Check for out-of-bounds values (check if the input is valid at the removed element location, refer to array)
if (index >= 0 && index < this.length) {
let current = this.head; // A reference to the current element of the list. Default is the first element of the list
let index = 0; // The variable used for the circular indexed list entry, which defaults to the position of the first element
/** * Removes the first element from the list */
if (index === 0) {
this.head = current.next;
} else {
/** * Removes an item or last item from the list * step 1: increments the index to the last item, current holds a reference to the last item, and previous holds a reference to the previous element */
const previous = this.getElementAt(index - 1);// A reference to the previous element of the current element in the list
current = previous.next;
// console.log(previous, current,index);
/** * If current. Next is null, and previous.next is null, then the last item is removed. Setting previous.next to current. Next removes the current element */
// Link previous to the next item of current: skip current, thereby removing it
previous.next = current.next;
}
// Reduce the length of the list
this.length--; // Update the length of the list
return current.element; // The removed element is returned
} else {
// Not a valid position, return undefined(i.e., no element removed from the list)
return undefined; }}/** * returns the element at a specific position in the list. If no such element exists in the list, undefined is returned. *@param {*} Index The position of an element in a linked list */
getElementAt(index) {
// Check for out-of-bounds values (check for valid positions where elements need to be inserted, refer to arrays)
if (index >= 0 && index <= this.length) {
let current = this.head; // A reference to the current element of the list. Default is the first element of the list
// Iterate through the list until the target index is found
for (let i = 0; i < index && current; i++) {
// When found, set current to the reference to the element in the index position
current = current.next;
}
// Return the element
return current;
}
// Not a valid position, return undefined(i.e. this position does not exist in the list)
return undefined;
}
/** * inserts a new item * at a specific location in the list@param {*} Element needs to be inserted into the list item *@param {Number} Index where the list needs to be inserted */
insert(index, element) {
// Check for out-of-bounds values (check for valid positions where elements need to be inserted, refer to arrays)
if (index >= 0 && index <= this.length) {
const node = new Node(element);// Create a Node item for the item to be inserted
// Add an element at the start of the list
if (index === 0) { // Add in the first position
const current = this.head; // A reference to the element after where the list wants to insert the new element. The default is the first element in the list
// Set Node.next to the first element in the list: current
node.next = current;
// Point the header reference to the insert (node)
this.head = node;
} else {
/** * Adds an element from the middle or end of the list * step 1: increments the index to the last item in the loop, current holds a reference to the element after the place where the list wants to insert a new element, and previous holds a reference to the element before the list wants to insert a new element */
const previous = this.getElementAt(index - 1);// A reference to the element before the place where the list wants to insert the new element
const current = previous.next; // A reference to an element after where the list wants to insert a new element
// console.log(previous, current,position);
/** * * To add a new item between previous and current, link the new item node to the current item, and then change the pointer to node for previous.next * To add a new element at the last location, previous is a reference to the last item in the list, Next points to current,previous.next points to node, and you have a new item * If you add a new element in the middle of the list, you insert node between the previous and current elements. Point Node. next to current and set previous.next to node to have a new item in the list. * /
node.next = current;
previous.next = node;
}
// Increments the list length
this.length++; // Update the length of the list
return true;
} else {
// Not a valid position, return false(that is, no new element is inserted from the list)
return false; }}/** * Outputs the list value * as a string@returns {String}* /
toString() {
// If head is empty, the linked list is an empty list and returns an empty string
if (!this.head) {
return ' ';
}
let objString = `The ${this.head.element}`;
let current = this.head.next; // A reference to the current element of the list defaults to the second element of the list
for (let i = 1; i < this.size() && current; i++) {
objString = `${objString}.${current.element}`
// console.log(objString);
current = current.next;
}
// Return the resulting list element as a string
return objString;
}
/** * Outputs linked list values * as an array@returns {Array}* /
toArray() {
let current = this.head;// A reference to the current element of the list. Default is the first element of the list
let array = []; // Receive element value variables
// Check whether current exists
while (current) {
// If it exists, add it to the array
array.push(current.element);
// Change the current reference to the next list element
current = current.next;
}
// Return the resulting list element as an array
return array;
}
/** * returns the index of the element in the linked list. Returns -1 if the element is not in the list. *@param {*} Element The element that needs to be queried in the list *@returns {Number}* /
indexOf(element) {
let current = this.head;// A reference to the current element of the list. Default is the first element of the list
// Iterate and check if current exists during iteration
for (let i = 0; i < this.length && current; i++) {
// Check if the input element value is equal to the element value of current. Element. If so, the current element is what we want to find
if (element === current.element) {
// If found, return to his position
return i;
}
// Change the current reference to the next list element
current = current.next;
}
// If still not found, the element does not exist in the list, returns -1
return -1;
}
/** * removes an item * from the cluster list@param {*} Element The item that needs to be removed from the list */
remove(element) {
// Use the indexOf method to find the position of the element
let index = this.indexOf(element);
// Then call the removeAt method to pass in the found location for deletion
return this.removeAt(index);
}
/** * returns the number of elements in the list. *@returns {Number}* /
size() {
return this.length;
}
/** * Returns true if the list contains no elements, false * if the list length is greater than 0@returns {Boolean}* /
isEmpty() {
return this.size() === 0;
}
/** * returns the list containing the Head node (Head) */
getHead() {
return this.head;
}
/** * clear the linked list */
clear() {
this.head = undefined; // The list head node is set to empty
this.length = 0; // The list length is reset to 0}}let list = new LinkedList();
list.push(15);
// list.push(10);
// list.push(17);
// console.log(list);
// list.insert(3, 5);
// list.removeAt(2);
// console.log(list);
list.toString();
// console.log(list.toString());
Copy the codeTwo-way linked list
concept
The difference between a bidirectional list and an ordinary unidirectional list is that in a unidirectional list, a node has only the link of the next node in the chain; In a bidirectional list, the links are bidirectional: one chain is one element down, and the other is one element ahead.
In a one-way list, if you miss the element you’re looking for, you go back to the starting point and start all over again, whereas in a two-way list, you can go from beginning to end, or from end to end. We can also access the next or previous element of a particular node.
advantage
- Bidirectionally linked lists provide two ways to iterate: from beginning to end, or from end to end.
- You can access the next or previous element of a particular node.
disadvantage
- Each operation of adding or deleting a node is more complex and requires more references (four).
- The memory footprint is larger than that of one-way linked lists
Code implementation
import { LinkedList, Node } from '/LinkedList/app.js';
// DoublyNode helper classes inherit from Node helper classes
export class DoublyNode extends Node {
constructor(element, next, prev) {
super(element, next);
this.prev = prev; // The previous node of the current node (new)}}/** * Bidirectional lists inherit from LinkedList * The difference between a bidirectional list and a regular list is that in a list, a node has only the link of the next node in the chain; In a bidirectional list, the links are bidirectional: one chain is one element down, and the other is one element ahead. * In a one-way list, if you miss an element while iterating, you need to go back to the beginning and start the iteration again, whereas in a bidirectional list, you can iterate from beginning to end, or from end to end. We can also access the next or previous element of a particular node. * /
export class DoublyLinkedList extends LinkedList {
constructor() {
this.tail = undefined; // A reference to the last element of the list (new)
}
/** * adds a new item * to the end of the list@param {*} Element The item to add */
push(element) {
const node = new DoublyNode(element); // Create a DoublyNode item by passing in the element to be added as a value
let current;
// If head is null, add the first node of the list (add an element to an empty list)
if (this.head === null) {
this.head = node; // Point the item to be added to head
this.tail = node; // Point the end of the list to node
} else {
// If head is not null, the list is not empty (adding elements to the end of a non-empty list), just append to the last node
// Set the last reference at the end of the list to node
this.tail.next = node;
// The reference to the previous item of node is changed to the list end node (this.tail).
node.prev = this.tail;;
// Assign node to the end of the list to complete the insert
this.tail = node;
}
// Increments the list length
this.length++; // Update the length of the list
}
/** * inserts a new item at a specific location in the list (overriding the insert method) *@param {*} Element needs to be inserted into the list item *@param {Number} Index where the list needs to be inserted **/
insert(index, element) {
// Check for out-of-bounds values (check for valid positions where elements need to be inserted, refer to arrays)
if (index >= 0 && index <= this.length) {
const node = new DoublyNode(element);// Create a DoublyNode item for the item to be inserted
let current = this.head; // Stores a reference to the first element of the bidirectional list
// Insert an element at the start of the list
if (index === 0) { // Add in the first position
/** * If the bidirectional list is empty, all you need to do is point head(the first node in the list) and tail(the last node) to node */
if (this.head === null) {
this.head = node; // The first node of the list has a reference to node
this.tail = node; // The last node of the list is referenced to
} else {
/** * If the bidirectional list is not empty,node.next(the pointer to the next node of node) is set to the reference to the first element of the current list -current(i.e. This.head) * and the pointer to the previous node of the current first node reference is set to Node * Finally, set the current head node(this.head) to node(since the index position is 0, node's prev pointer is undefined, so there is no need to manipulate it) */
node.next = this.head; // The next node of node points to the first node of the current list
current.prev = node; // Point the first reference to the first element of the current list to node
this.head = node; // Finally, set the current head node (this.head) to node}}else if (index === this.length) { // Insert an element at the end of the list (new)
/** * Add an element to the end of the list * 1.current holds a reference to the end of the list * 2. the next element of current points to node * 3. the reference to the previous node of node is set to current(a reference to the end of the list) * 4. Update tail to set the reference to the last node of the list to node */
current = this.tail; // current holds a reference to the last node of the list
current.next = node; // The next element of current points to node
node.prev = current; // Set the previous node's reference to current(the last node of the list)
this.tail = node; // Update tail to set the reference to node at the end of the list
} else {
/** * Insert an element from the middle of the list (except for the first and last nodes) * step 1: increments the index index to find the last item, current, which holds a reference to the element after where the list wants to insert the new element. Previous holds a reference to the previous element */ at which the linked list wants to insert a new element
const previous = this.getElementAt(index - 1);// A reference to the element before the place where the list wants to insert the new element
const current = previous.next; // A reference to an element after where the list wants to insert a new element
// console.log(previous, current,position);
/** * * To add a new item between Previous and current, Change the reference to the next node of node to current(current holds a reference to the element after where the list wants to insert a new element) * Next of previous(a reference to the node after previous) is set to node * The prev of current(which holds a reference to an element after where the list wants to insert a new element) is set to node * The previous node's prev is set to previous */
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
// Increments the list length
this.length++; // Update the length of the list
return true;
} else {
// Not a valid position, return false(that is, no new element is inserted from the list)
return false; }}/** * Removes an item * from a specific position in the list@param {Number} Index The position from which to remove the linked entry */
removeAt(index) {
// Check for out-of-bounds values (check if the input is valid at the removed element location, refer to array)
if (index >= 0 && index < this.length) {
let current = this.head; // A reference to the current element of the list. Default is the first element of the list
let index = 0; // The variable used for the circular indexed list entry, which defaults to the position of the first element
/** * Remove the first element from the list * 1
if (index === 0) {
this.head = current.next;
// 2. If current. Next returns undefined, update tail to undefined(new)
if (this.length === 1) {
this.tail = undefined; // Empty the end of the list.
} else {
// 2. If there is more than one entry, empty the reference to the previous node of the head node (new)
this.head.prev = undefined; }}else if (index === this.length - 1) {
/** * Remove the last item from the list (new) * Assign current * 2 to the end of the list. Update the reference to tail to the penultimate element * 3 in the two-way list. Update tail's next pointer to undefined(the next node on the tail is emptied) */
current = this.tail; // Assign the end of the list to current
this.tail = current.prev; // Change the reference to the last node to the previous node of the last node
this.tail.next = undefined; // Clear the next node reference of the last node
} else {
/** * Removes an item from the list (excluding the first and last nodes) * Step 1: increments the index to the last item in the loop, current holds the element to be removed, and previous holds the reference to the previous element */
current = this.getElementAt(index);// The element to be removed from the list
const previous = current.prev; // Remove the reference to the element before the element in the list
// console.log(previous, current,index);
/** * remove the reference to the middle element, in which case current. Next is the reference to the next linked element, and previous.next is set to current. Then point the reference (prev) of the previous element of current. Next to previous */
// Link previous to the next item of current: skip current, thereby removing it
previous.next = current.next;
// Modify current. Next to point to previous
current.next.prev = previous;
}
// Reduce the length of the list
this.length--; // Update the length of the list
return current.element; // The removed element is returned
} else {
// Not a valid position, return undefined(i.e., no element removed from the list)
return undefined; }}/** * returns the list containing Tail */
getTail() {
super.clear(); // Execute the parent class's clear method
this.tail = undefined; // Set the end of the list to undefined
}
/** * outputs the value of the reverse list * as a string@returns {String}* /
inverseToString() {
// If head is empty, the linked list is an empty list and returns an empty string
if (!this.tail) {
return ' ';
}
let objString = `The ${this.tail.element}`; // Element at the end of the list
let previous = this.tail.prev; // A reference to the element before the last element of the list
while(previous ! = =null) {
objString = `${objString}.${previous.element}`;
previous = previous.prev;
}
// Return the resulting list element as a string
returnobjString; }}/** Performance optimization related: * 1. Insert elements at the end of the bidirectional list if the result is no. * 2. If position is greater than Length /2, it is better to iterate from the end rather than from the beginning (thus iterating through fewer elements in the bidirectional list). * /
let list = new DoublyLinkedList();
list.push(13);
console.log(list);
Copy the codeCircular linked list
concept
Circular lists can have only one-way references, like linked lists, or they can have bidirectional references, like bidirectional lists. The only difference between a circular list and a linked list is that the last element points to a pointer to the next element, not to undefined, but to the first element.
advantage
- The traversal can start from any node, which increases the flexibility of traversal
Code implementation
import { LinkedList, Node } from '/LinkedList/app.js';
/** * Circular lists can inherit from the LinkedList class or the DoublyLinkedList class * Circular lists can have one-way references, like lists, or two-way references, like bidirectional lists. The only difference between a circular list and a linked * list is that the pointer to the next element (tail.next) does not refer to *undefined, but to the first element (head). * /
export class CircularLinkedList extends LinkedList {
constructor(){}/** * adds a new item * to the end of the list@param {*} Element The item to add */
push(element) {
const node = new Node(element); // Create a Node item by passing in the element to be added as a value
let current;
// If head is null, add the first node of the list (add an element to an empty list)
if (this.head == null) {
this.head = node; // Point the item to be added to head
} else {
// If head is not null, the list is not empty (adding elements to the end of a list that is not empty)
/** * step 1: Find the last element */
current = this.getElementAt(this.size() - 1);
// The first element of the list points to the next item of the current
current.next = node;
}
// Set the next item of node to the head of the linked list to complete the loop (new)
node.next = this.head;
this.length++; // Update the length of the list
}
/** * inserts a new item * at a specific location in the list@param {*} Element needs to be inserted into the list item *@param {Number} Index where the list needs to be inserted */
insert(element, index) {
// Check for out-of-bounds values (check for valid positions where elements need to be inserted, refer to arrays)
if (index >= 0 && index <= this.length) {
const node = new Node(element); // Create a Node item for the item to be inserted
let current = this.head; // A reference to the current element of the list. Default is the first element of the list
// Add an element at the start of the list
if (index === 0) { // Add in the first position
if (this.head === null) {
// If there are no items in the list
this.head = node; // Set the list header to node
node.next = this.head; // The next element of node points to the head of the list (new)
} else {
// If the list is not empty
node.next = current; // Point Node.next to the node referenced by the current head (current variable)
current = this.getElementAt(this.size()); // Get a reference to the last list item
this.head = node; // Update the header element to the newly inserted element node
current.next = this.head; // Next of the last node (current) points to the new head node to complete the loop list (new)}}else {
/** * Adds an element from the middle or end of the list * step 1: increments the index to the last item in the loop, current holds a reference to the element after the place where the list wants to insert a new element, and previous holds a reference to the element before the list wants to insert a new element */
const previous = this.getElementAt(index - 1);// A reference to the element before the place where the list wants to insert the new element
/** * * To add a new item between previous and current, link the new item node to the current item, and then change the pointer to node for previous.next * To add a new element at the last location, previous is a reference to the last item in the list, Next points to current,previous.next points to node, and you have a new item * If you add a new element in the middle of the list, you insert node between the previous and current elements. Point Node. next to current and set previous.next to node to have a new item in the list. * /
node.next = previous.next;
previous.next = node;
}
this.length++; // Update the length of the list
return true;
}
return false;
}
/** * Removes an item * from a specific position in the list@param {Number} Index The position from which to remove the linked entry */
removeAt(index) {
// Check for out-of-bounds values (check if the input is valid at the removed element location, refer to array)
if (index >= 0 && index < this.length) {
let current = this.head; // A reference to the current element of the list. Default is the first element of the list
/** * removes the first element */ from the list
if (index === 0) { // If the list element to be removed is the first
// If the list length is 1
if (this.size() === 1) {
this.head = undefined; // Empty the LinkedList header directly (as implemented in the LinkedList class)
} else {
// Remove an item or the last item from the list (new)
const removed = this.head; // First save a reference to the current head element
current = this.getElementAt(this.size() - 1); // To get a reference to the last element of the circular list
this.head = this.head.next; // Update the head element to point to the second element (head.next)
current.next = this.head; // Point the last element (current. Next) to the new head
current = removed; // Update the current variable reference to removed(used to return currentl.element)}}else {
/** * removes an item or the last item */ from the list
// no need to update last element for circular list
const previous = this.getElementAt(index - 1); // A reference to the previous element of the current element in the list
/** * If current. Next is null, and previous.next is null, then the last item is removed. Setting previous.next to current. Next removes the current element */
// Link previous to the next item of current: skip current, thereby removing it
current = previous.next;
previous.next = current.next;
}
// Reduce the length of the list
this.length--; // Update the length of the list
return current.element; // The removed element is returned
}
// Not a valid position, return undefined(i.e., no element removed from the list)
return undefined; }}let list = new CircularLinkedList();
list.push(13);
console.log(list);
Copy the codeOrder list
concept
An ordered list is a list structure that keeps elements ordered. In addition to using sorting algorithms, we can also insert elements into the correct positions to keep the list organized.
In an ordered linked list, the data is ordered by key values. Ordered lists can also be used in most cases where ordered arrays are required. Ordered lists are superior to ordered arrays in the speed of insertion (because elements don’t need to be moved), and linked lists can scale to the full useful memory, whereas arrays can be limited to a fixed size.
(The following code example is an ordered list descending from head to tail)
advantage
- Compared to arrays, which are limited to a fixed size in most programming languages (PS:JavaScript arrays are not fixed sizes)
- Ordered lists are faster than ordered arrays
Code implementation
import { LinkedList } from '/LinkedList/app.js';
/** * Ordered lists inherit from the LinkedList class * Ordered lists are lists that keep elements in order. In addition to using sorting algorithms, we can also insert elements into the correct positions to keep the list organized. * Here we assume an ordered linked list descending from head to tail */
// A constant for comparison (to keep code elegant)
export const Compare = {
LESS_THAN: -1.// If the first element is less than the second, it returns -1
BIGGER_THAN: 1.If the first element is greater than the second, it returns 1
EQUALS: 0 // If the element has the same reference, it returns 0
};
// Compare methods
export function defaultCompare(a, b) {
// If the element has the same reference, it returns 0
if (a === b) {
return Compare.EQUALS;
}
// If the first element is less than the second, it returns -1, otherwise it returns 1
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
export class SortedLinkedList extends LinkedList {
constructor() {
this.compareFn = compareFn;
}
/** * adds a new item * to the end of the ordered list@param {*} Element The item to add */
push(element) {
// If the ordered list is empty
if (this.isEmpty()) {
// Call the parent's push method directly to upload the new item
super.push(element);
} else {
// If the ordered list is not empty
const index = this.getIndexNextSortedElement(element); // Get the correct position of the inserted element
super.insert(element, index); // Call the insert method of LinkedList, passing in that location to keep the list in order}}insert(element, index = 0) {
if (this.isEmpty()) {
return super.insert(element, index === 0 ? index : 0);
}
const pos = this.getIndexNextSortedElement(element);
return super.insert(element, pos);
}
/** * gets the correct position of the inserted element *@param {*} Element requires a query for the item */ where the element is inserted
getIndexNextSortedElement(element) {
let current = this.head; // Save the list header reference with current
// Loop through the ordered list
let i = 0;
for (; i < this.size() && current; i++) {
/** * compares the passed element *@param {*} Element requires a query for the item * where the element is inserted@param {*} Current. Element Element content of the current loop item */
const comp = this.compareFn(element, current.element);
// Insert an element in an ordered list that is smaller than current
if (comp === Compare.LESS_THAN) {
// Return the found subscript
return i;
}
// Group no continues the loop iteration
current = current.next;
}
// If not, return 0
returni; }}let list = new SortedLinkedList();
list.push(13);
console.log(list);
Copy the code