Not long ago, I have started to practice data structures problems. Below I want to share what has helped me studying linked list problems.
Linked List
A linked list is a sequence of elements where each node points to the next one. First element of the list is called the ‘Head’ and all other elements are called the ‘Tail’. Note the last element on a list points to ‘Null’.
A linked list is a dynamic data structure that can allocate and deallocate memory at runtime, as opposed to eg. String. In most languages Strings are allocated once on creation and from now on their size doesn’t change. List can grow when new elements are added and that might require memory allocation.
First task: Insertion
Construct the node (element) with properties data and next (next.data is a pointer to another instance of Node).
function Node(value) {
this.value = value;
this.next = null;
} //Construct the LinkedList with property head and size. function singlyLinkedList() {
this.head = null;
this.size = 0;
}
How to insert into a singly linked list?
Consider those two scenarios: inserting at the end (if the list is empty, we are adding the first element, or if the list is not empty, we are appending elements to it) and inserting at the head.
//Insertion at the head.singlyLinkedList.prototype.insert = function(val) { if (this.head === null) {
this.head = new Node(val)
} else {
var temp = this.head //old heap
this.head = new Node(val) //new head
this.head.next = temp //new node's head points to the temp
}
this.size ++
}
If the head of the linked list is empty, the head is set to the new node. Otherwise, the old heap is saved in temp, and the new head becomes the newly added node. Finally, the new head’s next points to the temp (the old head).
//Insertion at the end
singlyLinkedList.prototype.push = function (val) {
let currentHead;
if (this.head == null) {
this.head = new Node(val);
} else{
currentHead = this.head;
while (currentHead.next != null) {
currentHead = currentHead.next;
}
//assign next to new element to make the link
currentHead.next = new Node(val);
}
this.size++;
}Second task: Deletion by value
Consider cases for position of deleted: at the head, in the middle and at the end.
singlyLinkedList.prototype.remove = function(val) { var currentHead = this.head
//deletion at the head
if(currentHead.data === value){
this.head = currentHead.next
}else{
var prev = currentHead; //deletion in the middle while(currentHead.next){ if(currentHead.data === value){
prev.next = currentHead.next
prev = currentHead.next;
break;
}
prev = currentHead;
currentHead = currentHead.next;
}
//deletion at the end if (currentHead.data == value) {
prev.next = null;
}
}
}
Third task: Reverse Linked List
// Time Complexity O(n); Space Complexity O(1)
//iterate through each node and set next property of the first node to prev (null)
// 1 -> 2 -> 3 -> 4 -> null
// expected result: 4 -> 3 -> 2 -> 1 -> null const reverseList = function(head) {
let reversedList = head
let prev = null while (reversedList) {
let oldList = reversedList.next
reversedList.next = prev
prev = reversedList if(!oldList){
break
} reversedList = oldList
} return reversedList
}
Fourth task: implement indexOf method
The indexOf method receives the value of a node and returns the position of this node if found. In each iteration, we will verify whether the value we are looking for, is in the current node. We are searching for primitive types using strict equality comparison. If the element is a complex type, a customized function to compare elements should be implemented.
singlyLinkedList.prototype.indexOf = function(nodeValue){
let currentHead = this.head;
for(let i = 0; i < this.size && currentHead!=null; i++){
if(nodeValue === currentHead.value){
return i
}
currentHead = currentHead.next
}
return -1
}
