Data Structures and How To Build It From Scratch (Linked List) #3
LinkedList is the dynamic data structure, as we can add or remove elements at ease, and it can even grow as needed. Just like arrays, linked lists store elements sequentially, but don’t store the elements contiguously like an array.
So we are going to make one class called LinkedList and it contains four main methods: append(), prepend(), insert(), and remove().
First, we have to create a class and its constructor. We need to create attributes like head, tail, and length.
head is an object with value and next, the value will be initialized with the value from a parameter of constructor. Tail will be equal to head, because when it first initializes, it only has 1 data which makes tail and head the same. Length is automatically 1.
Next, we gonna make our first methods, append. Append is a method to add a new node to the last one.
We make a variable called newNode, it is an object with value and next. And then we gonna set this.tail.next to newNode and this.tail to newNode. And increment the length because we just added 1 data into our LinkedList. It might be confusing for you to see step 1 and step 2, I will explain more.
In step 1, we set this.tail.next to a variable newNode or an object with value (let assume value from method append argument is 1) and next. Because this.tail is a reference to this.head, it will look like that after we set this.tail.next to a variable newNode.
In step 2, we just simply set this.tail to a variable newNode (let assume the value from method append argument is 1)because it will be the last data of our LinkedList.
And the next method is prepend(). Prepend is a method to add a new node to the first data.
Same like append(), we have to create a variable called newNode. After that, we set newNode.next to this.head and this.head to a newNode. And then we have to increment this.length. Last we have to return this. I will explain more step 1 and step 2.
Let’s assume we have this.head with value is 1 and next is null. So the step 1 will be like this.
And for step 2, we set this.head to a newNode and we modified it before step 1. So it will look like this.
To be able to imagine our data more clearly, we need to make a helper method called printList(), this method will print all of the values from node and it will be an array. Example: [1, 3, 4, 10]
The next method is insert(), unlike prepend and append which can only insert a node at the first or last data, insert() will add a node based on the given index.
First, we need to have 2 parameters index and value. And then we need a conditional, if the given index is greater than or equal to the length of our node, we will add the node at the last data. Same as in other methods, we have to make a variable called newNode. After that, we have a helper method called traverseToIndex.
Basically, traverseToIndex will return the data before the given index. Let’s assume we called LinkedList(1) and append() 3 times and the given value 3, 6, and 10. It will be [1, 3, 6, 10] if we called our method printList().
If we have data [1, 3, 6, 10] and the given index is 2, it will return the node of 1 and 3 or [1, 3]. So variable leader will have a value node of 1 and 3 (and of course the value of next from node 3).
And then we make a variable called restOfLeader equal to leader.next, which means it will be the rest of data [6, 10]. After that, we set leader.next to our newNode (not [6, 10] anymore, but will be [givenValue]) and set newNode.next to restOfLeader. In the end of insert(2, givenValue) method, it will be [1, 3, givenValue, 6, 10].
The last method is remove, remove will delete the data based on the given index.
So we have our final data [1, 3, givenValue, 6, 10]. If the given index is 2, variable leader will be [1, 3]. After that, we set leader.next (givenValue) to leader.next.next (6). So the final data will be [1, 3, 6, 10].
Our final code will look like this.
Do you realize that all we did is just for a Single Linked List? (it doesn’t have previous). What about Doubly Linked List? Well, we have to modify our code for that.
First, we have to modify our class and constructor. We add prev as a null.
Next is append(), we have to add prev inside newNode and set newNode.prev to this.tail.
After that, we have to modify our prepend(). We have to add prev inside newNode and set this.head.prev to newNode.
And the last one is insert(). So we have to add prev inside newNode. After that, we set newNode.prev to leader and restOfLeader.prev to new Node.
Final code of Doubly Linked List.
I’ll see you on Data Structures and How To Build It From Scratch (Stack) #4!
