Overview

A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node in the linked list. A doubly linked list gives each node pointers to both the next node and the previous node.

• Doubly Linked List: Each node has two pointers, one pointing to the next node and the other pointing to the previous node. This allows you to go backward and forward rather than in one direction
• Circularly Linked List: The end node points to the front node

Why?

• They can be used to implement other common abstract data types, such as lists, stacks, and queues.
• They can be preferred over arrays because elements can easily be inserted or removed without reallocation/reorganization of the entire data structure.

Pros and Cons

Advantages

• Dynamic size
• Quick insertion and deletion of nodes

Disadvantages

• Random access is not allowed. This slows down Access and Search. Each element must be iterated over starting from the first node
• Pointer takes up extra space
• Not cache friendly. In arrays, elements have contiguous locations which lends itself to a locality of reference. In linked lists, this is not the case.

Big O Analysis

Space Complexity: O(n)

Time Complexity

• Doubly linked lists have the same time and space complexity as singly linked lists

Code Implementation

Node

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

LinkedList

class LinkedList {
	constructor() {
			this.head = null;
			this.size = 0;
	}

	// functions to be implemented:
	// add(element)
	// insertAt(element,location)
	// removeFrom(location)
	// removeElement(element)

}