DataStructures Series — 7
N.B. This article would make more sense if you read previous articles in this series.
In case you missed last week on the data-structures series here.
We discussed the Queue ADT and we wrote some pseudocode using an array to implement it. We also discussed how some popular applications use the queue data structure.
This week we would be discussing the Linked List ADT.
The Linked List ADT
A linked list is a linear collection of data elements, unlike the array ADT, its order is not given by their physical placement in memory. Instead each element points to the next.
It consists of a collection of nodes which together forms a sequence. In its most basic form, each node contains two cells, one cell for the data and the other contains the memory address of the next node.
LinkedList Operations:
- Insert(data, position)
- delete(data)
- insert(data)
- delete
- get (data)
Insert (data, position) — This would insert a data at the specified position in the list
delete (data) — This would delete a data at the specified position in the list
insert (data)— This would add a new data to the end of the list
delete — This would delete the last data in the list
get (data) — This fetches the data from the list sequence
Implementation
The approach here is to create a class to represent a node with its following properties.
Below is a pseudocode implementation:
new Class Node {
int data = null; Node nextNode = null; class_constructor(data, nextNode) {
this.data = data;
this.nextNode = nextNode;
}}
Now, we have the node class with two properties data and nextNode.
Pseudocode Usage Example:
Let us create a list sequence of 1 → 3 → 4
Node four = new Node(4, null);Node three = new Node(3, four);Node one = new Node(1, three);
We have 2 missing in the sequence, so let us quickly insert that at position 1 (assuming the sequence is zero-indexed) and have a proper sequence:
1 → 2 → 3 → 4
insertNode (2, 1) :
Node headNode = one; // value already in memoryNode currentNode = headNode;
Node previousNode = null;
$counter = 0;
while (currentNode is not null) {
if (counter == 1) {
Node dataNode = new Node(2, currentNode);
previousNode.nextNode = dataNode;
break out of current loop;
}
previousNode = currentNode;
currentNode = currentNode.nextNode;
counter++;
}
And then we can decide to delete the three in the list so the sequence looks like this: 1 → 2 → 4
delete (3) :
Node headNode = one; // value already in memoryNode previousNode = null;
Node currentNode = headNode;
while (currentNode.nextNode is not null) {
if (currentNode.data == 3) {
previousNode.nextNode = currentNode.nextNode; // bypass node 3
break out of the while loop;
}
previousNode = currentNode;
currentNode = currentNode.nextNode;
}
To insert 5 into the list so the sequence becomes 1 → 2 → 4 → 5
insert (5) :
To speed up this operation, we would have an additional field to keep track of the last node and update it every time we insert a new element. This would prevent us from starting from the beginning of the sequence to insert a new element.
Node lastNode = four; // value already in memoryNode five = new Node(5, null);
lastNode.nextNode = five;
lastNode = five;
To delete, we have to start from the head till we get to last Node. Deleting the last node leaves us with this again: 1 → 2 → 4
delete () :
Node headNode = one; // value already in memory
Node lastNode = five; // value already in memoryNode previousNode = null;
Node currentNode = headNode;
while (currentNode.nextNode is not null) {
previousNode = currentNode;
currentNode = currentNode.nextNode;
if (currentNode.nextNode = null) {//check if currentNode is last
previousNode.nextNode = null;
lastNode = previousNode;
break out of while loop;
}
}
To search for data in the list sequence, we have to start from the head of the sequence and go all the way to last element in the sequence. we stop searching when we find one occurrence of the element.
get (2) :
Similar to delete at position, we loop through the sequence and look for a node with value 2 and return the Node.
We can clearly see that some of the methods are very inefficient as we have to loop through the sequence starting from the head to perform an operation.
Next week, we would be looking at types of Linked Lists and also look at how they improve these operations.
REFERENCES:
