A linked list stores an ordered set of elements, but unlike an array, 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. The following figure explains:
One of the advantages of linked lists over traditional arrays is that you don't need to move other elements when you add or remove elements. However, the list needs to use pointers, so we need to pay attention to the implementation of the list. Another detail of an array is that you can directly access any location element. To access an element in the middle of a linked list, you need to deliver the list from the starting point (header) until you find the required element
One way linked list implementation code:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title></title>
<script>
function LinkedList(){
//The Node class represents the item to be added to the list
var Node=function(element){
this.element=element; //Value to add to linked list
this.next=null; //Value pointing to the next node in the list
}
var length=0; //Number of linked list items
var head=null; //Store references for the first node
//Append elements to the end of the list
this.append=function(element){
var node=new Node(element); //Create a Node entry
var current;
if(head===null){ //If the head element is null, it means adding the first element to the linked list
head=node;
}
else{
current=head;
while(current.next){ //Start iterating from the beginning of the list. When current.next is null, it has reached the end of the list
current=current.next;
}
current.next=node; //Add the newly created node to the end of the list
}
length++;
}
//Remove fixed position elements from the list
this.removeAt=function(position){
if(position>=0 && position<=length){ //Verify location is valid
var index=0;
var previous;
var current=head; //Create the first element reference of the linked list with the current variable
if(position===0){
head=current.next;//To remove the first element, point the head to the second element
}
else{
while(index++ < position){ //Iterate to the destination node
previous=current;
current=current.next;
}
previous.next=current.next; //Link previous to the next item of current: skip current to remove it
}
length--;
return current.element;
}
else{
return null;
}
}
//Insert an element anywhere
this.insert = function (position, element) {
if (position >= 0 && position <= length) {//Check for out of line
var node = new Node(element); //Create a node
var index = 0;
var previous;
var current = head;
if (position === 0) {//Add in first place
node.next = current;
head = node;
}
else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;//Update linked list length
return true;
}
else {
return false;//false if out of range
}
};
//Convert Linkedlist object to string
this.toString=function(){
var current=head;
var string='';
while(current){ //Check if element exists
string+=','+current.element;
current=current.next;
}
return string.slice(1);
}
//Index found for element
this.indexOf=function(element){
var current=head;
var index=0;
while(current){ //Check if element exists
if(element===current.element){
return index;
}
index++;
current=current.next;
}
return -1;
}
//After the indexOf method is implemented, the element removeAt() can be removed according to the value of the element
this.remove=function(element){
var index=this.indexOf(element);
return this.removeAt(index);
}
this.isEmpty=function(){
return length===0;
}
this.size=function(){
return length;
}
this.getHead=function(){
return head;
}
}
var arr=new LinkedList();
arr.append(1)
arr.append(2)
arr.append(3)
console.log(arr.toString()+'----------length: '+arr.size());
arr.removeAt(2)
console.log(arr.toString()+'----------length: '+arr.size());
arr.insert(2,10)
console.log(arr.toString()+'----------length: '+arr.size());
console.log(arr.indexOf(10));
arr.remove(10);
console.log(arr.toString()+'----------length: '+arr.size())
console.log(arr.isEmpty());
console.log(arr.size());
console.log(arr.getHead());
</script>
</head>
<body>
</body>
</html>
Operation result:
