JavaScript data structure and algorithm -- linked list

A linked list stores an ordered set of elements, but unlike an array, each element in a linked list that is not placed consecutively in memory consists of a node storing the element itself and a reference to the next element. The following figure shows the structure of a linked list:

Linked list is a very common data structure. It does not need to initialize the capacity and can add or subtract elements at will;
When you add or delete elements, you only need to change the address of the pointer field of the two element nodes before and after, so you can add and delete them quickly;

Because it contains a lot of pointer fields, it takes up a lot of space;
It is very time-consuming to search elements by traversing the linked list.

Applicable scenarios:
Scenarios with small amount of data and frequent increase and deletion

``````function LinkedList() {
// Create a node class to represent the item to be added element represents the value to be added, and next points to the next node item in the list
let Node = function(element) {
this.element = element;
this.next = null;
}
let length = 0;
// Here is how to declare the linked list
// 1. Add a new item to the end of the list
this.append = function(element) {
let node = new Node(element);
current;
// The list is empty and the first element is added
// List is not empty, append to it
} else {

// Loop through the list until the last item is found
while(current.next) {
current = current.next;
}
// Find the last item, assign its next as node, and establish a link
current.next = node;
}
// Update list length
length++;
}
// 2. Remove elements from the list
this.removeAt = function(position) {
// Check whether the position is out of the range of linked list
if(position > -1 && position < length) {
previous,
index = 0;
// Remove first element
if(position === 0 ) {
} else {
// Loop to the specified location to find previous and current
while(index++ < position) {
previous = current;
current = current.next;
}
// Link previous to the next item in current: skip current
previous.next = current.next;
}
// Chain length minus one
length--;
// Return deleted items
return current.element;
} else {
// Not a valid location, return null
return null
}
}
// 3. Insert elements anywhere
this.insert = function(element, position) {
//Judge whether it is beyond the range of linked list
if (position >= 0 && position<= length) {
let node = new Node(element),
previous,
index = 0;
// Insert element first
if (position === 0 ) {
node.next = current;
} else{
// x loops to the location where the position should be added, taking previous and current
while(index++ < position) {
previous = current;
current = current.next;
}
// Insert between previous and current
node.next = current;
previous.next = node;
};
length++;
return true;
} else{
return false;
};
}
//4. Convert LinkedList object to string
this.toString = function() {
string = '';
while(current) {
string += current.element + (current.next ? 'n' : '');
current = current.next;
}
return string;
}
//5. Whether there is a value in the list
this.indexOf = function(element) {
index = 0;
while(current) {
if(element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
//6. Implement remove element through element
this.remove = function(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
this.isEmpty = function() {
return length === 0;
}
this.size = function() {
return length;
}
}
}``````

Tags: Javascript

Posted on Mon, 02 Dec 2019 04:52:15 -0800 by PnHoPob