## DEV Community

Swarup Das

Posted on • Updated on • Originally published at dev.to

# Data Structures & Algorithms in JavaScript(Single Linked List) Part 1

Hello Everyone, this is part 5.1 in the series of blogs about data structures and algorithms in JavaScript, In this blog, I will cover linked list.

A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. - geeksforgeeks.org ## List Of Operations Available

• Push: Insert an element at the end of the linked list.
• Insert: Insert an element at the given index of the linked list.
• Remove: Remove the end element of the linked list.
• RemoveAt: Remove the element at the given index of the linked list.
• GetElementAt: Get the element at the given index of the linked list.
• IndexOf: Return the index of the element in the linked list.

## Implementation of linked list in Javascript

Let us define the ES6 class Node, with two properties data and next,
data property will hold, the data which we will insert in the linked list and next property will hold, the pointer to the next Node. A Linked List is just a chain of Node linked to each other by next pointer. What's a pointer? A pointer points to the next member of the list, as you see in the above image.

`````` class Node {
constructor(element){
this.element = element;
this.next = null;
}
}

``````

Now, Let's define the ES6 class linked list with three properties,

``````class LinkedList {
constructor(func) {
this.count = 0;
this.equalFunc = func || defaultEq;
}
}

``````

### Push

When adding an element at the end of the linked list, there can be two scenarios:

• When the linked list is not empty we need to append at the end.

First, we create a Node passing element as its value if the head is undefined then assign head to the node ({1}) else ,we will define a current variable equal to head and loop until we reach the end of the linked list i.e when node's next is null ({2}) and assign the end Node's next to the node ({3}), after adding an element will always increment the count variable ({4}).

``````
push(element) {
const node = new Node(element);
}else{
while (current.next != null) { //2
current = current.next
}
current.next = node; //3
}
this.count++ //4;
return;
}

``````

### GetElementAt

To get an element by its index we will first define a variable node, referring to head ({1}), we valid the index's out of bound error, by check is the index, greater than zero and less than count. ({2}); if not then return undefined ({5}), Now, iterate over the linked list starting from 0 to the index and ({3}), return the node ({4}). This method will be very useful in insert and remove an element from any position in the linked list.

``````
getElementAt(index) {
let node = this.head; // 1
if (index >= 0 && index < this.count) { //2
for (let i = 0; i < index; i++) { //3
node = node.next;
}
return node; //4
}
return undefined; //5
}

``````

### Insert

Insert an element at a given the position; the index must be greater than zero and less than and equal to count, there are two scenarios,
we will first define a variable node which refers to the head.

• index is equal to zero ({1})
• check if the head is undefined or not
• if undefined than head equal to the node
• else change the head node to the new node and node's next to the previous head. • index is greater than zero ({2})
• adding an element in the middle or at the end of the list. First, need to loop through the list until we reach the desired position. In this case, we will loop to index -1, meaning one position before where we desire to insert a new node
• When we get out of the loop, the previous variable will be reference to an element before the index where we would like to insert to new element, and the current variable .
• So , first we link the node's next to current and then change the link between previous and current. we need previous.next to the node.
``````insert(element, postion) {
if (postion >= 0 && postion <= this.count) {
const node = new Node(element);
if (postion == 0) { //1
}
node.next = current;
} else {
let previous = this.getElementAt(postion - 1);
current = previous.next;
node.next = current;
previous.next = node;
}
this.count++;
}
}

``````

you get the full source here

### Conclusion :

Methods Complexity
insert at any position O(n)
GetElementAt O(n)

So, stay tuned for the next blog, in which I will cover remaining methods of Linked List. de0xyrib0se

Your complexity for insert at any position is incorrect as it does not take into account the additional getElementAt. That being said you can get rid of that func call by simply using a trailing "pointer". Swarup Das

Yes, you can get rid of the function and simply use a trailing pointer, But loop until the desired index is common in linked list methods, so instead of rewriting the same code, again and again, I have extract into a function. And the complexity of the find the desired position in the linked list is O(n) once you know it required constant time to insert.
So to insert at any position, first you have the position, I.e 0(n) and insert the element I.e O(1),
To compute O-notation we will ignore the lower order terms since the lower order terms are relatively insignificant for large input. That's why the complexity is O(n). de0xyrib0se • Edited

Your insert calls this.getElementAt to get the previous, that is not O(1).

That trailing pointer can make the difference between serving a response and not serving anything in a production setting ;) Every cycle counts, even on 32 cores and 128GB of RAM...