8. Linked List - marinakosova/master-the-coding-interview GitHub Wiki
A linked list is a linear data structure similar to an array.
Unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.
Each element (commonly called nodes) contains two items: the data stored and a link to the next node. The data can be any valid data type.
The entry point to a linked list is called the head. The head is a reference to the first node in the linked list. The last node on the list points to null. If a list is empty, the head is a null reference.
There are two types of linked list: singly linked list and doubly linked list.
Each node in a singly-linked list contains not only the value but also a reference field to link to the next node.
By this way, the singly-linked list organizes all the nodes in a sequence.
Nodes can easily be removed or added from a linked list without reorganizing the entire data structure. This is one advantage it has over arrays.
- Search operations are slow in linked lists. Unlike arrays, random access of data elements is not allowed. Nodes are accessed sequentially starting from the first node.
- It uses more memory than arrays because of the storage of the pointers.
Unlike the array, we are not able to access a random element in a singly-linked list in constant time. If we want to get the ith element, we have to traverse from the head node one by one. It takes us O(N) time on average to visit an element by index, where N is the length of the linked list.
- adding nodes
- removing nodes
- finding a node
- traversing (or traveling through) the linked list
Unlike an array, we don’t need to move all elements past the inserted element. Therefore, you can insert a new node into a linked list in O(1) time complexity, which is very efficient.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
setNextNode(node) {
if (!(node instanceof Node)) {
throw new Error('Next node must be a member of the Node class');
}
this.next = node;
}
getNextNode() {
return this.next;
}
}
// LinkedList implimentation
class LinkedList {
constructor() {
this.head = null;
}
addToHead(data) {
const newHead = new Node(data);
const currentHead = this.head;
this.head = newHead;
if (currentHead) {
this.head.setNextNode(currentHead);
}
}
addToTail(data) {
let tail = this.head;
if (!tail) {
this.head = new Node(data);
} else {
while (tail.getNextNode() !== null) {
tail = tail.getNextNode();
}
tail.setNextNode(new Node(data));
}
}
removeHead() {
const removedHead = this.head;
if (!removedHead) {
return;
}
this.head = removedHead.getNextNode();
return removedHead.data;
}
printList() {
let currentNode = this.head;
let output = '<head> ';
while (currentNode !== null) {
output += currentNode.data + ' ';
currentNode = currentNode.getNextNode();
}
output += '<tail>';
console.log(output);
}
}
const seasons = new LinkedList();
seasons.addToHead('summer');
seasons.addToHead('spring');
seasons.addToTail('fall');
seasons.addToTail('winter');
seasons.removeHead();
console.log(seasons.printList());Swapping Elements in a Linked List,
Swap nodes in a linked list without swapping data (Very Easy Explanantion)
const testList = new LinkedList();
for (let i = 0; i <= 10; i++) {
testList.addToTail(i);
}
testList.printList();
swapNodes(testList, 2, 5);
testList.printList();
function swapNodes(list, data1, data2) {
console.log(`Swapping ${data1} and ${data2}:`);
let node1Prev = null;
let node2Prev = null;
let node1 = list.head;
let node2 = list.head;
if (data1 === data2) {
console.log('Elements are the same - no swap to be made');
return;
}
while (node1 !== null) {
if (node1.data === data1) {
break;
}
node1Prev = node1;
node1 = node1.getNextNode();
}
while (node2 !== null) {
if (node2.data === data2) {
break;
}
node2Prev = node2;
node2 = node2.getNextNode();
}
if (node1 === null || node2 === null) {
console.log('Swap not possible - one or more element is not in the list');
return;
}
if (node1Prev === null) {
list.head = node2;
} else {
node1Prev.setNextNode(node2);
}
if (node2Prev === null) {
list.head = node1;
} else {
node2Prev.setNextNode(node1);
}
let temp = node1.getNextNode();
node1.setNextNode(node2.getNextNode());
node2.setNextNode(temp);
}The worst case for time complexity in swapNodes() is if both while loops must iterate all the way through to the end (either if there are no matching nodes, or if the matching node is the tail). This means that it has a linear big O runtime of O(n), since each while loop has a O(n) runtime, and constants are dropped.
There are four new variables created in the function regardless of the input, which means that it has a constant space complexity of O(1).
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = {
value: value,
next: null
}
console.log(newNode)
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = {
value: value,
next: null
}
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
printList() {
const array = [];
let currentNode = this.head;
while(currentNode !== null){
array.push(currentNode.value)
currentNode = currentNode.next
}
return array;
}
insert(index, value){
//Check for proper parameters;
if(index >= this.length) {
console.log('yes')
return this.append(value);
}
const newNode = {
value: value,
next: null
}
const leader = this.traverseToIndex(index-1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.next = holdingPointer;
this.length++;
return this.printList();
}
traverseToIndex(index) {
//Check parameters
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove(index) {
// Check Parameters
const leader = this.traverseToIndex(index-1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
this.length--;
return this.printList();
}
reverse() {
if (!this.head.next) {
return this.head;
}
let first = this.head;
this.tail = this.head;
let second = first.next;
while(second) {
const temp = second.next;
second.next = first;
first = second;
second = temp;
}
this.head.next = null;
this.head = first;
return this.printList();
}
}
let myLinkedList = new LinkedList(10);
myLinkedList.append(5)
myLinkedList.append(16)
myLinkedList.prepend(1)
myLinkedList.printList()
myLinkedList.insert(2, 99)
myLinkedList.insert(20, 88)
myLinkedList.printList()
myLinkedList.remove(2)
myLinkedList.reverse()