Linked Lists — Why, What and How — Guide for beginners — with code.
Hi, in this blog post you will learn about the basic data structure called Linked Lists,
Why Linked Lists, how to use them effectively, application of Linked Lists, advantages and disadvantages of Linked Lists, Operations that you can perform on Linked Lists. Time and Space Complexity Analysis of Linked Lists.
So lets start with the basic introduction about the Linked Lists.
I believe you are some what familiar with array, Linked lists were made to overcome the problems that array has.
In arrays you cannot add more data then the size of the defined array, now you might say we have dynamic array for that, (i.e. ArrayLists in java & lists in python), but they have their own drawbacks. In dynamic array every time you add element, exceeding the size of the dynamic array, what happens behind the scenes is a new array twice the size of the current array gets created, and it waste the extra memory space that gets allocated to the dynamic array.
Linked Lists overcomes the disadvantages of the array :-
1) Fixed Size
2) Inefficient Memory Usage
3) Slow Insertion and Deletion time.
Now lets have look at how Linked Lists works.
So what happens in Linked list is it stores the data and memory address of the next element that was added or we can use this analogy to understand it better It is like saying I know a guy, who knows a guy, who knows another guy.
Well this is the principle of linked list holding the data and knowing the reference to another Node.
From now onwards lets call data and reference to another data as Node.
Node can be defined as a custom datatype or class which will hold data when the object has been created for Node.
In Linked List the head is the most important part as its the initial reference to where the node lies in the memory. Tail is the end of the linked list.
class Node: def __init__(self, data): // Constructor that takes in the data self.data = data //data self.next = None //reference to next node, None by default.
Well this was just the basic introduction, now lets have look at the code to understand linked lists more better.
FULL CODE IS BELOW
To create a linked list.
Explanation: This function takes the input from the user, convert it into list of integers and then a loop is run to create Node objects using the data from the list of integers, Inside for loop it checks if the data is -1 than it will break the loop as it is consider as the end of the insertion (while taking the input -1 is used to denote end of input).
newNode = Node(data) //is used to create the node of the linked listIt checks if the head = None then assign the current Node as head and Tail, else it uses the Tail.next to set the reference of the Next Node into the Head Node, and it keeps on doing this till the input List Ends. After that it will return the object head.
To traverse through linked list.
Explanation: Traversing through the linked list is very simple, this function takes head as input argument and iterates over the while loop until it reaches the end of the List.
To delete a Node in linked list
Explanation: To delete a Node from the we would require head and element that needs to be deleted. its same like traversing but inside while loop there's an extra if check, it checks if the element is equal to the element that we want to delete, if its equal what the program does is just changes the reference of its previous Node to the Next Node rest is the job of garbage collection in python.
To modify a Node at certain given index.
Explanation: To modify a node at certain index, we need 3 things head node, index(not technically presents), element(new data).
There are better ways to do this, but in our solution i have kind of brute forced my way to get the desire solution. In this case we are iterating over the linked list and we are maintaining a counter variable to create a hypothetical index as there is no concept on indexes in linked list. Before traversing the entire list we check if the index is less than the count of the linked list. While traversing once it reaches the node it just reassign the data head.data = element; if data is modified it returns true otherwise it returns -1.
To search the data if it exist or not.
Explanation: Traversing through the list if the data is found to be equal it returns the index.
To insert at the end.
Explanation: This functions takes in the head and the data, the concept is same go till the end if the head is pointing to none, create a new node and assign the head.next = Node(elem)
To print the Ith Node.
Explanation: The idea is same as modify function above, but here we are just printing that data and breaking out of the loop, if not found return -1.
To count the length of linked lists.
Explanation: Again it is similar as printing the data, we here will just maintained a counter variable as it will hold the number of elements it looped through.
To sort the Linked List in Ascending order.
Explanation: To sort the linked list we can just compare the First Node with the Next Node, SWAP if First Node is greater than Next Node.
if not, do nothing; keep doing this for every single NODE for N times.
Okay, so now that you know how linked list works and how to code them.
Now lets have look at Types of Linked Lists
- Simple Linked List − Only forward traversing.
- Doubly Linked List − Both way forward and backward traversal can be done.
- Circular Linked List − Last node contains reference of the first node as next and the first node has a reference to the last node as previous.
Applications of linked list.
1) Music Player
2) Web Browsers
3) Stacks and Queues
If you think about it, a “Link” is simply a way of identifying a “Next”, “Previous”, “Child” or “Parent” relationship among data instances. So, among real world applications you’ll find a broad variety of applications. Think of a simple List (e.g. Grocery List) for basic Linked Lists. But consider too the uses to which we can place Graphs (plotting distances between cities on a map, interactions among species in biology) or Trees (hierarchies in an organization).
Time and Space Complexity is very important to look at when you are learning Data structure and Algorithms
Time and Space Complexity is nothing but just a way to find which algorithm or data structure is better than the other. It gives us a variable on which we can compare 2 different algorithms.
In space and time complexity when we look at a certain Algorithm we look at its Worst case and Best case, how the Algorithm can perform the worst and what would be the best case in reference to the time of execution and storage.
Time: Insertion O(1) | Deletion O(1) | Searching O(n)
Space : O(n)
Code:
