Introduction
Data structures in programming are often compared to the human brain. A data structure is a man-made way to use a computer’s memory efficiently. In programming, data structures like linked lists, arrays, and graphs organize and store data so that it can be accessed, retrieved and manipulated efficiently. In this blog, we will dive into linked list, its types, operations, advantages and disadvantages, and real-world applications.
Data Structures in Programming
In computer science, data structures are fundamental concepts. Think of how the human brain stores memories in different regions and how the neural networks retrieve the memories as and when needed. In computer programming, data structures also perform a similar function. A data structure allows you to efficiently access, manipulate, and retrieve data organized and stored in a computer’s memory. Data structures play an important role in computer programming and software development. Different data structures are used to solve various computational problems.
Types of Data Structures
Data structures can be categorized as linear and non-linear.
Linear Data Structure
Linear data structures store data sequentially. Data is arranged such that the elements are next to each other. Linear data structures have all the data at a single level so that all data can be traversed into a single run. Linear data structures are easy to implement as all the data is stored in a linear manner. Linked list, stack, queue, array, and hashmap are examples of linear data structures. Linear data structures are used mainly to develop software.
Non-Linear Data Structure
This data structures is a bit complex, as the data is connected to the next, previous and more elements. Non-linear data structures store data at multiple levels in a non-linear way. Compared to linear data structures, non-linear data structures are difficult to implement. Trees, graphs, and hashmaps are examples of non-linear data structures. Non-linear data structures are mainly used in AI and image processing.
Now that you have a fair understanding of linear and non-linear data structures, let’s dive into a linear data structure type, linked lists.
What is a Linked List?
A linked list is one of the most preferred data structures for handling dynamic data. It is a data structure that stores data in the form of a node. There are two fields in each node; one has data, and the second has an address that keeps a reference to the next node.
A linked list is a data structure where elements are linked using pointers rather than being stored at a contiguous location. In linked lists, a series of connected nodes are formed. The data and the address of the next node is stored in each node. A linked list looks like a chain of nodes, as each node contains a data field and a link to the next node in the list.
Types of Linked Lists
Single Linked List
Each node contains a reference to the next node in the sequence in a single linked list. In other words, every node in a single linked list stores the address or reference of the next node in the list. Likewise, the last node has the next address or reference as NULL.
Double Linked List
A double linked list has references to both the next and previous node. Doubly linked lists allow traversal in both forward and backward directions. However, backward referencing requires additional memory.
Circular Linked List
A circular linked list points the last node back to the head node. This creates a circular structure that can be either singly or doubly linked.
Circular Doubly Linked List
In this type of linked list, each node has two links that connect it to the previous node and the next node.
Header Linked List (in C)
A list that has a header node is called the header linked list. A header node is a special node found at the beginning of the list.
There are two types of header linked lists:
- Grounded Header Linked List: In this list, the last node contains the NULL pointer.
- Circular Header Linked List: In this list, the last node points back to the header node.
Musd Read: What are the various types of databases?
Operations on Linked Lists
Insertion: This operation can be performed at the beginning, end, or any position within the list. You must adjust the existing nodes’ pointers to maintain the proper sequence when adding a new node to a linked list.
Example code to insert at the beginning of the linked list:
void insertatbeg()
{
struct node *NewNode;
int item;
NewNode = (struct node *) malloc(sizeof(struct node *));
if(NewNode == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
NewNode->data = item;
NewNode->next = start;
start = NewNode;
printf("\nNode inserted");
}
}
Here is an example code to insert at the end of the linked list:
void insertatend()
{
struct node *NewNode,*temp;
int item;
NewNode = (struct node*)malloc(sizeof(struct node));
if(NewNode == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
NewNode->data = item;
if(start == NULL)
{
NewNode -> next = NULL;
start = NewNode;
printf("\nNode inserted");
}
else
{
temp = start;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = NewNode;
NewNode->next = NULL;
printf("\nNode inserted");
}
}
}
Example code to insert in the middle of a linked list:
void insertmiddle()
{
int i,position,item;
struct node *NewNode, *temp;
NewNode = (struct node *) malloc (sizeof(struct node));
if(NewNode == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
NewNode-> data = item;
printf("\n Enter the location after which you want to insert an element ");
scanf("\n%d",&position);
temp=start;
for(i=0;i<position;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\can't insert\n");
return;
}
}
NewNode ->next = temp ->next;
temp ->next = NewNode;
printf("\nNode inserted");
}
}
Deletion: This operation can also be performed at the beginning, end, or any position within the list. To remove a node from a linked list, the pointers of the neighboring nodes must be adjusted to bridge the gap left by the deleted node.
Here is an example code to delete from the beginning of a linked list:
void deleteatbeg()
{
struct node *NewNode;
if(start == NULL)
{
printf("\nList is empty\n");
}
else
{
NewNode = start;
start = NewNode->next;
free(NewNode);
printf("\nNode deleted from the beginning\n");
}
}
Here is a code to delete from the middle of a linked list:
void deletemiddle()
{
struct node *NewNode,*NewNode1;
int position,i;
printf("\n what location of the node \n");
scanf("%d",&position);
NewNode=start;
for(i=0;i<position;i++)
{
NewNode1 = NewNode;
NewNode = NewNode->next;
if(NewNode == NULL)
{
printf("\nCan't delete");
return;
}
}
NewNode1 ->next = NewNode ->next;
free(NewNode);
printf("\nDeleted node %d ",position+1);
}
A code to delete from the end of a linked list:
void deleteatend()
{
struct node *NewNode,*NewNode1;
if(start == NULL)
{
printf("\list is empty");
}
else if(start -> next == NULL)
{
start = NULL;
free(NewNode);
printf("\n node of the list deleted\n");
}
else
{
NewNode = start;
while(NewNode->next != NULL)
{
NewNode1 = NewNode;
NewNode = NewNode ->next;
}
NewNode1->next = NULL;
free(NewNode);
printf("\nDeleted Node from the last\n");
}
}
Searching: In this operation, the list from the head node is traversed until the value is found or the end of the list is reached.
Here is a code to search for an element in a linked list:
void search()
{
struct node *NewNode;
int item,i=0,flag;
NewNode = start;
if(NewNode == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter an item which you want to search\n");
scanf("%d",&item);
while (NewNode!=NULL)
{
if(NewNode->data == item)
{
printf("item found at position%d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
NewNode = NewNode -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
}
Traversal: This operation displays all the nodes in the linked list. If the temp is null, it indicates that all the nodes have been traversed. It means that you have reached the end of the linked list to get out from the while loop.
struct node * temp = start;
printf(“\n list empty are-”);
while (temp!= NULL)
{
printf(‘%d “, temp -> data)
temp=temp -> next;
}
Advantages and Disadvantages of Linked Lists
| Advantages of Linked Lists | Disadvantages of Linked Lists |
|---|---|
| Dynamic Size As the memory is allocated at runtime, linked lists can grow or shrink dynamically. | Random Access Specific code can be reached only through traversal. Linked lists don’t allow direct access to elements by index. |
| Insertion and Deletion Linked lists efficiently add or delete elements, especially for large lists. | Extra Memory To store pointers, linked lists take additional memory compared to arrays. |
| Flexibility There is no need for a contiguous block of memory to identify and modify a linked list. |
Applications of Linked Lists in the Real World
Linked lists are dynamic and efficient and find applications in many real-world scenarios, some of which are:
GPS navigation systems
You can use linked lists to store and manage a list of locations and routes. Double linked lists represent paths or routes between locations. This helps users using navigation systems easily navigate to their destination.
Robotics
Control systems for robots are implemented using linked lists. It allows robots to navigate and interact with their environment.
Image viewer
We use the ‘next’ button to go to the next image. However, images are not stored in a contiguous memory location. A linked list allows us to scroll through the previous and next images in the image viewer on the computer.
Music Player
Music player uses linked lists to link the the previous and next songs in the same way as images in the image viewer.
Web Browser History
A double linked list allows us to go to a previous web page and again move to the next one in a web browser while moving through web pages.
Undo Function
A double linked list can be used in Photoshop and Word documents to implement the undo function. Each change made in a Word document or the image file is saved as nodes in a doubly linked list.
Speech Recognition
In speech recognition software, each possible pronunciation is represented as a node in the list. Linked lists are used to represent the possible phonetic pronunciations of a word.
Simulation of Physical Systems
Physical systems simulation is done with the help of linked lists. Each element in the list represents a discrete point in time and the state of the system at that time.
Don't miss out on your chance to work with the best!
Apply for top job opportunities today!
Conclusion
A clear understanding of fundamental programming concepts like linear and non-data structures is crucial for any programmer. Arrays, linked lists, graphs, trees, stacks, and queues are data structures that help programmers handle dynamic data efficiently. In this blog, we looked at linked lists, a linear data structure, as a fundamental concept in computer programming. Linked lists help programmers organize and store data so that it can be accessed, manipulated, and retrieved efficiently. However, the knowledge of linked lists is not only theoretical but also has practical, real-world applications, ranging from GPS navigation systems and robotics to image viewers, music players, web browser history, and more. The knowledge of linked lists, hence, serves as a foundational skill for any programmer.
FAQs
Data structures organize data efficiently and help computers to run the code faster. Choosing the right data structure helps programmers run code smoothly.
Data structures and algorithms are fundamental concepts and should be understood deeply. However, it is important to use these concepts with other programming essentials.
A full stack developer should have a strong knowledge of data structures, as they are the foundational blocks of software development.
Yes. Data structures help you with efficient data processing, storage, and retrieval.
Take control of your career and land your dream job!
Sign up and start applying for the best opportunities!
