A list of multiple elements
The elements are stored discontiguously, connected by the next pointer
There are no linked lists in JavaScript
You can use Object to simulate linked lists
Arrays VS linked lists
Array: Moves elements when adding or deleting non-primacy elements
Linked list: When adding or deleting non-first elements, you don’t need to move the elements, just change the direction of next
Definition 1.
Stores an ordered collection of elements
It’s not continuous
A node that stores the element itself + a reference to the next element
2. Specific operations
create
class Node { // Represents the item you want to add to the list
constructor(element, next) {
this.element = element;
this.next = next; // A pointer to the next element in the list}}class LinkedList {
constructor() {
this.count = 0;
this.head = undefined; // Save the reference}}Copy the codemethods
// Returns the element at a specific location
getElementAt(index) {
if (index >= 0 && index <= this.count) {
let node = this.head;
for (let i = 0; i < index && node ! =null; i++) {
node = node.next; // Loop node to the index element
}
return node;
}
throw new Error("out range");
}
// Returns the index of the element in the linked list. Returns -1 if the element is not in the list
indexOf(element) {
let current = this.head;
for (let i = 0; i < this.size() && current ! =null; i++) {
if (current.element === element) {
return i;
}
current = current.next;
}
return -1;
}
// Add a new element to the tail
push(element) {
let node = new Node(element);
if (this.head == null) { // If the list is empty, add it directly to the header
this.head = node;
} else {
let current = this.head;
while(current.next ! =null) { // Get the last item
current = current.next;
}
. / / when the current next = = undefined | | null, that is to list the tail
//** The next element of the last node in the list is always undefined or null**
current.next = node; // Assign its next element to the new element and create a link
}
this.count++;
}
// You can also use this method
/ /...
// else {
// **let current = this.getElementAt(this.count - 1); ** // Find node
// **current.next = node; 支那
/ /}
/ /...
// Insert a new element at a specific location
insert(element, index) {
if (index >= 0 && index <= this.count) { // Within the range
let node = new Node(element);
if (index === 0) { // Add it directly to the header
const current = this.head;
node.next = current;
this.head = node;
} else {
const pre = this.getElementAt(index - 1); // Get the position of the previous node
node.next = pre.next; // The newly created node is assigned the value pre-.next
pre.next = node; // point pre-.next to the newly created node
}
this.count++; / / length + 1
return true;
}
throw new Error("out range");
}
// Remove an element from a specific position
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) { // Remove the first item
this.head = current.next; // You can also use head=head.next
} else {
for (let i = 0; i < index; i++) { // From the removed position, the element moves forward one bit
let pre = current;
current = current.next;
}
// The pre pointer points to the first bit of the element to be removed and the next pointer points to the next bit of the element to be removed
pre.next = current.next;
}
this.count--;
return current.element;
}
return undefined; // If index is not in the range, return undefined
}
// Remove an element
remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.count;
}
getHead() {
return this.head;
}
clear() {
this.head = undefined;
this.count = 0;
}
// Convert the LinkedList object to a string
toString() {
if (this.head == null) {
return ' ';
}
let objString = `The ${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
3. Bidirectional linked lists
Links are bidirectional: one chain down the element, the other chain up the element
Advantage: In a one-way linked list, if you miss an element while iterating, you need to go back to the starting point and start iterating again
A bidirectional list controls both the next and prev Pointers
class Node {
constructor(element, next) {
this.element = element;
this.next = next; }}function defaultEquals(a, b) {
return a === b;
}
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.count = 0;
this.head = undefined;
this.equalsFn = equalsFn; }}class DoublyNode extends Node {
constructor(element,next,prev) {
super(element,next);
this.prev = prev; }}class DoublyLinkedList extends LinkedList {
constructor(equalasFn = defaultEquals) {
super(equalasFn);
this.tail = undefined; }}Copy the codeinsert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new DoublyNode(element);
let current = this.head;
if (index === 0) {
if(this.head == null) { // This. Head and this.tail point directly to node
this.head = node;
this.tail = node;
} else {
node.next = this.head;
current.prev = node;
this.head = node; }}else if (index === this.count) { // Insert to the end
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} eles {
const previous = this.getElementAt(index - 1); // Find the position before the insertion point
current = previous.next;
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
this.count++;
return true;
}
return false;
}
removeAt(index) {
if (index >= 0 && index < this.count) { // Within the range
let current = this.head;
if (index === 0) {
this.head = current.next;
if (this.count === 1) {
this.tail = undefined;
} else {
this.head.prev = undefined; }}else if (index === this.count - 1) { // Remove the last element
current = this.tail;
this.tail = current.prev;
this.tail.next = undefined;
} else {
current = this.getElementAt(index);
const previous = current.prev;
previous.next = current.next;
current.next.prev = previous;
}
this.count--;
return current.element;
}
return undefined;
}
Copy the code4. Circular linked lists
Have linked form item reference + bidirectional linked list bidirectional reference
Pointer to last element to next element (tail.next) to first element (head)
Bidirectional circular lists: tail.next to head elements and head.prev to tail elements
class CircularLinkedList extends LinkedList {
constructor(equalsFN = defaultEquals) {
super(equalsFn); }}Copy the codeinsert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
let current = this.head;
if(index === 0) { // The insertion point is the first position in the list
if (this.head == null) { // The list is empty
this.head = node;
node.next = this.head;
} else {
node.next = current; // Node's next pointer points to the head
current = this.getElementAt(this.size()); // The last element
this.head = node; // Add the element as the head of the list
current.next = this.head; // The last element points to the header}}else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}
removeAt(index) {
if(index >= 0 && index < this.count) {
let current = this.head;
if(index === 0) { // Remove the first element
if(this.size() === 1) {
this.head = undefined; // There is only one element, let the header be undefined
} else {
const removed = this.head;
current = this.getElementAt(this.size()); // The last element
this.head = this.head.next; // The header element becomes the next element
current.next = this.head; // The last element, next, points to the head
current = removed; // Get the removed element, followed by return to remove the element value}}else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}
Copy the code5. Ordered lists
A list structure that keeps elements ordered
const Compare = {
LESS_THAN: -1.BIGGER_THAN: 1
};
function defaultCompare(a,b) {
if (a === b) {
return 0;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn);
this.compareFn = compareFn; }}Copy the codeinsert(element, index = 0) {
if(this.isEmpty()) {
return super.insert(element,0);
}
const pos = this.getIndexNextSortedElement(element);
return super.insert(elemenet,pos);
}
getIndexNextSortedElement(element) {
let current = this.head;
let i = 0;
for(; i < this.size() && current; i++) {
const comp = this.compareFn(element,current.element);
if(comp === Compare.LESS_THAN) {
return i;
}
current = current.next;
}
return i;
}
Copy the code6. Create StackLinkedList class
class StackLinkedList {
constructor() {
this.items = new DoublyLinkedList(); / / {1}
}
push(element) {
this.items.push(element); / / {2}
}
pop() {
if (this.isEmpty()) {
return undefined;
}
return this.items.removeAt(this.size() - 1); / / {3}}}Copy the code7. LeetCode problem
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
var reverseList = function(head) {
let p1 = head;
let p2 = null;
while(p1) {
const tmp = p1.next;
p1.next = p2; // point to the previous pointer
p2 = p1;
p1 = tmp;
}
return p2; // P1 has disappeared
};
Copy the codeGeneral idea:
Flip the node so that n+1 next points to n
Specific operation:
Create a pair of fast and slow Pointers, p1 to the head, p2 to null (slower than p1)
When p1 exists, store p1.next as TMP, p1.next points to the previous pointer, p2 and P1 move to the right until all nodes are flipped
var addTwoNumbers = function(l1, l2) {
const l3 = new ListNode(0)
let p1 = l1
let p2 = l2
let p3 = l3
let carry = 0 // store the units digit of val
while(p1 || p2) {
const v1 = p1 ? p1.val:0
const v2 = p2 ? p2.val:0
const val = v1 + v2 + carry / / add up
carry = Math.floor(val / 10) // Retrieve ten digits
p3.next = new ListNode(val % 10) // Add the units digit
//p1, P2 go right
if(p1) p1 = p1.next
if(p2) p2 = p2.next
p3 = p3.next
}
if(carry) {
p3.next = new ListNode(carry) // Put carry in
}
return l3.next
};
Copy the code
var deleteDuplicates = function(head) {
let p = head;
while(p && p.next) {
if(p.val === p.next.val){
p.next = p.next.next;
}else{ p = p.next; }}return head;
};
Copy the code
var hasCycle = function(head) {
let slow = head;
let fast = head;
while(slow && fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
return true; }}return false;
};
Copy the codeFast and slow pointer: when the fast and slow pointer meets, it indicates that there is a ring