Linked Lists - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki
Linked Lists
How Work?
- LinkedList is the dynamic data structure, as we can add or remove elements at ease, and it can even grow as needed. Just like arrays, linked lists store elements sequentially, but don’t store the elements contiguously like an array.
Skeleton Code
// User defined class node
class Node {
// constructor
constructor(element)
{
this.element = element;
this.next = null
}
}
// linkedlist class
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
// functions to be implemented
// add(element)
// insertAt(element, location)
// removeFrom(location)
// removeElement(element)
// Helper Methods
// isEmpty
// size_Of_List
// PrintList
}
Methods
// adds an element at the end
// of list
add(element)
{
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
// insert element at the position index
// of the list
insertAt(element, index)
{
if (index > 0 && index > this.size)
return false;
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this.head;
// add the element to the
// first index
if (index == 0) {
node.next = head;
this.head = node;
} else {
curr = this.head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this.size++;
}
}
// removes an element from the
// specified location
removeFrom(index)
{
if (index > 0 && index > this.size)
return -1;
else {
var curr, prev, it = 0;
curr = this.head;
prev = curr;
// deleting first element
if (index == = 0) {
this.head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this.size--;
// return the remove element
return curr.element;
}
}
// removes a given element from the
// list
removeElement(element)
{
var current = this.head;
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element == = element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
Helper Methods
// finds the index of element
indexOf(element)
{
var count = 0;
var current = this.head;
// iterae over the list
while (current != null) {
// compare each element of the list
// with given element
if (current.element == = element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
// checks the list for empty
isEmpty()
{
return this.size == 0;
}
// gives the size of the list
size_of_list()
{
console.log(this.size);
}
// prints the list items
printList()
{
var curr = this.head;
var str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
console.log(str);
}
Example
// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
console.log(ll.isEmpty());
// adding element to the list
ll.add(10);
// prints 10
ll.printList();
// returns 1
console.log(ll.size_of_list());
// adding more elements to the list
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// returns 10 20 30 40 50
ll.printList();
// prints 50 from the list
console.log("is element removed ?" + ll.removeElement(50));
// prints 10 20 30 40
ll.printList();
// returns 3
console.log("Index of 40 " + ll.indexOf(40));
// insert 60 at second position
// ll contains 10 20 60 30 40
ll.insertAt(60, 2);
ll.printList();
// returns false
console.log("is List Empty ? " + ll.isEmpty());
// remove 3rd element from the list
console.log(ll.removeFrom(3));
// prints 10 20 60 40
ll.printList();
Full Working Example
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor() {
this.length = 0
this.head = null
}
peekHead() {
return this.head
}
get size() {
return this.length
}
add(value) {
var newNode = new Node(value)
if (!this.head) {
this.head = newNode
} else {
var currentNode = this.head
while (currentNode.next) {
currentNode = currentNode.next
}
currentNode.next = newNode
}
this.length++
return true
}
addAt(index, value) {
if (index < 0 || index >= this.size) {
return null
}
var currentNode = this.head, previousNode
var currentIndex = 0
var next = new Node(value)
if (index === 0) {
next.next = this.head
this.head = next
} else {
while (currentIndex < index) {
previousNode = currentNode
currentNode = currentNode.next
currentIndex++
}
previousNode.next = next
next.next = currentNode
currentNode = next
}
this.length++
return true
}
remove(value) {
if (this.isEmpty()) {
return null
}
if (this.head.value === value) {
this.length--
this.head = this.head.next
return true
}
var currentNode = this.head, previousNode
while (currentNode.value !== value) {
previousNode = currentNode
currentNode = currentNode.next
// no match found
if (!currentNode) {
return null
}
}
this.length--
previousNode.next = currentNode.next
return true
}
removeAt(index) {
if (index < 0 ||
this.isEmpty() ||
index >= this.size) {
return null
}
// remove from head
if (index === 0) {
var removed = this.head.value
this.head = this.head.next
this.length--
return removed
}
// remove from body / tail
var currentNode = this.head,
previousNode,
currentIndex = 0
while (currentIndex < index) {
previousNode = currentNode
currentNode = currentNode.next
currentIndex++
}
this.length--
previousNode.next = currentNode.next
return currentNode.value
/* NOTE: this method could be significantly improved
if a 'tail' were added to this structure. Think about
removing the last item in the list. We have to iterate
all the way to the end, and with long lists this can be
quite time consuming. A direct reference to the last item
could prevent this worst-case with a simple equality check.
I've left it like this for now to illustrate this point, but
feel free to try to implement this on your own! We'll add a
tail to our next structure, the doubly linked list. */
}
indexOf(value) {
var count = 0
var currentNode = this.head
if (!currentNode) return -1
while (value !== currentNode.value) {
if (currentNode.next === null) {
return -1
}
currentNode = currentNode.next
count++
}
return count
}
elementAt(index) {
if (index < 0 || index >= this.size) {
return null
}
var currentIndex = 0
var currentNode = this.head
while (currentIndex < index) {
currentNode = currentNode.next
currentIndex++
}
return currentNode.value
}
isEmpty(num) {
if (!this.head) {
return true
}
return false
}
}
// example usage:
var list = new LinkedList()
list.add('Planes')
list.add('Trains')
list.add('Automobiles')
list.add('Magic Carpets')
console.log(JSON.stringify(list.peekHead(), null, 2))
console.log(`indexOf trains: ${list.indexOf('Trains')}`)
console.log(`indexOf trucks: ${list.indexOf('Trucks')}`)
console.log(`size: ${list.size}`)