Getting started with the Linked List
Welcome Back Readers,
Introduction
I am Dhruv Trehan, Microsoft Student Partner and Coding Blocks Campus Representative from India. This blog brought to you, under the initiative started by me #10DaysofInnovation. I would be sharing my learning with students all across the globe, as a step towards learning in a community. In this blog, I would be documenting the information based on the self-made notes while, I was learning Linked List.
Objective
The objective of the article is to acquaint readers with “Linked List in C++”.
Relatively, we would be covering the:
Basics of Linked List
Linked List Vs. Arrays
Basic Operation in Linked List
Insertion, Deletion, Search, Reversing, Building and Printing the Linked List
Implementation
Linked List is a linear collection of the data elements. It is data structure consisting of collection of nodes which together represents the sequence. Each node consists of:
Data
Reference (Address to next node)
Features of Linked List
· Structure of Linked List allows the efficient insertion or removal of an element at any position
· Access time is linear in Linked List
· Random access is not feasible in Linked List
· Arrays have better cache locality compared to Linked List
Cache Locality(Locality of Reference or Principal of Locality): Tendency of a processor to access same set of memory location repetitively over a shorter period of a time.
Benefit of a Linked List over an array
The list items could be easily removed or re-inserted without any reallocation or reorganization of an entire structure because data items could not be restored contiguously. In the disk, while restructuring in an array is a long process
Linked List are dynamic, so the length of the list can be increased or decreased depending upon situation. However, the length of the array remains same as that at the time of deceleration and cannot be changed.
Node
Node is a basic unit of a data structure such as linked list or tree data structure. Node basically comprises of the data and reference to be connected with the other nodes. Let us create a class node in C++.
Most of you, would think why a constructor is created while declaring a node? The reason behind, this is:
· To dynamically allocate space for the node
· To initialize data members of class
· As the node is being used in multiple operations in a code, to make it reachable
Basic operations in Linked List
Now, we would discuss the basic operations of the Linked List
Counting the number of elements in the linked list
Here, we would calculate the total number of elements in the linked list.
DRY RUN:
· The loop would be executed, till the value of head is not equal to NULL
· We have declared a count pointer whose value would increase, till the loop doesn’t terminate
· The value of the count would be the length of the linked list
Insertion (Adding element in the list)
Insertion means adding a new node in a linked list. Insertion is of three types:
Insert at Head
The following code is implemented to insert the node at the head in the linked list:
DRY RUN
· LINE 1: The void function is passed with the parameters
The first parameter is pointing to the NULL in the memory , used as a reference pointer to the the node
The second parameter is a data to be added in the linked list
· LINE 3: It is a dynamic allocation of a heap memory to the value passed by the main (Data)
· LINE 4: ‘->’ is a reference pointer used to point to the members of the class. The value of is changed with the address of the head
· LINE 5: The address of head would change to the address of the data passed
Insert at the tail
The following code is implemented to insert the node at the tail in the linked list.
DRY RUN
LINE 4–8: In the above statement, the condition where only one element passed in list is checked
LINE 10: A new pointer named “Tail” is declared with passing value of “Head”
LINE 12–15: Loop runs until “Tail” reaches to the end of the Linked List
LINE 17: With the help of constructor a new pointer named n is customized
LINE 19: Value is added at the end of the tail pointer
Insert at the Middle
The following code is implemented to Insert the node in the middle of the linked list:
DRY RUN:
· LINE 3–6: In the “IF” Statement, the base condition is check, if it has only one node, so “Insertathead()” function is called.
· LINE 7–10: In the “ELSE IF” Statement, the second condition is checked, if the length of the given linked list is more than the required length. In such a case, “Insertattail()” function is called.
· LINE 11–24: In the “ELSE” Statement:
A new variable “JUMP” is assigned with value 1
A new pointer “Temp” is assigned with value “head”
A loop is customized till, the jump is not equal to the (entered position — 1)
A new node (n) is dynamically allocated the memory using the constructor
Now, n (node to added) would point to the node next to its position
Now, address of next would point to the node that is no be inserted
Deletion (Removing the element from the list)
Deletion means removing the node from the Linked List. Deletion are of three types:
Delete at Head
The following code is implemented to delete at the head of the linked list:
DRY RUN:
LINE 3–7: Basic condition is checked, that the element exist in linked list or not
LINE 8–14: In the “ELSE” Statement:
A new pointer name temp is declared with value (head)
Head is made to point to next variable
Finally the head which was assigned to temp is deleted
Return statement is executed
Deleting at Tail
The following code is implemented to delete at the Tail of the linked list:
DRY RUN:
LINE 19: A new node named “Temp” would be pointing to head (the value is NULL)
LINE 20–24: A loop is executed until the value of temp is NULL
Prev is pointing to one less than a last node
Temp is pointing to the last node
LINE 25: Temp is deleted
LINE 26: Prev which store last node, is made to point to NULL
LINE 27: Finally, a value is returned
Deleting at the Mid
The following code is implemented to delete at the middle of the linked list:
DRY RUN
LINE 32–42
Variable “I” is pointed to 1
A pointer is declared in which stores the value “head”
A loop is executed ; till the position where to delete the node is not found
As, the loop is terminated
The value of prev is changed to the node which is to be deleted
The value of fast is changed to next of the deleted node
Finally delete prev
Return from the function take place
Searching in the linked list
Searching means finding the element in the Linked List:
DRY RUN
It is the recursive function to search the element in the Linked List
The three conditions are implemented in the DRY RUN
The “IF” Statement states that, “ the value at the head is 0” then return would be executed
The second “IF” Statement states that is a base case of recursive statement, if the data is found true is returned
The “Else” Statement is a recursive case in which the the value is passed again and again
Reversing the Linked List
Reversing the linked list, means changing the order of the given list.
DRY RUN:
A normal reversal take place using swap of the variables
You can refer to swapping to understand the context
Building the Linked List
Here, we would learn a way to build a linked list.
DRY RUN
In this code , data is asked from the user, till the user doesn’t input -1
The data is added in the Linked List in the sequential manner using insertatTail() method
Printing the Linked List
This code is used to print the linked list:
DRY RUN:
· Value of head is stored at the local pointer, in the temp
· A while loop is executed until the NULL Statement is reached
· Simultaneously, linked list is printed and value of temp is changed
Conclusion
Here, we come to the end of this blog. In this blog, the author discussed the concept of Linked List, covering the basic operations in linked list like: Insertion, Deletion, Searching, Building a linked list, Reversing a Linked List, and Print the Linked List.
Acknowledgment
I have created a repository to share my daily code byte, I would learn in Data Structure and Algorithm.
GitHub Repository: https://github.com/DhruvTrehan/Data-Structure-and-algorithm
