Understanding Linked Lists | C++ and Python Implementations | Usage | Why matters | Comprehensive Guide

Introduction To Linked Lists

Basically, Linked List is a data structure used for efficent reterieval, insertion and deletion of data cells. In this data structure we don't need to make shifting of elements from deleted or inserted element's index to onward. So, if we want to optimize our dealings with data storage in lists in any language, than linked List is best option to choose.

Comparison with Arrays

So, why would we say it's better to choose LinkedLists over arrays. So, basicaly when we want to insert an element in an array what happens in back end, all the element after the index where we want to insert shift one place farward. Similarly, when we want to delete an element from an array, we simply run our delete command, but in the backend all the elements take time to move one step backward in order to fill out the vacancy generated by the removal of an element. So, this is cool in small arrays, but if the size of our array is too large which mostly happens when we dela with rela world problems, then arrays become less effiecint as compared to Linked lists where there's no need for elements to move back in deletion and to move farward in insertion.

In C++, if we create even dynamic arrays, then to insert any element we have to follow these steps :

• First create a new dynamic array of size plus one of the size of previous array
• Copy all the elements from previous array
• Insert the new element in this newly built array
• Delete the previous array

Here, we can see how time, space recquired to accomplish only insertion in arrays. But in Linked Lists, we can increase size of array to any extent and insertion, deletion happens in constant time O(1).

In Python, although we have lists, and the size of List increases automatically as we insert new ones, and reduces as well when we delete any item. But, in python, we again prefers to use LinkedLists, see why ?

• As we know, in list elements are arranged in contigous way. Means, if we have a list of 10 elements, then it will store in the same block of 10 cells in memoy one afterthe other and no gaps. So, when some times, when we want to append new element, and there's no space in that block to add new element contigously. Python creates a new, larger block of memory, copies the existing elements, and frees the old memory block. And if the list is large in size, this reallocation becomes surely inefficient.
• MoreOver, deletion and insertion takes O(n) time, as compared to Linked Lists which take constant time to insert and delete, because we only play with pointers in Linked lists.

Why choose Linked Lists over Arrays?

Although, we already discussed comparison of arrayts with linked Lists, yet we need to discuss, the WHY of this?

I'll explain this in easy way. Suppose we have memory of only 10 elements to store and these spaces are random in memory like 0x1004, 0x2104, 0x0016 and etc. And we also want to store 10 elements, if we make array, than we know that array stores element contigously means in a block. Like array will store 10 values in block having address like this : 0x1004, 0x1008, 0x10012, 0x10016, 0x10020, 0x10024, 0x10028, 0x10032, 0x10036, 0x10040. Here, we can see that address of elements are contigous (One after the other with same difference of 4 which is here only because integers take 4 bytes). But we haven't consistent space, we have random positions to store. So, here we can't use arrays, because array stores in single block. But, we can store 10 values via Linked Lists. Because Linked lists stores element in random positions and it will store those 10 elements in random addresses, which are avialaible in memory.

Structure of a Linked List

As, we discussed that Linked List stores elements in random addresses, like if first element is at address 0x10024, then the other will be at 0x14034. So, to move to other elements, we need to store the address of next element in current element, so that we can move to next element easily. I arrays, as the address are stored next after the other, like if address of element in array are : 0x1004, 0x1008, 0x10012, 0x10016, 0x10020, 0x10024, 0x10028, 0x10032, 0x10036, 0x10040. And we are in want to move to 4th element, we will just write *(arr + i * 4), where 4 is number of bytes intger take to store in memory, arr is the address of first element and i is the index where we want to move. That's why in array we don't need store addresses.

So, we will use two classes

1. Class Node, where we will have a data member named value and other data member will be the address of next element.
2. Class Solution, where we will use these nodes to perorm different operations like insertion, deletion, and other operation of linked List.

Resources : To see the structure of Linked Lists both in python and C++, you can see my repositories:

For C++ : Linked Lists Structure in C++

For Python : Linked List Structure in Python

When to Use Linked Lists

• So, if we want to search then arrays will be efficient to use, because here we can direct reach to desired element. So, if we want searching, then arrays are most preferred to use.
• But in case of insertion and eletions, we'll prefer to use LinkedLists, as their advantages and array's disadvantages we already discussed earlier.

Basic Operations In Linked List

The three basic operation, we mostly implement on Linked Lists are :

• Searching, Let's suppose user wants to search an element in linked list, so for this we will move our linked list untill we reach to that value and than print it and break the loop, if we reach to NULL it menas value not found. So, for search ing we need to traverse th list untill value not found.

• Insertion, To insert at particular position. Here, you have to check some cases : -> If we want to insert at position '0', means at the start. -> If we want to insert at middle of the linked list -> If we want to insert at the end of the list We will check all these cases if the list is not empty, if empty and position to insert is greater than 0 it means we will print error message List is empty then how can we insert at 4th or 5th or any other poistion.

• Deletion, , To insert at particular position. Here, you have to check some cases : -> If we want delete element at position '0', means at the start. -> If we want to delete element from middle of the linked list -> If we want to delete element from the end of the list We will check all these cases if the list is not empty, if List is empty then how can we delete any element from Linked List.

Excercise To Implement

To better understand the logic behind linked lists, it’s essential to implement them from scratch and practice through various exercises. I’ve created repositories where I provide examples and coding challenges specifically designed to help you grasp the core concepts of linked lists. For both C++ and Python, you can find separate examples and tasks that will guide you through creating nodes, performing traversals, and implementing insertions and deletions in linked lists. These exercises will strengthen your understanding of how linked lists function at a low level. Follow my repositories to explore these examples and challenges:

• C++ Linked Lists Exercises & Solutions
• Python Linked Lists Exercises & Solutions