Adding to Linked Lists — JS Data Structure
Linked Lists were the hardest data structure for me to wrap my head around. Objects floating in memory, connected by pointers? It took me a while to understand this conceptually. Here is an implementation of a Linked List with an ‘addToTail’ method.
Step 1: Create a Constructor Function. (This example is in the functional style). Here’s the skeleton:
var LinkedList = function() {
var list = {};
list.head = null;
list.tail = null;
return list;
};Step 2: Create a function variable that will return an object with the properties ‘value’ and ‘next’.
var Node = function(value) {
var node = {}; node.value = value;
node.next = null;
return node;
};
Step 3: Write ‘addToTail’ method inside LinkedList. What we’ll need to do:
- Create a new Node object
2. If it is the first node being added to the list, set both list.head & list.tail to the new Node object.
3. Otherwise, set the tail’s next property to the Node object, and re-assign the list’s tail to the node.
var LinkedList = function() {
var list = {};
list.head = null;
list.tail = null; list.addToTail = function (value) {
var node = new Node(value); //create a new Node object if (list.tail === null) { //first Node being added to list
list.head = node;
list.tail = node; } else { list.tail.next = node;
list.tail = node;
}
return list;};
Let’s say the first node has value of 5. Execute the first if statement.
list.head = { value: 5, next: null}
list.tail = { value: 5, next: null} Add a node with value of 6. Execute else statement.
list.head = { value: 5, next: undefined}
list.tail = { value: 5, next: Node(6)}Re-assign list.tail to point to Node(6).
list.head = { value: 5, next: {value 6: next: null}}
list.tail = { value: 6, next: null }