In this post I cover the basics of a Linked List, and dive into the differences between a singly, doubly and circular Linked Lists. Looking at the structure for each and problem sets.
There are four main parts when it comes to a Linked List, the head, tail, node and pointer. Each have a specific part to play within the Linked List.
This is the value at the start of the Linked List. The value of the Head can be changed by inserting a node before the current Head or deleting the value at the Head.
This is the value at the end of the Linked List. Like the Head, the Tail’s value can also be changed by inserting or deleting the last node.
This is the value that the pointer is pointing to. Let’s say for example Head has a Node value of one.
The pointer will usually point at the Head or Node and will move along between each Node.
class LinkedList {
constructor() {
this.head = this.tail = null
}
}
class Node {
constructor() {
this value = value;
this.next = next || null;
this.prev = prev || null
}
}
search(value) {
let currentNode = this.head
while(currentNode) {
if(currentNode.value === value) {
return currentNode
}
currentNode = currentNode.next
}
return null
}
addAtHead(value) {
if(!this.head) {
// if the list is empty
this.head = this.tail = new Node(value)
} else {
let oldHead = this.head
this.head = new Node(value)
oldHead.prev = this.head
this.head.next = oldHead
}
}addAtTail (value) {
if(!this.tail) {
this.head = this.tail = new Node(value)
} else {
let oldTail = this.tail
this.tail = new Node(value)
oldTail.next = this.tail
this.tail.prev = oldTail
}
}deleteHead() {
if(!this.head) {
// if list is empty/has no head
return null
} else {
let removedHead = this.head
// if list only has one node
if(this.head === this.tail) {
this.head = this.tail = null
} else {
this.head = this.head.next
this.head.prev = null
}
return removedHead.value
}
}deleteTail() {
if(!this.tail) {
return null
} else {
let removedTail = this.tail
if(this.head === this.tail) {
this.tail = this.head = null
} else {
this.tail = this.tail.prev
this.tail.next = null
}
return removedTail.value
}
}class LinkedList {
constructor() {
this.head = this.tail = null;
}
addTail(value) {
if (!this.tail) {
this.head = this.tail = new Node(value);
} else {
let oldTail = this.tail;
this.tail = new Node(value);
oldTail.next = this.tail;
this.tail.prev = oldTail;
}
}
addHead(value) {
if (!this.head) {
this.head = this.tail = new Node(value);
} else {
let oldHead = this.head;
this.head = new Node(value);
oldHead.prev = this.head;
this.head.next = oldHead;
}
}
deleteHead() {
if (!this.head) {
return null;
} else {
let removedHead = this.head;
if (this.head === this.tail) {
this.head = this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
return removedHead.value;
}
}
deleteTail() {
if (!this.tail) {
return null;
} else {
let removedTail = this.tail;
if (this.head === this.tail) {
this.tail = this.head = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
return removedTail.value;
}
}
search(value) {
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
}
class Node {
constructor(value, prev, next) {
this.value = value;
this.next = next || null;
this.prev = prev || null;
}
}
const list = new LinkedList();
list.addTail(1);
list.addHead(3);
list.search(1);
list.search(3);
list.deleteHead();
list.deleteTail();class LinkedList {
constructor() {
this.head = this.tail = null
this.length = 0;
}
}
class Node {
constructor() {
this value = value;
this.next = next || null;
this.prev = prev || null
}
}
search(value) {
let currentNode = this.head
while(currentNode) {
if(currentNode.value === value) {
return currentNode
}
currentNode = currentNode.next
}
return null
}addHead() {
this.length++
let newNode = Node(value)
if(this.head) {
this.head.prev = newNode
newNode.next - this.head
this.head = newNode
return newNode
}
this.head = this.tail = newNode
return newNode
}addAtTail (value) {
this.length++
let newNode = Node(value)
if(this.tail) {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
return newNode
}
this.head = this.tail = newNode
return newNode
}
deleteHead() {
if(this.head) {
this.length--
const removedHead = this.head
this.head = this.head.next
if(this.head) {
this.head.prev = null
} else {
this.tail = null
}
return removedHead
}
return undefined
}deleteTail() {
if(this.tail) {
this.length--
const removedTail = this.tail
this.tail = this.tail.prev
if(this.tail) {
this.tail.next = null
} else {
this.head = null
}
return removedTail
}
return undefined
}class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor(value) {
this.head = this.tail = null;
this.length = 0;
}
if(value) {
this.initialise(value)
}
}
initialise(value) {
const newNode = new Node(value)
newNode.next = newNode
this.head = newNode
this.tail = newNode
this.length++
}addHead(value) {
if(this.length === 0) {
return this.initialise(value)
}
const newNode = new Node(value)
newNode.next = this.head
this.tail.next = newNode
this.head = newNode
this.length++
}addTail(value) {
if(this.length === 0) {
return this.initialise(value)
}
const newNode = new Node(value)
newNode.next = this.head
this.tail.next = newNode
this.tail = newNode
this.length++
} traverseToIndex(index) {
if (index < 0) return undefined
// keeps track of traversal
let counter = 0
// starting point
let currentNode = this.head
// traverse to the target index
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
insert(index, value) {
if(index === 0) {
return this.addHead(value)
}
if(!index) return 'index missing'
if(typeof index !== 'number') return 'index needs to be a number'
if(index < 0) return 'index needs to be bigger than 0
if(index >= this.length) {
return this.append(value)
}
const newNode = newNode(value, null)
const prevIndex = this.traverseToIndex(index-1)
const targetIndex = prevIndex.next
prevIndex.next = newNode
newNode.next = targetIndex
this.length++
return this
}deleteHead() {
if(this.length === 0) return 'list is empty'
const currHead = this.head
if(this.length === 1) {
const headVal = this.head.value
this.head = null
this.tail = null
this.length--
return headVal
}
const headVal = this.head.value
const newHead = this.head.next
this.head = newHead
this.tail.next = this.head
this.length--
return headVal
}deleteTail() {
if(this.length === 0) return 'list empty'
if(this.length === 1) {
const headVal = this.head.value
this.head = null
this.tail = null
this.length--
return headVal
}
const tailVal = this.tail.value
const newTail = this.traverseToIndex(this.length - 2)
newTail.next = this.head
this.tail.next = newTail
this.length--
return tailVal
}delete(index) {
if (!index) return 'index missing'
if (typeof index !== number) return 'index should be a number'
if (index < 0) return 'index should be bigger than 0'
if (this.length === 2) {
if (index === 0) {
return this.deleteHead()
}
if (index > 0) {
reutrn this.deleteTail()
}
}
let removalType
if (index === 0) {
removalType = 'head'
} else if (index >= this.length) {
removalType = 'tail'
} else {
removalType = 'middle'
}
if (removalType === 'head') return this.deleteHead()
if (removalType === 'tail') return this.deleteTail()
if (removalType === 'middle') {
const prevIndex = this.traverseToIndex(index - 1)
const targetIndex = prevIndex.next
const targetVal = targetIndex.value
prevIndex.next = targetIndex.next
this.length--
return targetVal
}
}Cost of accessing elements: O(n)
Insert/remove from beginning: O(1)
Insert/remove from end: O(n)
Insert/remove from middle: O(n)
[algoexpert]
You are given the head of a singly Linked List whose nodes are in osrted order. Write a function that returns a modified version of the Linked List that doesn’t contain any nodes with duplicate values. The Linked List should be modified in place (you don’t need to create a new list) and the modified Linked List should still have it’s nodes sorted.
1 -> 3 -> 3 -> 4 -> 6 -> 6 -> 81 -> 3 -> 4 -> 6 -> 8// This is an input class. Do not edit.
class LinkedList {
constructor(value) {
this.value = value;
this.next = null;
}
}
function removeDuplicatesFromLinkedList(linkedList) {
// Write your code here.
return null;
}function removeDuplicatesFromLinkedList(linkedList) {
let node = linkedList;
while (node.next) {
if (node.value === node.next.value) {
node.next = node.next.next;
} else {
node = node.next;
}
}
return linkedList;
}[algoexpert]
You are given two Linked Lists of potentially unequal length. These Linked Lists potentially merge at a shared intersection node. Write a function that returns the intersection node or returns None/null if there isn’t an intersection.
linkedListOne: 2 -> 3 -> 1 -> 4
linked ListTwo: 5 -> 4 -> 1 -> 41 -> 4// This is an input class. Do not edit.
class LinkedList {
constructor(value) {
this.value = value;
this.next = null;
}
}
function mergingLinkedLists(linkedListOne, linkedListTwo) {
// Write your code here.
return null;
}function mergingLinkedLists(linkedListOne, linkedListTwo) {
let currNodeOne = linkedListOne;
let currNodeTwo = linkedListTwo;
while (currNodeOne !== currNodeTwo) {
if (currNodeOne === null) {
currNodeOne = linkedListTwo;
} else {
currNodeOne = currNodeOne.next;
}
if (currNodeTwo === null) {
currNodeTwo = linkedListOne;
} else {
currNodeTwo = currNodeTwo.next;
}
}
return currNodeOne;
}[leetcode 430]
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.
Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.
head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12][1,2,3,7,8,11,12,9,10,4,5,6]1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]To merge…
[1, 2, 3, 4, 5, 6, null]
|
[null, null, 7, 8, 9, 10, null]
|
[ null, 11, 12, null][1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]/**
* // Definition for a Node.
* function Node(val,prev,next,child) {
* this.val = val;
* this.prev = prev;
* this.next = next;
* this.child = child;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var flatten = function (head) {};function flatten(head) {
let newHead = head;
while (newHead) {
if (head.child) {
let curr = newHead.next;
newHead.next = flatten(newHead.child);
newHead.next.prev = newHead;
newHead.child = null;
while (newHead.next !== null) {
newHead = newHead.next;
}
newHead.next = curr;
if (curr) {
curr.prev = newHead;
}
newHead = newHead.next;
}
return head;
}
}The code you see here is pulled from different sources but do the same thing in different ways