Linked Lists 1. Introduction 2. What Is a Linked List? 3. Why Linked Lists? 3.1. Linked Lists vs. Arrays 3.1.1. Linked Lists vs. Hash Tables 4. What Is a Pointer? 5. Create a Singly Linked List 5.1. Append & Prepend 5.2. Node Class 5.3. Insert 6. Doubly Linked List 6.1. Singly vs. Doubly Linked Lists 7. Reverse 8. Linked List Review
1. Introduction• What problems do we face with arrays? – With static arrays, we only have certain amount of amount of data/memory that can be allocated next to each other in memory.– Both static and dynamic arrays can increase their memory once it hits a certain limit and double up that memory in another location. This doubling up process has a performance implication and it costs us O(n). – Arrays also have bad performance for any sorts of operation like INSERT or DELETE that have to shift indexes over. • What problems do we face with hash tables? – With hash tables, we can store things pretty much wherever we wanted in memory and hash tables would take care of it and know where to place it in memory.– But, hash tables are NOT ordered.2. What Is a Linked List?• Linked list is a set of lists are linked!• You can think of linked lists as a set of nodes where each nodes contains two main information:– The data values– A pointer to the next node in the linked list.• The first node is called the head and the last node is called the tail.• Linked lists are null-terminated, where null signifies the end of the list, i.e. the tail always points to the null.• You can have linked lists both sorted or unsorted.• JavaScript doesn't come with linked list built-in, Java has it built-in.• Check out visualgo website to get a visual understanding of linked lists (and other data structures).3. Why Linked Lists?3.1. Linked Lists vs. Arrays• Linked lists have a sort of loose structure that allows you to insert a value in the middle of the list by simply reseting a few pointers. This is the same of deleting a node.– Remember in arrays, once we insert an element, we had to shift all the next indexes down by 1.• However, contrary to arrays where the elements are indexed, in linked list if you want to get to an element, you have to traverse the list until you get that element. This is an O(n) operation.– Usually, for lookup in linked lists, we use while loop because we don't know how long we have to traverse.• Iterating over items in arrays are faster than linked list, although they're both O(n).– Most computers have caching systems that makes reading from sequential memory faster than scattered addresses. Arrays items are always located next to each other in memory and linked list items are scattered all over the memory. •
prependO(1)
appendO(1)
lookupO(n)
insertO(n)
deleteO(n)
Table 1:Big-O of Operations for Linked List
• • Insert and delete in arrays are also O(n). How's linked list better?– We will answer this question in the next following sections.• 3.1.1. Linked Lists vs. Hash Tables• One advantage of linked lists over hash tables is that there's some sort of order in linked lists.– Each node points to the next node, so you can have ordered data unlike hash tables. 4. What Is a Pointer?• A pointer is a reference to another place in memory (or another object or another node).• A simple way to show a pointer in JS is like this:
const obj1 = { a:true };const obj2 = obj1;
 • In the example above, obj2 is only pointing to obj1. So, it's not like in memory we have stored { a:true } twice. If we change obj1, obj2 will change accordingly. They both point to the same location in memory.– Note: If we delete obj1, the computer won't delete { a:true } because obj2 is still pointing to it.* Now, if we set obj2 = 'hello', the automatic garbage collection in JS will now delete { a:true } because nothing is pointing to it anymore.* There are low level languages where you have to manage the memory and manually delete this kind of unreferenced values.5. Create a Singly Linked List5.1. Append & Prepend• Let's say we want to create a linked list of 10 → 5 → 16.• Languages like JS or Python don't have linked list but we can simply create one. Below is an example of creating so in JS.• Here, we add methods for append and prepend.
// create a linked list, add append & prepend methods 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; }} let myLinkedList = new LinkedList(10);console.log(myLinkedList.append(5));console.log(myLinkedList.append(16));console.log(myLinkedList.prepend(1))
 5.2. Node Class• To make the code above cleaner and also observe the DIY (Do It Yourself), we can create a node class.
class Node { constructor(value) { this.value = value; this.next = null; }} // to create a new nodeconst newNode = new Node(value);
 5.3. Insert• We're going to add an insert method that takes a value and index.
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 } 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); } if (index === 0) { this.prepend(value); return this.printList(); } 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(); }} let myLinkedList = new LinkedList(10);myLinkedList.append(5);myLinkedList.append(16);myLinkedList.prepend(1);myLinkedList.insert(2, 99);myLinkedList.insert(20, 88);myLinkedList.remove(2);
 6. Doubly Linked List• Doubly linked list is similar to singly linked list except that it links to the node before it. It has two pointers per node.• Doubly linked list allows us to traverse our list backwards.
class DoublyLinkedList { constructor(value) { this.head = { value: value, next: null, prev: null }; this.tail = this.head; this.length = 1; } append(value) { const newNode = { value: value, next: null, prev: null } console.log(newNode) newNode.prev = this.tail this.tail.next = newNode; this.tail = newNode; this.length++; return this; } prepend(value) { const newNode = { value: value, next: null, prev: null } newNode.next = this.head; this.head.prev = newNode 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) { return this.append(value); } const newNode = { value: value, next: null, prev: null } const leader = this.traverseToIndex(index-1); const follower = leader.next; leader.next = newNode; newNode.prev = leader; newNode.next = follower; follower.prev = newNode; this.length++; console.log(this) return this.printList(); } traverseToIndex(index) { //Check parameters let counter = 0; let currentNode = this.head; while(counter !== index){ currentNode = currentNode.next; counter++; } return currentNode; }} let myLinkedList = new DoublyLinkedList(10);myLinkedList.append(5)myLinkedList.append(16)myLinkedList.prepend(1)myLinkedList.insert(2, 99)
 6.1. Singly vs. Doubly Linked Lists• When should we use one vs. the other?– The advantage of singly linked list is that it has a fairly simple implementation. It requires lesser memory and it's a little bit faster.– The downside of singly linked list is that it cannot be iterated in reverse.– Singly list is mainly used when:* There's shortage in memory (or memory is expensive).* Or our main goal is fast insertion and deletion and you don't have that much searching (especially when you have insertion at the beginning of the list).– The advantage of doubly linked list is that it can traversed both from the front or from the back.– Also, with doubly it's easier to delete the previous node (instead traversing all the way from the head).– The downside of doubly list is that it's a bit more complex to implement and it requires more memory.– Doubly lists are good when you don't have that much limitation on memory and you want good operation for searching for elements.• Note: Most of the times in interviews, you're going to see singly linked list. 7. Reverse• One of the most popular interview questions is to revere a linked list, i.e. given a linked list, how would you reverse it?
// add this method to the class defined before 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();}
 8. Linked List Review• Linked list doesn't come pre-built in a lot of languages.• Linked lists are low level data structures and is mostly used in other data structures (such as hash tables, stacks, queues).
ProsCons
Fast InsertionSlow Lookup
Fast DeletionMore Memory
Ordered
Flexible Size
Table 2:Linked List Pros and Cons
• Linked lists have applications in many places like implementing file systems on your computer, or even browser history.• Watch this video for a nice comparison between arrays and linked lists.