When we are developing software, we have to store data in memory. However, many types of data structures, such as arrays, maps, sets, lists, trees, graphs, etc., and choosing the right one for the task can be tricky. This series of posts will help you know the trade-offs so that you can use the right tool for the job!
This section will focus on linear data structures: Arrays, Lists, Sets, Stacks, and Queues.
You can find all these implementations and more in the Github repo: //github.com/amejiarosario/dsa.js
This post is part of a tutorial series:
Learning Data Structures and Algorithms [DSA] for Beginners
Intro to algorithms time complexity and Big O notation
Eight time complexities that every programmer should know
Data Structures for Beginners: Arrays, HashMaps, and Lists you are here
Graph Data Structures for Beginners
Trees Data Structures for Beginners
Self-balanced Binary Search Trees
Appendix I: Analysis of Recursive Algorithms
Data Structures Big-O Cheatsheet
The following table is a summary of everything that we are going to cover.
Bookmark it, pin it, or share it, so you have it at hand when you need it.
Click on the name to go to the section or click on the runtime to go to the implementation
* = Amortized runtime
| Array | O[n] | O[1] | O[n] | O[n] | Insertion to the end is O[1]. Details here. |
| HashMap | O[1] | O[1] | O[1] | O[1] | Rehashing might affect insertion time. Details here. |
| Map [using Binary Search Tree] | O[log[n]] | - | O[log[n]] | O[log[n]] | Implemented using Binary Search Tree |
| Set [using HashMap] | O[1] | - | O[1] | O[1] | Set using a HashMap implementation. Details here. |
| Set [using list] | O[n] | - | O[n] | O[n] | Implemented using Binary Search Tree |
| Set [using Binary Search Tree] | O[log[n]] | - | O[log[n]] | O[log[n]] | Implemented using Binary Search Tree |
| Linked List [singly] | O[n] | - | O[n] | O[n] | Adding/Removing to the start of the list is O[1]. Details here. |
| Linked List [doubly] | O[n] | - | O[n] | O[n] | Adding/Deleting from the beginning/end is O[1]. But, deleting/adding from the middle is O[n]. Details here |
| Stack [array implementation] | O[1] | - | - | O[1] | Insert/delete is last-in, first-out [LIFO] |
| Queue [naïve array impl.] | O[1] | - | - | O[n] | Remove [Array.shift] is O[n] |
| Queue [array implementation] | O[1] | - | - | O[1] | Worst time insert is O[n]. However amortized is O[1] |
| Queue [list implementation] | O[1] | - | - | O[1] | Using Doubly Linked List with reference to the last element. |
Note: Binary search trees and trees, in general, will be cover in the next post. Also, graph data structures.
Primitive Data Types
Primitive data types are the most basic elements, where all the other data structures are built upon. Some primitives are:
- Integers. E.g., 1, 2, 3,
- Characters. E.g., a, b, "1", "*"
- Booleans. E.g., true or false.
- Float [floating points] or doubles. E.g., 3.14159, 1483e-2.
- Null values. E.g. null
JavaScript specific primitives:
- undefined
- Symbol
- Number
Note: Objects are not primitive since they are composed of zero or more primitives and other objects.
Array
Arrays are collections of zero or more elements. Arrays are one of the most used data structures because of their simplicity and fast way of retrieving information.
You can think of an array as a drawer where you can store things in the bins.
Array is like a drawer that stores things on bins
When you want to search for something, you can go directly to the bin number. Thats a constant time operation [O[1]]. However, if you forgot what cabinet had, you will have to open one by one [O[n]] to verify its content until you find what you are looking for. That same happens with an array.
Depending on the programming language, arrays have some differences. For some dynamic languages like JavaScript and Ruby, an array can contain different data types: numbers, strings, words, objects, and even functions. In typed languages like Java/C/C++, you have to predefine the Array size and the data type. In JavaScript, it would automatically increase the size of the Array when needed.
Arrays built-in operations
Depending on the programming language, the implementation would be slightly different.
For instance, in JavaScript, we can accomplish append to end with push and append to the beginning with unshift. But also, we have pop and shift to remove from an array. Lets describe some everyday operations that we are going to use through this post.
Common JS Array built-in functions
| array.push | O[1] | Insert element to the end of the array |
| array.pop | O[1] | Remove element to the end of the array |
| array.shift | O[n] | Remove element to the beginning of the array |
| array.unshift | O[n] | Insert element[s] to the beginning of the array |
| array.slice | O[n] | Returns a copy of the array from beginning to end. |
| array.splice | O[n] | Changes [add/remove] the array |
Insert element on an array
There are multiple ways to insert elements into an array. You can append new data to the end or add it to the beginning of the collection.
Lets start with append to tail:
| 1 2 3 4 5 6 7 | function insertToTail[array, element] { array.push[element]; return array; } const array = [1, 2, 3]; console.log[insertToTail[array, 4]]; // => [ 1, 2, 3, 4 ] |
Based on the language specification, push just set the new value at the end of the Array. Thus,
The Array.push runtime is a O[1]
Lets now try appending to head:
| 1 2 3 4 5 6 7 | function insertToHead[array, element] { array.unshift[element]; return array; } const array = [1, 2, 3]; console.log[insertToHead[array, 0]]; // => [ 0, 1, 2, 3 ] |
What do you think is the runtime of the insertToHead function? It looks the same as the previous one, except that we are using unshift instead of push. But theres a catch! unshift algorithm makes room for the new element by moving all existing ones to the next position in the Array. So, it will iterate through all the elements.
The Array.unshift runtime is an O[n]
Access an element in an array
If you know the index for the element that you are looking for, then you can access the element directly like this:
| 1 2 3 4 5 6 7 | function access[array, index] { return array[index]; } const array = [1, 'word', 3.14, {a: 1}]; access[array, 0]; // => 1 access[array, 3]; // => {a: 1} |
As you can see in the code above, accessing an element on an array has a constant time:
Array access runtime is O[1]
Note: You can also change any value at a given index in constant time.
Search an element in an array
Suppose you dont know the index of the data that you want from an array. You have to iterate through each element on the Array until we find what we are looking for.
| 1 2 3 4 5 6 7 8 9 10 11 | function search[array, element] { for [let index = 0; index < array.length; index++] { if[element === array[index]] { return index; } } } const array = [1, 'word', 3.14, {a: 1}]; console.log[search[array, 'word']]; // => 1 console.log[search[array, 3.14]]; // => 2 |
Given the for-loop, we have:
Array search runtime is O[n]
Deleting elements from an array
What do you think is the running time of deleting an element from an array?
Well, lets think about the different cases:
- You can delete from the end of the Array, which might be constant time. O[1]
- However, you can also remove it from the beginning or middle of the collection. In that case, you would have to move all the following elements to close the gap. O[n]
Talk is cheap. Lets do the code!
| 1 2 3 4 5 6 7 8 | function remove[array, element] { const index = search[array, element]; array.splice[index, 1]; return array; } const array1 = [0, 1, 2, 3]; console.log[remove[array1, 1]]; // => [ 0, 2, 3 ] |
So we are using our search function to find the elements index O[n]. Then we use the JS built-in splice function, which has a running time of O[n]. Whats the total O[2n]? Remember, we constants dont matter as much.
We take the worst-case scenario:
Deleting an item from an array is O[n].
Array operations time complexity
We can sum up the arrays time complexity as follows:
Array Time Complexities
| Access [Array.[]] | O[1] |
| Insert head [Array.unshift] | O[n] |
| Insert tail [Array.push] | O[1] |
| Search [for value] | O[n] |
| Delete [Array.splice] | O[n] |
HashMaps
Maps, dictionaries, and associative arrays all describe the same abstract data type. But hash map implementations are distinct from treemap implementations in that one uses a hash table and one uses a binary search tree.
Hashtable is a data structure that maps keys to values
Going back to the drawer analogy, bins have a label rather than a number.
HashMap is like a drawer that stores things on bins and labels them
In this example, if you are looking for the book, you dont have to open bin 1, 2, and 3. You go directly to the container labeled as books. Thats a huge gain! Search time goes from O[n] to O[1].
In arrays, the data is referenced using a numeric index [relatively to the position]. However, HashMaps uses labels that could be a string, number, Object, or anything. Internally, the HashMap uses an Array, and it maps the labels to array indexes using a hash function.
There are at least two ways to implement hashmap:
- Array: Using a hash function to map a key to the array index value. Worst: O[n], Average: O[1]
- Binary Search Tree: using a self-balancing binary search tree to look up for values [more on this later]. Worst: O[log n], Average: O[log n].
We will cover Trees & Binary Search Trees, so dont worry about it for now. The most common implementation of Maps is using an array and hash function. So, thats the one we are going to focus on.
HashMap implemented with an array
As you can see in the image, each key gets translated into a hash code. Since the array size is limited [e.g., 10], we have to loop through the available buckets using the modulus function. In the buckets, we store the key/value pair, and if theres more than one, we use a collection to hold them.
Now, What do you think about covering each of the HashMap components in detail? Lets start with the hash function.
HashMap vs. Array
Why go through the trouble of converting the key into an index and not using an array directly, you might ask. The main difference is that Arrays index doesnt have any relationship with the data. You have to know where your data is.
Lets say you want to count how many times words are used in a text. How would you implement that?
- You can use two arrays [lets call it A and B]. One for storing the word and another for storing how many times they have seen [frequency].
- You can use a HashMap. They key is the word, and the value is the words frequency.
What is the runtime of approach #1 using two arrays? If we say, the number of words in the text is n. Then we have to search if the word in the array A and then increment the value on array B matching that index. For every word on n, we have to test if its already on array A. This double loop leave use with a runtime of O[n2].
What is the runtime of approach #2 using a HashMap? We iterate through each word on the text once and increment the value if there is something there or set it to 1 if that word is seen for the first time. The runtime would be O[n], which is much more performant than approach #1.
Differences between HashMap and Array
- Search on an array is O[n] while on a HashMap is O[1]
- Arrays can have duplicate values, while HashMap cannot have duplicated keys [but they can have identical values.]
- The Array has a key [index] that is always a number from 0 to max value, while in a HashMap, you have control of the key, and it can be whatever you want: number, string, or symbol.
Hash Function
The first step to implement a HashMap is to have a hash function. This function will map every key to its value.
The perfect hash function is the one that for every key, it assigns a unique index.
Ideal hashing algorithms allow constant time access/lookup. However, its hard to achieve a perfect hashing function in practice. You might have the case where two different keys yields on the same index, causing a collision.
Collisions in HashMaps are unavoidable when using an array-like underlying data structure. At some point, data that cant fit in a HashMap will reuse data slots. One way to deal with collisions is to store multiple values in the same bucket using a linked list or another array [more on this later]. When we try to access the keys value and found various values, we iterate over the values O[n]. However, in most implementations, the hash adjusts the size dynamically to avoid too many collisions. We can say that the amortized lookup time is O[1]. We are going to explain what we mean by amortized runtime later in this post with an example.
Naïve HashMap implementation
A simple [and bad] hash function would be this one:
Naive HashMap Implementationfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class NaiveHashMap { constructor[initialCapacity = 2] { this.buckets = new Array[initialCapacity]; } set[key, value] { const index = this.getIndex[key]; this.buckets[index] = value; } get[key] { const index = this.getIndex[key]; return this.buckets[index]; } hash[key] { return key.toString[].length; } getIndex[key] { const indexHash = this.hash[key]; const index = indexHash % this.buckets.length; return index; } } |
We are using buckets rather than drawer/bins, but you get the idea :]
We have an initial capacity of 2 [two buckets]. But, we want to store any number of elements on them. We use modulus % to loop through the number of available buckets.
Take a look at our hash function in line 18. We are going to talk about it in a bit. First, lets use our new HashMap!
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | // Usage: const assert = require['assert']; const hashMap = new NaiveHashMap[]; hashMap.set['cat', 2]; hashMap.set['rat', 7]; hashMap.set['dog', 1]; hashMap.set['art', 8]; console.log[hashMap.buckets]; /* bucket #0: , bucket #1: 8 */ assert.equal[hashMap.get['art'], 8]; // this one is ok assert.equal[hashMap.get['cat'], 8]; // got overwritten by art assert.equal[hashMap.get['rat'], 8]; // got overwritten by art assert.equal[hashMap.get['dog'], 8]; // got overwritten by art |
This Map allows us to set a key and a value and then get the value using a key. The key part is the hash function. Lets see multiple implementations to see how it affects the Maps performance.
Can you tell whats wrong with NaiveHashMap before expanding the answer below?
What is wrong with `NaiveHashMap` is that...
1] Hash function generates many duplicates. E.g.
| 1 2 | hash['cat'] // 3 hash['dog'] // 3 |
This hash implementation will cause a lot of collisions.
2] Collisions are not handled at all. Both cat and dog will overwrite each other on position 3 of the Array [bucket#1].
3] Size of the Array even if we get a better hash function, we will get duplicates because the Array has a size of 3, which less than the number of elements that we want to fit. We want to have an initial capacity that is well beyond what we need to fit.
Did you guess any? ️
Improving Hash Function
The primary purpose of a HashMap is to reduce the search/access time of an Array from O[n] to O[1].
For that, we need:
- A proper hash function that produces as few collisions as possible.
- An array big enough to hold all the required values.
Lets give it another shot at our hash function. Instead of using the strings length, lets sum each character ascii code.
| 1 2 3 4 5 6 7 8 9 10 11 | hash[key] { let hashValue = 0; const stringKey = key.toString[]; for [let index = 0; index < stringKey.length; index++] { const charCode = stringKey.charCodeAt[index]; hashValue += charCode; } return hashValue; } |
Lets try again:
| 1 2 | hash['cat'] // 312 [c=99 + a=97 + t=116] hash['dog'] // 314 [d=100 + o=111 + g=103] |
This one is better! Because words with the same length have different codes.
Howeeeeeeeeever, theres still an issue! Because rat and art are both 327, collision!
We can fix that by offsetting the sum with the position:
| 1 2 3 4 5 6 7 8 9 10 11 | hash[key] { let hashValue = 0; const stringKey = `${key}`; for [let index = 0; index < stringKey.length; index++] { const charCode = stringKey.charCodeAt[index]; hashValue += charCode 1 } |
Note: We will use the Map rather than the regular Object, since the Maps key could be anything while on Objects key can only be string or number. Also, Maps keeps the order of insertion.
Behind the scenes, the Map.set just insert elements into an array [take a look at DecentHashMap.set]. So, similar to Array.push we have that:
Insert an element in HashMap runtime is O[1]. If rehash is needed, then it will take O[n]
Our implementation with rehash functionality will keep collisions to the minimum. The rehash operation takes O[n], but it doesnt happen all the time, only when it is needed.
Search/Access an element on a HashMap runtime
This is the HashMap.get function that we use to get the value associated with a key. Lets evaluate the implementation from DecentHashMap.get]:
| 1 2 3 4 5 6 7 8 9 10 | get[key] { const hashIndex = this.getIndex[key]; const values = this.array[hashIndex]; for [let index = 0; index < values.length; index++] { const entry = values[index]; if[entry.key === key] { return entry.value } } } |
If theres no collision, then values will only have one value, and the access time would be O[1]. But, we know there will be collisions. If the initial capacity is too small and the hash function is terrible like NaiveHashMap.hash, then most of the elements will end up in a few buckets O[n].
HashMap access operation has a runtime of O[1] on average and worst-case of O[n].
Advanced Note: Another idea to reduce the time to get elements from O[n] to O[log n] is to use a binary search tree instead of an array. Actually, Javas HashMap implementation switches from an array to a tree when a bucket has more than 8 elements.
Edit/Delete element on a HashMap runtime
Editing [HashMap.set] and deleting [HashMap.delete] key/value pairs have an amortized runtime of O[1]. In the case of many collisions, we could face an O[n] as a worst-case. However, with our rehash operation, we can mitigate that risk.
HashMap edits and delete operations has a runtime of O[1] on average and worst-case of O[n].
HashMap operations time complexity
We can sum up the arrays time complexity as follows:
HashMap Time Complexities
| Access/Search [HashMap.get] | O[n] | O[1] | O[n] is an extreme case when there are too many collisions |
| Insert/Edit [HashMap.set] | O[n] | O[1] | O[n] only happens with rehash when the Hash is 0.75 full |
| Delete [HashMap.delete] | O[n] | O[1] | O[n] is an extreme case when there are too many collisions |
Sets
Sets are very similar to arrays. The difference is that they dont allow duplicates.
How can we implement a Set [Array without duplicates]? We could use an array and check if an element is there before inserting a new one. But the running time of checking if a value is already there is O[n]. Can we do better than that? We develop the Map with an amortized run time of O[1]!
Set Implementation
We could use the JavaScript built-in Set. However, if we implement it by ourselves, its more logical to deduct the runtimes. We are going to use the optimized HashMap with rehash functionality.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | const HashMap = require['../hash-maps/hash-map']; class MySet { constructor[] { this.hashMap = new HashMap[]; } add[value] { this.hashMap.set[value]; } has[value] { return this.hashMap.has[value]; } get size[] { return this.hashMap.size; } delete[value] { return this.hashMap.delete[value]; } entries[] { return this.hashMap.keys.reduce[[acc, key] => { if[key !== undefined] { acc.push[key.content]; } return acc }, []]; } } |
We used HashMap.set to add the set elements without duplicates. We use the key as the value, and since the hash maps keys are unique, we are all set.
Checking if an element is already there can be done using the hashMap.has, which has an amortized runtime of O[1]. Most operations would be an amortized constant time except for getting the entries, O[n].
Note: The JS built-in Set.has has a runtime of O[n] since it uses a regular list of elements and checks each one at a time. You can see the Set.has algorithm here
Here some examples how to use it:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | const assert = require['assert']; // const set = new Set[]; // Using the built-in const set = new MySet[]; // Using our own implementation set.add['one']; set.add['uno']; set.add['one']; // should NOT add this one twice assert.equal[set.has['one'], true]; assert.equal[set.has['dos'], false]; assert.equal[set.size, 2]; // assert.deepEqual[Array.from[set], ['one', 'uno']]; assert.equal[set.delete['one'], true]; assert.equal[set.delete['one'], false]; assert.equal[set.has['one'], false]; assert.equal[set.size, 1]; |
You should be able to use MySet and the built-in Set interchangeably for these examples.
Set Operations runtime
From our Set implementation using a HashMap, we can sum up the time complexity as follows [very similar to the HashMap]:
Set Time Complexities
| Access/Search [Set.has] | O[n] | O[1] | O[n] is an extreme case when there are too many collisions |
| Insert/Edit [Set.add] | O[n] | O[1] | O[n] only happens with rehash when the Hash is 0.75 full |
| Delete [Set.delete] | O[n] | O[1] | O[n] is an extreme case when there are too many collisions |
Linked Lists
A linked list is a data structure where every element is connected to the next one.
The linked list is the first data structure that we are going to implement without using an array. Instead, we will use a node that holds a value and points to the next element.
node.js| 1 2 3 4 5 6 | class Node { constructor[value] { this.value = value; this.next = null; } } |
When we have a chain of nodes where each one points to the next one, we a Singly Linked list.
Singly Linked Lists
For a singly linked list, we only have to worry about every element referencing the next one.
We start by constructing the root or head element.
linked-list.js| 1 2 3 4 5 6 7 8 | class LinkedList { constructor[] { this.root = null; // first/head/root element this.size = 0; // total number of elements in the list } // ... } |
There are four basic operations that we can do in every Linked List:
- addLast: appends an element to the end of the list [tail]
- removeLast: deletes element to the end of the list
- addFirst: Adds an element to the beginning of the list [head]
- removeFirst: Removes an element from the start of the list [head/root]
Adding/Removing an element at the end of a linked list
There are two primary cases:
- If the list first [root/head] doesnt have any element yet, we make this node the head of the list.
- Contrary, if the list already has items, then we have to iterate until finding the last one and appending our new node to the end.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | addLast[value] { // similar Array.push const node = new Node[value]; if[this.root] { let currentNode = this.root; while[currentNode && currentNode.next] { currentNode = currentNode.next; } currentNode.next = node; } else { this.root = node; } } |
Whats the runtime of this code? If it is the first element, then adding to the root is O[1]. However, finding the last item is O[n].
Now, removing an element from the end of the list has a similar code. We have to find the current before last and make its next reference null.
LinkedList.prototype.removeLast| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | removeLast[] { let current = this.root; let target; if[current && current.next] { while[current && current.next && current.next.next] { current = current.next; } target = current.next; current.next = null; } else { this.root = null; target = current; } if[target] { return target.value; } } |
The runtime again is O[n] because we have to iterate until the second-last element and remove the reference to the last [line 10].
Adding/Removing an element from the beginning of a linked list
Adding an element to the head of the list is like this:
LinkedList.addFirst| 1 2 3 4 5 6 7 8 9 10 | /** * Adds an element to the beginning of the list. Similar to Array.unshift * Runtime: O[1] * @param {any} value */ addFirst[value] { const node = new Node[value]; node.next = this.root; this.root = node; } |
Adding and removing elements from the beginning is a constant time because we hold a reference to the first element:
LinkedList.removeFirst| 1 2 3 4 5 6 7 8 9 10 11 12 | /** * Removes element from the start of the list [head/root]. It's Similar `Array.shift` * Runtime: O[1] */ removeFirst[] { const first = this.root; if [first] { this.root = first.next; return first.value; } } |
As expected, the runtime for removing/adding to the first element from a linked List is always constant O[1]
Removing an element anywhere from a linked list
Removing an element anywhere in the list leverage the removeLast and removeFirst. However, if the removal is in the middle, then we assign the previous node to the next one. That removes any reference from the current node, this is removed from the list:
LinkedList.remove| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | remove[index = 0] { if[index === 0] { return this.removeFirst[]; } for [let current = this.first, i = 0; current; i++, current = current.next] { if[i === index] { if[!current.next] { // if it doesn't have next it means that it is the last return this.removeLast[]; } current.previous.next = current.next; this.size--; return current.value; } } } |
Note that index is a zero-based index: 0 will be the first element, 1 second, and so on.
Removing an element anywhere within the list is O[n].
Searching for an element in a linked list
Searching an element on the linked list is very somewhat similar to remove:
LinkedList.contains| 1 2 3 4 5 6 7 | contains[value] { for [let current = this.first, index = 0; current; index++, current = current.next] { if[current.value === value] { return index; } } } |
This function finds the first element with the given value.
The runtime for searching an element in a linked list is O[n]
Singly Linked Lists time complexity
Singly Linked List time complexity per function is as follows.
| addFirst | O[1] | Insert element to the beginning of the list |
| addLast | O[n] | Insert element to the end of the list |
| add | O[n] | Insert element anywhere in the list. |
| removeFirst | O[1] | Remove element to the beginning of the list |
| removeLast | O[n] | Remove element to the end of the list |
| remove | O[n] | Remove any element from the list |
| contains | O[n] | Search for an element from the list |
Notice that every time we add/remove from the last position, the operation takes O[n].
But we could reduce the addLast/removeLast from O[n] to a flat O[1] if we keep a reference of the last element!
We are going to add the last reference in the next section!
Doubly Linked Lists
When we have a chain of nodes where each one points to the next one, we have a Singly Linked list. When we have a linked list where each node leads to the next and the previous element, we have a Doubly Linked List
Doubly linked list nodes have double references [next and previous]. We are also going to keep track of the list first and the last element.
Doubly Linked Listfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Node { constructor[value] { this.value = value; this.next = null; this.previous = null; } } class LinkedList { constructor[] { this.first = null; // head/root element this.last = null; // last element of the list this.size = 0; // total number of elements in the list } // ... } |
Adding and Removing from the start of a list
Adding and removing from the start of the list is simple since we have this.first reference:
LinkedList.prototype.addFirstfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | addFirst[value] { const node = new Node[value]; node.next = this.first; if[this.first] { this.first.previous = node; } else { this.last = node; } this.first = node; // update head this.size++; return node; } |
Notice that we have to be very careful and update the previous and last reference.
LinkedList.prototype.removeFirstfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | removeFirst[] { const first = this.first; if[first] { this.first = first.next; if[this.first] { this.first.previous = null; } this.size--; return first.value; } else { this.last = null; } } |
Whats the runtime?
Adding and removing elements from a [singly/doubly] LinkedList has a constant runtime O[1]
Adding and removing from the end of a list
Adding and removing from the end of the list is a little tricky. If you checked in the Singly Linked List, both operations took O[n] since we had to loop through the list to find the last element. Now, we have the last reference:
LinkedList.prototype.addLastfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | addLast[value] { const node = new Node[value]; if[this.first] { let currentNode = this.first; node.previous = this.last; this.last.next = node; this.last = node; } else { this.first = node; this.last = node; } this.size++; return node; } |
Again, we have to be careful about updating the references and handling exceptional cases such as only one element.
LinkedList.prototype.removeLastfull code| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | removeLast[] { let current = this.first; let target; if[current && current.next] { current = this.last.previous; this.last = current; target = current.next; current.next = null; } else { this.first = null; this.last = null; target = current; } if[target] { this.size--; return target.value; } } |
Using a doubly-linked list, we no longer have to iterate through the whole list to get the 2nd last element. We can use directly this.last.previous and is O[1].
Did you remember that for the Queue, we had to use two arrays? We can now change that implementation and use a doubly-linked list instead. The runtime will be O[1] for insert at the start and deleting at the end.
Adding an element anywhere from a linked list
Adding an element on anywhere on the list leverages our addFirst and addLast functions as you can see below:
LinkedList.addFullCode| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | add[value, index = 0] { if[index === 0] { return this.addFirst[value]; } for [let current = this.first, i = 0; i Chủ Đề |