Linked List
In the last article
https://medium.com/catalysts-reachout/arrays-f1f71e230881
we got to know about array data structure. Talking of arrays. It is not the most efficient in terms of memory usage. There are some limitations in array data structure.
Suppose a user need to store some data in memory, he can communicate to memory manager in a HLL (example C or C++). He communicates to memory by declaring an integer variable (example a).
The memory manager provides 4 bytes of memory, as the user request for integer, which is typically stored in 4 bytes. Address of the block of memory is the address of the first block of the memory.
Suppose the user wants to store an array of integer which has 10 integers in it. The memory manager allocates 400 bytes of memory, which is stored in one contiguous block of memory.
To access any element in an array it takes constant time. What if the user needs to store 2 more elements in the array, but he has already declared an array of size of 10 integers. So, in order to store 2 more elements in an array he need to redeclare the array with size of 12 integers and he needs to copy all the elements of array b to new array c.
So, copying all the elements again and again to a new array, is a very costly operation. The solution to this problem is Linked List Data structure.
Suppose a user needs to store some numbers, but he is not aware of how many numbers he might store. He requests for 2, then 7, then 1, then 8, and so. The numbers will be stored in disjoint non-contiguous block of memory. But how can we traverse from one integer to another, as they are not stored in one contiguous block of memory. So basically, we need to link these blocks of memory. What we can do is we can make two parts in each block like data field and the address fields. The data field stores the data and the address field stores the address of the next block. The address fields of last Node in the linked list is pointing to NULL, hence indication the end of list.
Basic structure of Linked List would be
Now the question comes when to choose array and when to choose linked list???
Implementation of linked list
Inserting an element at the end of the linked list
Insert at the beginning of the linked list
Deletion of element in a linked list
Printing a the elements of the linked List
Then we have doubly linked list and circular linked list.
Doubly Linked List: In doubly linked list we would have three fields: data, next and previous.
Next is a pointer to next block of the linked list and previous is the pointer to the previous node of the linked list.
Implementation of doubly linked list
Inserting an element in a doubly linked list
Deletion of node in doubly linked list
Displaying the elements of Doubly linked list
Circular Linked List: In singly linked list the last node pointes to NULL, but in circular linked list the last node points to head node.
Insertion of an element in a circular linked list
Displaying the circular linked list
Deletion in circular linked list
Advantages of linked list
- A linked list is a dynamic data structure because it can grow and shrink at runtime by allocating and deallocating memory. As a result, there is no need to specify the linked list’s initial size.
- There is no memory wastage in the linked list because the size of the linked list increases or decreases at run time, so there is no memory wastage and no need to pre-allocate the memory.
- Linear data structures such as stacks and queues are frequently easily implemented using a linked list.
- Insertion and deletion operations in the linked list are much simpler. There is no need to shift elements after an element is inserted or deleted; only the address in the next pointer must be updated.
Disadvantages of linked list
- In a linked list, traversal takes longer than in an array. A linked list, unlike an array, does not allow direct access to an element by index. For example, in order to access a node at position n, one must first traverse all the nodes preceding it.
- Reverse traversing is not possible in a singly linked list, but it is possible in a doubly-linked list because each node contains a pointer to the previously connected nodes. Because this extra memory is required for the back pointer, there is memory waste.
- Because of the dynamic memory allocation in a linked list, random access is not possible.
- More memory is needed withinside the linked list compared to an array. Because in a linked list, a pointer is likewise required to keep the address of the following element and it requires more memory for itself.
To get comfortable with linked list you can check the following link, a link to GitHub repository , where I’ve added some resources.
Thanks for reading! If you have any queries feel free to drop an comment.
