Linked Lists
Learning Goals
- Understand what a linked list is
- Understand the cost/benefit trade-offs of using arrays vs linked lists
- Focus on problem solving processes to start building out a linked-list
What is a Linked List?
A linked list is a data structure composed of nodes. A node is simply a space in memory that contains some data. This data can be a string, integer, object, etc. In addition to the data that’s being stored in the node, each node will contain a pointer, or reference, to the next node.
Here is an example of what a LinkedList would look like in JS:
class ListNode {
constructor(data) {
this.val = data;
this.next = null;
}
}
const linkedList = new ListNode(1);
linkedList.next = new ListlinkedList(2);
linkedList.next.next = new ListNode(3);
// Looking at the value of what the variable node returns
=> ListNode {
val: 1,
next: ListNode {
val: 2,
next: ListNode {
val: 3,
next: null
}
}
}
// Or in object literal syntax
=> {
val: 1,
next: {
val: 2,
next: {
value: 3,
next: null
}
}
}
Click here to see an example of this being run in Repl.
As a result of this, each node has a value property describing the data it is holding. It also holds a property that points to the next node. When it reaches the last node, it points to null because there are no values at the end. This effectively creates a node list where nodes point in this order 1->2->3->null.
The example above is a singly linked list. There are other flavors of linked lists, including doubly linked lists (each node points to the following node and the preceding node) and circular linked lists (the final node points back to the head node).
Turn & Talk
In your own words, explain what a linked list is. Then explain what each line is doing in the previous example. Make sure each person gets the opportunity to explain!
Arrays vs. Linked Lists
Linked lists seem very similar to Arrays, and you might be wondering when or why we would use one over the other. Read through some of the answers on this stackoverflow question to learn about the differences between the two data structures and their pros vs. cons. We’ll discuss them together as a class.
Synthesis of Arrays vs Linked Lists
Arrays
- Built-in to JS & Ruby by default
- Expensive to add & remove items
- Easy to access random items
Linked Lists
- Must be implemented by you
- Cheap to add & remove items
- Difficult to access random items
Practicing with Linked Lists
While understanding high level concepts can be important during an interview, your problem solving process can be even more important. Complete the following:
Pass The Tests
In either the JS Repl or Ruby Repl, read & utilize the tests to create a ListNode class that allows you to add a new node to the end of a LinkedList in the same way push works on Arrays. You will be working on this in breakout groups for the rest of the session. Even if you are not as familiar with the language, focus on your processes and the logic behind the problem.
Closing Reflection
- Why use a linked list over an array? Or an array over a linked list?
- What went well with your process during the exercise at the end? What didn’t go well? What can you change for next time?
