Data structures and Algorithms are the backbones of computer programming. As a programmer, it is very important to have a good command over them. This article is about what is a Linked list? and implementation of Singly linked list using Python programming language.
Also Read: Implementation of Dynamic Arrays in Python Programming
Contents
What is Linked Lists?
Linked List is a linear data structure. Basically, these are the links in a chain that can be very long, and these chains are nodes that together form a linear sequence. The diagram representation is shown below.
In a linked list, each node contains two elements i.e a value of any type since it is a kind of an array and reference to the next element in the sequence as shown in the figure above.
Singly Linked List & its implementation through Python language
A singly linked list is also a collection of nodes and has a starting point called as HEAD and an endpoint called TAIL.
- Head is the pointer that simply points or identifies to the first element in the singly linked list.
- Tail identifies to the last node in the singly linked list and in this case, the reference part of the node points to nothing or nil.
This is what a single list liked looks like diagrammatically. Each node has a Key/Value which are strings in the case shown above, and a reference i.e. a next pointer that points to the next element. Basically, the first node is the head and the last node is the tail in the list. The movement from one node to other is called traversal in the list.
NOTE: A singly linked list does not have a predetermined size so it uses space proportionally according to the number of elements present in the list and unlike arrays, it does not have the contiguous memory allocation i.e. they are not allocated one after another, rather, distributed in memory and attached through pointer that we call the reference part.
Basic Operations in the Singly Linked List
There are basically two operations that we usually perform with the singly linked list.
- Push i.e. inserting a new element.
- Pop i.e. deleting/removing an element from the list.
Push Operation
In the push operation, we simply take a new key/value and add that to the existing list. The push operation can be performed in different cases.
- Inserting the element at the beginning.
- Inserting the element at the end.
Inserting the element at the beginning
Inserting the element at the end
POP Operation
The removal of an element from the head of the list is the opposite process of insertion of elements at the head side but, deletion of the last node is a tiresome operation and it is not an easy task. You must be wondering Why?
Well, suppose there is a singly linked list containing 20 values and we want to delete the last element, in that case, we have to traverse to the last node then only we can delete it, and this is not an efficient method. In Computer Science, solving a given problem with efficiency is a major concern and the above-described traversal method is not the proper solution we can go for.
Pros and Cons of Singly Linked List
Pros
- They have constant time insertion and deletions in any case.
- Its size is not fixed and is flexible
Cons
- The accessibility of the elements in the linked list is not easy and is a lengthy process and the time in the form of Big O notation is given by O(k) for traversal from head to the (kth) element of the list.
Code
You can use any text editor and try out this code.
OutPut:
For a detailed study, review and practice problems, you can check out this course: Complete Python Bootcamp: Go from zero to hero in Python on Udemy.
