In this module, you'll dive deep into object references, linked lists, and classes. These concepts are fundamental to understanding data structures and object-oriented programming in JavaScript.
This video explores how objects are stored and referenced in JavaScript, which is fundamental to understanding more complex data structures.
// Primitive types are copied by value
let a = 5;
let b = a;
a = 10;
console.log(a); // 10
console.log(b); // Still 5 (unaffected by change to a)
// Objects are copied by reference
let obj1 = { name: 'Alice', age: 25 };
let obj2 = obj1;
obj1.age = 26;
console.log(obj1.age); // 26
console.log(obj2.age); // Also 26 (affected by change to obj1)
// Shallow copying objects
let original = { name: 'Bob', profile: { job: 'Developer' } };
let shallowCopy = { ...original }; // Using spread operator
original.name = 'Charlie'; // This won't affect the copy
console.log(shallowCopy.name); // Still 'Bob'
original.profile.job = 'Designer'; // This WILL affect the copy
console.log(shallowCopy.profile.job); // Also 'Designer' (nested objects are still references)
Related Practice: LeetCode: Copy List with Random Pointer - A challenge that tests your understanding of object references.
Linked lists are fundamental data structures that use object references to create sequential collections of data. This video introduces the concept and basic operations.
// A node in a linked list
class Node {
constructor(value) {
this.value = value; // The data stored in this node
this.next = null; // Reference to the next node
}
}
// Creating a simple linked list manually
const head = new Node('A');
head.next = new Node('B');
head.next.next = new Node('C');
// Traversing the linked list
let current = head;
while (current !== null) {
console.log(current.value);
current = current.next;
}
// Output: A, B, C
Related Practice: LeetCode: Reverse Linked List - A classic problem for practicing linked list manipulation.
This video focuses on implementing linked lists using JavaScript classes, creating a more structured and reusable data structure.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
// Add a new node to the end of the list
append(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
// Add a new node to the beginning of the list
prepend(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
// Get a node at a specific index
getNodeAtIndex(index) {
if (index < 0 || index >= this.length) return null;
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current;
}
// Print the list (for debugging)
printList() {
const values = [];
let current = this.head;
while (current) {
values.push(current.value);
current = current.next;
}
return values.join(' -> ');
}
}
// Using the LinkedList class
const list = new LinkedList();
list.append('A');
list.append('B');
list.append('C');
list.prepend('Z');
console.log(list.printList()); // Z -> A -> B -> C
console.log(list.getNodeAtIndex(1).value); // A
Related Practice: LeetCode: Linked List Cycle - Detect if a linked list has a cycle, a common interview question.
This video begins a series on building a complete linked list implementation, starting with understanding the requirements and design considerations.
Related Practice: LeetCode: Design Linked List - Implement your own linked list from scratch.
In this video, you'll learn how to plan your linked list implementation, designing the API and considering implementation details.
/*
INSERT AT INDEX:
1. If index is 0, use prepend method
2. If index is length, use append method
3. If index is out of bounds, return false
4. Get the node at index - 1
5. Create a new node
6. Set new node's next to previous node's next
7. Set previous node's next to new node
8. Increment length
9. Return true
REMOVE AT INDEX:
1. If list is empty or index is out of bounds, return undefined
2. If index is 0, remove head
3. If index is last element, remove tail
4. Otherwise, get node at index - 1
5. Set removed node = previous node's next
6. Set previous node's next to removed node's next
7. Decrement length
8. Return removed node's value
*/
This video covers the implementation phase, turning your plan into working code with a complete linked list implementation.
// Additional methods for our LinkedList class
// Insert a node at a specific index
insertAt(index, value) {
if (index < 0 || index > this.length) return false;
if (index === 0) return !!this.prepend(value);
if (index === this.length) return !!this.append(value);
const newNode = new Node(value);
const prevNode = this.getNodeAtIndex(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
this.length++;
return true;
}
// Remove a node at a specific index
removeAt(index) {
if (index < 0 || index >= this.length) return undefined;
// Remove head
if (index === 0) {
const removedNode = this.head;
this.head = this.head.next;
// If we removed the last node
if (this.length === 1) {
this.tail = null;
}
this.length--;
return removedNode.value;
}
// Remove tail or middle node
const prevNode = this.getNodeAtIndex(index - 1);
const removedNode = prevNode.next;
prevNode.next = removedNode.next;
// If we removed the tail
if (index === this.length - 1) {
this.tail = prevNode;
}
this.length--;
return removedNode.value;
}
// Search for a value, return its index or -1 if not found
indexOf(value) {
let current = this.head;
let index = 0;
while (current) {
if (current.value === value) {
return index;
}
current = current.next;
index++;
}
return -1; // Not found
}
Related Practice: LeetCode: Remove Nth Node From End of List - A problem that tests your linked list manipulation skills.
The final video in the linked list series focuses on reflecting on the implementation, analyzing its performance, and considering potential improvements.
/*
LINKED LIST TIME COMPLEXITY:
- Access: O(n) - must traverse from head
- Search: O(n) - must traverse to find value
- Insertion:
- At beginning (prepend): O(1)
- At end (append): O(1) with tail reference
- At middle: O(n) to find position + O(1) to insert = O(n)
- Deletion:
- At beginning: O(1)
- At end: O(n) to find node before tail
- At middle: O(n) to find position + O(1) to remove = O(n)
COMPARED TO ARRAYS:
Arrays have O(1) access but O(n) insertion/deletion at beginning
or middle due to reindexing.
Linked Lists excel when:
- Frequent insertions/deletions at beginning
- Unknown size (dynamic growth)
- No need for random access
*/
Related Practice: LeetCode: LRU Cache - An advanced problem that often uses a doubly linked list with a hash map.
Complete the Module 3 Guided Project to practice implementing and manipulating linked lists with object references.
Instead of using CodeSignal Arcade which is no longer available, we recommend the following LeetCode collections that follow the same principles and provide great alternatives for interview preparation: