Singly Linked Lists - rohit120582sharma/Documentation GitHub Wiki

A data structure that contains a head, tail and length property.

Linked Lists consist of nodes, and each node has a value and a pointer to another node or null.

Singly Linked Lists are an excellent alternative to arrays when insertion and deletion at the beginning are frequently required

Arrays contain a built in index whereas Linked Lists do not

The idea of a list data structure that consists of nodes is the foundation for other data structures like Stacks and Queues

• Lists
  • Do not have indexes!
  • Connected via nodes with a next pointer
  • Random access is not allowed
• Arrays
  • Indexed in order!
  • Insertion and deletion can be expensive
  • Can quickly be accessed at a specific index

• Insertion - O(1)
• Removal - It depends.... O(1) or O(N)
• Searching - O(N)
• Access - O(N)

• Adding a new node to the end of the Linked List!
• Pseudocode
  • This function should accept a value
  • Create a new node using the value passed to the function
  • If there is no head property on the list, set the head and tail to be the newly created node
  • Otherwise set the next property on the tail to be the new node and set the tail property on the list to be the newly created node
  • Increment the length by one
  • Return the linked list

class Node {
	constructor(value){
		this.value = value;
		this.next = null;
	}
}
class SinglyLinkedList {
	constructor(){
		this.head = null;
		this.tail = null;
		this.length = 0;
	}
	push(value){
		var newNode = new Node(value);
		if(!this.head){
			this.head = newNode;
			this.tail = newNode;
		}else{
			this.tail.next = newNode;
			this.tail = newNode;
		}
		this.length++;
		return this;
	}
}

• Removing a node from the end of the Linked List!
• Pseudocode
  • If there are no nodes in the list, return undefined
  • Loop through the list until you reach the tail
  • Set the next property of the 2nd to last node to be null
  • Set the tail to be the 2nd to last node
  • Decrement the length of the list by 1
  • Return the value of the node removed

pop(){
	if(!this.head){
		return undefined;
	}
	var current = this.head;
	var newTail = this.head;
	while(current.next){
		newTail = current;
		current = current.next;
	}
	this.tail = newTail;
	this.tail.next = null;
	this.length--;
	if(this.length === 0){
		this.head = null;
		this.tail = null;
	}
	return current;
}

• Removing a new node from the beginning of the Linked List!
• Pseudocode
  • If there are no nodes, return undefined
  • Store the current head property in a variable
  • Set the head property to be the current head's next property
  • Decrement the length by 1
  • Return the value of the node removed

shift(){
	if(!this.head){
		return undefined;
	}
	var currentHead = this.head;
	this.head = currentHead.next;
	this.length--;
	if(this.length === 0){
		this.head = null;
		this.tail = null;
	}
	return currentHead;
}

• Adding a new node to the beginning of the Linked List!
• Pseudocode
  • This function should accept a value
  • Create a new node using the value passed to the function
  • If there is no head property on the list, set the head and tail to be the newly created node
  • Otherwise set the newly created node's next property to be the current head property on the list
  • Set the head property on the list to be that newly created node
  • Increment the length of the list by 1
  • Return the linked list

unshift(value){
	var newNode = new Node(value);
	if(!this.head){
		this.head = newNode;
		this.tail = newNode;
	}else{
		newNode.next = this.head;
		this.head = newNode;
	}
	this.length++;
	return this;
}

• Retrieving a node by it's position in the Linked List!
• Pseudocode
  • This function should accept an index
  • If the index is less than zero or greater than or equal to the length of the list, return null
  • Loop through the list until you reach the index and return the node at that specific index

get(index){
	if(index < 0 || index >= this.length){
		return null;
	}
	var counter = 0;
	var current = this.head;
	while(counter != index){
		current = current.next;
		counter++;
	}
	return current;
}

• Changing the value of a node based on it's position in the Linked List
• Pseudocode
  • This function should accept a value and an index
  • Use your get function to find the specific node
  • If the node is not found, return false
  • If the node is found, set the value of that node to be the value passed to the function and return true

set(index, value){
	var foundNode = this.get(index);
	if(foundNode){
		foundNode.value = value;
		return true;
	}
	return false;
}

• Adding a node to the Linked List at a specific position
• Pseudocode
  • If the index is less than zero or greater than the length, return false
  • If the index is the same as the length, push a new node to the end of the list
  • If the index is 0, unshift a new node to the start of the list
  • Otherwise, using the get method, access the node at the index - 1
  • Set the next property on that node to be the new node
  • Set the next property on the new node to be the previous next
  • Increment the length
  • Return true

insert(index, value){
	if(index < 0 || index > this.length){
		return false;
	}
	if(index === 0){
		this.unshift(value);
		return true;
	}
	if(index === this.length){
		this.push(value);
		return true;
	}
	var newNode = new Node(value);
	var prevNode = this.get(index-1);
	newNode.next = prevNode.next;
	prevNode.next = newNode;
	this.length++;
	return true;
}

• Removing a node from the Linked List at a specific position
• Pseudocode
  • If the index is less than zero or greater than the length, return undefined
  • If the index is the same as the length - 1, pop
  • If the index is 0, shift
  • Otherwise, using the get method, access the node at the index - 1
  • Set the next property on that node to be the next of the next node
  • Decrement the length
  • Return the value of the node removed

remove(index){
	if(index < 0 || index >= this.length){
		return undefined;
	}
	if(index === 0){
		return this.shift();
	}
	if(index === this.length - 1){
		return this.pop();
	}
	var prevNode = this.get(index-1);
	var nextNode = prevNode.next;
	prevNode.next = nextNode.next;
	this.length--;
	return nextNode;
}

• Reversing the Linked List in place!
• Pseudocode
  • Swap the head and tail
  • Create a variable called next
  • Create a variable called prev
  • Create a variable called node and initialise it to the head property
  • Loop through the list
  • Set next to be the next property on whatever node is
  • Set the next property on the node to be whatever prev is
  • Set prev to be the value of the node variable
  • Set the node variable to be the value of the next variable
  • Once you have finished looping, return the list

reverse(){
	if(!this.head){
		return undefined;
	}
	var next;
	var prev = null;
	let node = this.head;

	this.head = this.tail;
	this.tail = node;
	
	for(let i = 0; i < this.length; i++){
		next = node.next;
		node.next = prev;
		prev = node;
		node = next;
	}
	return this;
}