Implementing a Singly Linked List
Overview
A singly linked list is a type of data structure commonly used in computer science. Basically, a linked list is a linear collection of data elements of any type called node. Each node has a value and points to the next node in the linked list as shown below.
Why use a linked list over an array? Well a linked list has an advantage that arrays does not have where values can be efficiently inserted and removed without relocating the rest of the list. Pretty cool! In this article, we will develop a basic linked list which will include the following methods:
- Append: inserts the given item at the tail of the linked list
- Length: returns the length of the linked list by traversing its nodes
- Find: returns an item from the linked list satisfying the given quality
- Delete: deletes the given item from the linked list
Node
In a linked list, a node is where data is stored. Think of it like an easter egg! Each easter egg contains a treat which the treat represents the data that is stored. A node also has a pointer, a reference to another node in the list like the picture shown above. Here’s a simple implementation of the node class.
In this Node class, we will initialize a single datum and it’s pointer (this pointer is set to None by default). We set the pointer to None by default because the very first node in the list will point to nothing since it’s the only node in the list.
Linked List
In a Linked List class, we want the head node and the tail node to be set to None. When a linked list is first initialized it has no nodes, so the head and tail node is set to None. (Note: when a linked list is first initialized it will takes in a iterable , if given, which will append each element in the linked list.)
Append
The append method simply adds the given item to end of the list. First you want to create a new node to hold the item that is being passed in. When adding a new node in a linked list you want to check if the list is empty. If so, make this new node the head node of the linked list. (Note: you want the new node to be the tail node regardless since we are appending the item at end of the list.) Otherwise, if the list is not empty; make the tail node point to the new node.
Here’s a demonstration when appending a new node in a linked list shown below.
Length
This method basically keeps count of nodes until it can’t no more and returns the length of the linked list. For this method while traversing through the linked list you want to start at the head node to be able to traverse through the linked list. you want to update the node count variable as shown below.
Find
The find method is quite similar to the length method. In this case, we’re going to traverse through the linked list until we find the requested item. This means as long as the current node does not equal to None and it does not match the requested item; continue to traverse the linked list. If the current node holding the data matches the requested item we are looking for; return the current node holding that data! If we traversed through the whole linked list and the requested item was not found; raise a value error to notify that the item requested was not found.
Delete
The delete method is tricky in comparison to the other methods we implemented. In this method, we’re going to switch up our logic quite a bit. Keep in mind that the item that we’re looking for could possibly be located at the head, somewhere in between the linked list, and at the tail. If the item to be deleted is the head node; update the head node to the next node. If the node to be deleted is the tail or somewhere in the middle, we want to keep track of the previous node by creating a variable. This will allow us to remove the pointer or reference of the current node (Note: the node that we want to delete) without losing the reference to the other nodes in the linked list. If the item to be deleted is the tail node; update the new tail node to the previous node and update its pointer to the old tail nodes pointer. Otherwise, if we traversed through the whole linked list and the item is nowhere to be found; raise a value error to notify the item was not found.
Conclusion
After all, implementing a linked list is not bad at all. I hope while reading this article you learned something new about linked lists. If you found this article helpful give this article some claps and if you have any questions regarding this article, please feel free to reach out to me. I would love to give feedback.
