vs Arrays
If you’re like me, you’re probably familiar with arrays or lists, ordered data structures where memory allocation is contiguous. For example if you have the following array:
numbers = [1, 2, 3, 4, 5]And we use street addresses for pseudo code to demonstrate, the memory location addresses for this array may be:
123 Main Street
124 Main Street
125 Main Street
126 Main Street
127 Main StreetWhereas a linked list is a collection of data that is linked together with references, or pointers. This means the location where the data is stored in memory can be in a non-contiguous manner.
For example if we take the array from above and turned it into a (singly) linked list, each element or node would have a reference to the next element/node.
1 --> 2 One points to Two's memory address, 124 Main Street
2 --> 3 Two points to Three's memory address, 541 12th Avenue
3 --> 4 Three points to Four's memory address, 2 Water Place
4 --> 5 etc.Therefore element 1 doesn’t know anything about element 3, and only through element 2.
For a better visual:
But that’s not all when it comes to the differences between arrays and linked lists! Let’s say we remove element 3 from the original array above. What happens to the remaining elements in the array? Remember an array is ordered by an index, starting from 0 and in our case element 3 is at index 2. Naturally the amended array looks like this:
numbers
// => [1, 2, 4, 5]
// index: 0, 1, 2, 3It looks as if only one change was done — 3 was removed, but in fact several things have changed.
- Index two changed from the number 3 to 4
- Index three changed from 4 to 5
- The data stored in the array’s memory addresses have changed
Now this may not seem very significant at all, but take this scenario: in programming languages like Java, you must define the length or size of an array upon creation.
If you want to make it any longer or add an additional element, then you must copy the entire array and create another array with its data plus the additional element.
In large applications this may use a lot of memory and could take time which may be costly to UX, and we all know this could cost you users!
Linked Lists
What do we know now?
- We know a linked list is made up of elements located in different places in memory where each element points to the next element in the list.
- It can be costly to adjust an array, more than it appears
Terminology
- Head — refers to the first element of the list
- Tail — refers to the last element of the list
- Node — refers to an element of the list
- Singly — a linked list where each node only points to only one other node
- Doubly — a linked list where each node points to the node behind it and to the node after it
Altogether
The Benefits
Remember the several changes that are made when you remove an element from an array? And recall how in statically typed languages, like Java, you must define the data type of a variable and its properties? So if you defined an array with only 5 elements but wanted a 6th later on, you would have to make a clone of the current array and make a new array with it with the extra slot.
When it comes to time complexities, adding and removing from a linked list is generally constant time — it will take the same amount of time to do a task regardless of the input size.
With that said, it can be advantageous to use linked lists over arrays when it comes to space as well. If you have to copy arrays all the time, it would use loads of memory after all.
The Challenges
Since a node in a singly linked list knows only about the next node, and a doubly linked list knows only about the node previous to it and the node after it, you can’t access a specific node in constant time. Even if you knew that the node was 3rd in the list, you would have to start with the head and continue until you reached the 3rd node.
In code, it may look something like this:
headNode.next.next// or for a more dynamic wayfunction getNnode(headNode, n){
currentNode = headNode
count = 0
node while(currentNode) {
if(count === n) {
return node
} count++
currentNode = currentNode.next
}
}getNnode(headNode, 3)
As you can see, it would always take N iterations in order to retrieve the node you are looking for. And that’s if you even know where it was in the linked list.
An array is contiguous and so each element’s location in memory is next to one another. But with a linked list they can be located anywhere in memory as long as they are referencing the next node. With that said, each and every node has at least one pointer to another node right? This of course takes up extra memory. In a large application this may or may not be an issue.
TL;DR
- Linked lists are made up of nodes which point to another node creating a list
- Arrays can be costly with adding and removing elements, whereas a linked list can add and remove a node in constant time
- It is better to randomly access an array than a linked list since you don’t have to traverse through a list to get to an element/node
- Linked lists really shine when implemented in a queue or stack formation since you are only adding and removing from the head or tail
- Particularly with static programming languages, arrays can be costly as you are forced to copy and create a new array in memory every time you want to extend the length or size of an array
Queue
Based on this tutorial, I was initially introduced to linked lists via a queue. I tweaked it to include some edge cases:
class Node { constructor(value) {
this.value = value // customer's name
this.next = null
}
}
class Queue { constructor(queueName) {
this.name = queueName // deliLine, supermarketLine, etc.
this.front = null
this.back = null
} enqueue(value) { const node = new Node(value)
console.log(`${node.value} has joined the line.`); if(!this.front) {
this.front = this.back = node; } else {
this.back.next = node
this.back = node
} return this.print()
} dequeue() {
const firstInQueue = this.front
console.log(`Now servicing ${firstInQueue.value}.`); if(!this.front) {
this.back = null
} if(firstInQueue) {
this.front = this.front.next
} this.print()
return firstInQueue
} print() {
let inQueue = this.front;
if(!inQueue) { return console.log(`The ${this.name} line is empty.`) }
const queueArr = []; while(inQueue) {
queueArr.push(inQueue.value); if(this.front === this.back) {
break } else {
inQueue = inQueue.next
}
} let output = `The ${this.name}'s line is now: ` if(queueArr.length === 2) {
output += `${queueArr[0]} and ${queueArr[1]}.` } else if(queueArr.length > 2) {
for(let i=0; i<queueArr.length; i++) { if(i === 0) {
return output += `${queueArr[i]} ` } else {
return output += `, ${queueArr[i]}`
}
} } else {
output += `${queueArr[0]}.`
} return output
}
}
Doubly Linked List
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}class LinkedList {
constructor(name) {
this.name = name;
this.head = null;
this.tail = null;
} addToHead(nodeValue) {
const oldHead = this.head;
const node = new Node(nodeValue); if (oldHead) {
// make the new head to the new node
this.head = node; // point the new head's next to the old head
this.head.next = oldHead;
// point the old head's prev to the new head
this.head.next.prev = node; } else {
// when there's only one node in the list
this.head = this.tail = node;
};
}; addToTail(nodeValue) {
const node = new Node(nodeValue);
const oldTail = this.tail; if(!this.head && !this.tail) {
this.head = this.tail = node;
}; if(oldTail) {
// make tail the new node
this.tail = node; // make the new tail's prev point to the old tail node
this.tail.prev = oldTail; // make the old tail's next point to the new node
this.tail.prev.next = node;
return this.tail;
};
}; addWhereN(nodeValue, n) {
let currentNode = this.head;
const node = new Node(nodeValue); for(let i=1; i < n; i++) {
if(!currentNode) return console.log(`addWhereN: There aren't that many nodes in this list yet...`); currentNode = currentNode.next;
}; // change prev node's next to the new node
currentNode.prev.next = node; // update new node's pointers to the current's
node.prev = currentNode.prev;
node.next = currentNode;
currentNode = node; // change next node's prev to new node
currentNode.next.prev = node; return currentNode;
}; removeHead() {
if(this.head) {
this.head = this.head.next ? this.head.next : null;
this.head.prev = null;
return this.head; } else {
console.log(`There is no head node.`);
};
}; removeTail() {
if(this.tail) {
this.tail.prev.next = null;
this.tail = this.tail.prev ? this.tail.prev : null;
return this.tail; } else {
console.log(`There is no tail node.`);
}
} removeWhereN(n) {
let currentNode = this.head; for (let i = 1; i < n; i++) {
if (!currentNode) return console.log(`removeWhereN: There aren't that many nodes in this list yet...`); currentNode = currentNode.next;
}; currentNode.prev.next = currentNode.next; currentNode.next.prev = currentNode.prev; return currentNode;
} print() {
const list = [];
let currentNode = this.head; while (currentNode) {
list.push(currentNode.value);
currentNode = currentNode.next;
}; return list;
};
};
