As the name suggests, the linked list comprises elements linked together by a bond or a linkage. In computer science, a linked list refers to a group of entities having data in them. These entities further point to the next entity containing some other valuable data.
Table of Contents:
- Advantages of Link List
- Link List: Concepts
- Link List in Python
- Insertion to the LinkedList
- Deletion from the LinkedList
- Disadvantages of Link List
Moreover, these entities’ order is not allotted by their placement in memory but because each entity gives the next one’s address. In short, a linked list is a kind of data structure which is consisted of nodes. Each node in the list contains two things. The first thing is the stored data, and the second thing is the link to the next node. This link between two nodes is referred to as reference or pointer. Thus, the collection of such nodes makes a sequence which is called a linked list.
Advantages of Link List
As mentioned earlier, the link list is a dynamic data structure. When working with unexpected data, it provides the liberty of extra memory usage on run time. Furthermore, there is no need to allocate memory beforehand in case the program needs it. The link list modifies itself to shrink or grow as the program runs further.
Also, working with complex programs using a link list proves helpful. For example, it helps implement linear data structures such as Queue and stack easily to run the program efficiently. Moreover, addition and deletion functions are relatively more straightforward in link list than in other data structures. The users can perform these functions by updating the previous node’s link without shifting nodes like in arrays. It also provides faster access to Data without memory overhead than others.
Link List: Concepts
As mentioned earlier, the link list consists of nodes. Every node has Data and pointer to the next node. The pointer part is called Next. The first node or the starting point of the list is called Head and its Next points to the next node. Whereas, the Next of the last node points to None.
Link List in Python
A node is a simple data block of a list connected using pointers. Each block stores the user’s data and the next node’s address to quickly locate the next node. The python code below shows a simple class of node which stores a data value and the “next” pointer to point to the next node in the list. When the user creates the node class object, the program assigns null to both data and next.
Class Node: def __init__(self, data = None): self.data = data self.next = None
The above code only creates the individual nodes of the list. Now, the user needs to write a class for the link list to maintain and connect the nodes, saving him from remembering and changing the nodes repeatedly. This class stores the pointer to the Head of the list, i.e., the first node. The below python code shows a class of LinkedList, which creates an empty LinkedList.
class LinkedList: def __init__(self): self.head = None
The user can create a link list containing the data such as weekdays’ names using the below python code. It creates a LinkedList with the name “List1,” which stores the Head to the node containing the value “Mon.” This node points to N2, which contains “Tues,” which points to N3 containing “Wed.” The user can observe from the below code that the next pointer of node “N5” is NULL because it doesn’t point to any node in the list and hence is the last node in the LinkedList.
List1 = LinkedList()
List1.head = Node("Mon")
N2 = Node("Tue")
N3 = Node("Wed")
N4 = Node(“Thurs”)
N5 = Node ("Fri")
List1.head.next = N2
N2.next = N3
N3.next = N4
N4.next = N5
Now when the user has created a LinkedList, it is essential to have a traversal function that prints the data stored in the linked list. The print function assigns the value of Head, i.e., the first node’s address to pointer “p.” Then, it prints the data of all the values and assigns the next node’s address to the pointer “p” until it reaches the end of the list, i.e., the pointer to the next node becomes empty. The user can understand this concept from the above code that the next pointer of the node “N5” is empty because it does not point to anyone.
Weekdays through Link List
def print(self):
p = self.head
while p is not None:
print(p.data)
p = p.next
List1 = LinkedList()
List1.head = Node("Mon")
N2 = Node("Tue")
N3 = Node("Wed")
N4 = Node(“Thurs”)
N5 = Node ("Fri")
List1.head.next = N2
N2.next = N3
N3.next = N4
N4.next = N5
List1.print()
Output
Mon Tues Wed Thurs Fri
Insertion to the LinkedList
As the LinkedList nodes are connected by merely pointers, the users can add anywhere in the list by inserting the node in the list and changing the pointers of the previous and next node of the list. For instance, if the user wants to add a node at the beginning of the linked list, he makes the new node point to the first node, and the Head points to the new node. The image below visually explains this concept of insertion.
The python function for insertion at the beginning is given below:
def Insert_at_beginning(self,data): Node4 = Node(data) Node4.next = self.head self.head = Node4
The function given above takes the data, which it has to add to the list’s beginning. First, it creates a node and adds the data to it. It then assigns the Head’s value, which is the previous first node’s address, to the new first node. Lastly, it assigns the address of the new node to the Head. Now head points to the new node, which makes it the first node in the list
Adding a Weekday into Link List
List1 = LinkedList()
List1.head = Node("Mon")
N2 = Node("Tue")
N3 = Node("Wed")
N4 = Node(“Thurs”)
N5 = Node ("Fri")
List1.head.next = N2
N2.next = N3
N3.next = N4
N4.next = N5
List1.Insert_at_beginning (“Sun”)
List1.print()
Output
Sun Mon Tues Wed Thurs Fri
Deletion from the LinkedList
The deletion from the LinkedList is as more straightforward as an insertion to the linked list without wasting any space. The user can remove the node by searching through the list to find the key node and then make the previous node point to the next node instead of pointing to the key node.
The “Delete” function takes the value that it has to delete from the list in the code below. It then matches the data of all the nodes to find the key node. While searching the data, it keeps the pointers to the current node’s prev and next nodes. When it has found that key node, it merely makes the prev node point to the next node, skipping the current node, which removes the current node from the list.
Note: The users can also write search function using delete function
def Delete(self, Data): current = self.head if (current is not None): if (current.data == Data): self.head = current.next current = None return while (current is not None): if current.data == Data: break prev = current current = current.next if (current == None): return prev.next = current.next current = None
Deleting a Weekday from Link List
List1 = LinkedList()
List1.head = Node("Mon")
N2 = Node("Tue")
N3 = Node("Wed")
N4 = Node(“Thurs”)
N5 = Node ("Fri")
List1.head.next = N2
N2.next = N3
N3.next = N4
N4.next = N5
List1.Insert_at_beginning (“Sun”)
List1.Delete(“Mon”);
List1.print()
Output
Sun Tues Wed Thurs Fri
Disadvantages of Link List
When the link list has various advantages, it has some disadvantages as well. Since it consists of pointers, it consumes more memory because pointers need extra memory for storage. Also, it would take a while to get to a specific node in the link list. The reason is that it does not support random access to any node.
Furthermore, the program’s time complexity increases with the link list’s use due to individual access required for every node. Moreover, reverse traversing a singly link list is rather tricky than a double link list. Finally, the link list is a useful data structure depending on its purpose and implementation.
