Doubly Linked Lists - rohit120582sharma/Documentation GitHub Wiki

Doubly Linked Lists are almost identical to Singly Linked Lists except there is an additional pointer to previous nodes

Better than Singly Linked Lists for finding nodes and can be done in half the time!

However, they do take up more memory considering the extra pointer

Doubly linked lists are used to implement other data structures and certain types of caches

• Insertion - O(1)
• Removal - O(1)
• Searching - O(N)
• Access - O(N)

• Adding a node to the end of the Doubly Linked List
• Pseudocode
  • Create a new node with the value passed to the function
  • If the head property is null set the head and tail to be the newly created node
  • If not, set the previous property on the newly created node to be the tail
  • Set the next property on the tail to be that node
  • Set the tail to be the newly created node
  • Increment the length
  • Return the Doubly Linked List

class Node {
	constructor(value){
		this.value = value;
		this.prev = null;
		this.next = null;
	}
}
class DoublyLinkedList {
	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{
			newNode.prev = this.tail;
			this.tail.next = newNode;
			this.tail = newNode;
		}
		this.length++;
		return this;
	}
}

• Removing a node from the end of the Doubly Linked List
• Pseudocode
  • If there is no head, return undefined
  • Store the current tail in a variable to return later
  • If the length is 1, set the head and tail to be null
  • Update the tail to be the previous Node.
  • Set the newTail's next to null
  • Decrement the length
  • Return the value removed

pop(){
	if(!this.head){
		return undefined;
	}
	var oldTail = this.tail;
	if(this.length === 1){
		this.head = null;
		this.tail = null;
	}else{
		this.tail = oldTail.prev;
		this.tail.next = null;
		oldTail.prev = null;
	}
	this.length--;
	return oldTail;
}

• Removing a node from the beginning of the Doubly Linked List
• Pseudocode
  • If length is 0, return undefined
  • Store the current head property in a variable (we'll call it old head)
  • If the length is 1, set the head and tail to be null
  • Update the head to be the next of the old head
  • Set the head's prev property to null
  • Set the old head's next to null
  • Decrement the length
  • Return old head

shift(){
	if(!this.head){
		return undefined;
	}
	var oldHead = this.head;
	if(this.length === 1){
		this.head = null;
		this.tail = null;
	}else{
		this.head = oldHead.next;
		this.head.prev = null;
		oldHead.next = null;
	}
	this.length--;
	return oldHead;
}

• Adding a node to the beginning of the Doubly Linked List
• Pseudocode
  • Create a new node with the value passed to the function
  • If the length is 0, set the head and tail to be the new node
  • Otherwise, set the next property on the new node to be the head property
  • Set the prev property on the head of the list to be the new node
  • Update the head to be the new node
  • Increment the length
  • Return the list

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

• Accessing a node in a Doubly Linked List by its position
• Pseudocode
  • If the index is less than 0 or greater or equal to the length, return null
  • If the index is less than or equal to half the length of the list
    • Loop through the list starting from the head and loop towards the middle
    • Return the node once it is found
  • If the index is greater than half the length of the list
    • Loop through the list starting from the tail and loop towards the middle
    • Return the node once it is found

get(index){
	if(index < 0 || index >= this.length){
		return null;
	}
	var counter, current;
	if(index <= this.length / 2){
		counter = 0;
		current = this.head;
		while(counter != index){
			current = current.next;
			counter++;
		}
	}else{
		counter = this.length - 1;
		current = this.tail;
		while(counter != index){
			current = current.prev;
			counter--;
		}
	}
	return current;
}

• Replacing the value of a node to the in a Doubly Linked List
• Pseudocode
  • Create a variable which is the result of the get method at the index passed to the function
  • If the get method returns a valid node, set the value of that node to be the value passed to the function
  • Return true
  • Otherwise, return false

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

• Adding a node in a Doubly Linked List by a certain position
• Pseudocode
  • If the index is less than zero or greater than or equal to the length return false
  • If the index is 0, unshift
  • If the index is the same as the length, push
  • Use the get method to access the index -1
  • Set the next and prev properties on the correct nodes to link everything together
  • 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 beforeNode = this.get(index - 1);
	var afterNode = beforeNode.next;
	beforeNode.next = newNode;
	newNode.prev = beforeNode;
	newNode.next = afterNode;
	afterNode.prev = newNode;

	this.length++;
	return true;
}

• Removing a node in a Doubly Linked List by a certain position
• Pseudocode
  • If the index is less than zero or greater than or equal to the length return undefined
  • If the index is 0, shift
  • If the index is the same as the length-1, pop
  • Use the get method to retrieve the item to be removed
  • Update the next and prev properties to remove the found node from the list
  • Set next and prev to null on the found node
  • Decrement the length
  • Return the removed node.

remove(index){
	if(index < 0 || index >= this.length){
		return undefined;
	}
	if(index === 0){
		this.shift();
		return true;
	}
	if(index === this.length - 1){
		this.pop();
		return true;
	}
	var foundNode = this.get(index);
	var beforeNode = foundNode.prev;
	var afterNode = foundNode.next;
	foundNode.next = null;
	foundNode.prev = null;
	beforeNode.next = afterNode;
	afterNode.prev = beforeNode;
	this.length--;
	return foundNode;
}

• Reversing a Doubly Linked List in place!
• Pseudocode
  • Create a variable called current and set it to be the head of the list
  • Create a variable called tail and set it to be the head of the list
  • Loop through the list and set the next property of the current node to be the prev property of the current node
  • If there is no next property, set the tail to be the head and the head to be the current variable
  • Return the list