Linked List
A linked list is a linear data structure that does not store elements in contiguous memory locations, the elements in the linked list are linked using pointers. It is a collection of nodes in which each node stores data and a pointer that links to the next node to form a sequence of nodes.
-> Linked List is a linear data structure which is a combination of Nodes.
-> Nodes contain two parts i.e. data & address.
Representation of a Linked List in C:
A linked list is represented as a pointer to the first node where each node contains:
- Data: Here the actual information is stored.
- Next: Pointer that links to the next node.
Advantages of a Linked List:
- Linked list is dynamic data structure it has memory allocation and de-allocation, which means that memory is only used when needed and not earlier in order to avoid waste.
- In linked list items are arranged in a linear fashion, new items can be inserted or removed as and when needed without affecting other items on the list, which makes these processes efficient.
- Memory is utilized effectively since nodes are created on-demand, which means that memory is not pre-allocated when the system has less load.
- Several linear data structures, like stacks and queues, can be implemented with the help of linked lists.
Disadvantages of a Linked List:
- In a linked list whenever we want to find the element with position n, all the other elements must be visited first, and this could take quite a lot of time.
- In a linked list, there is more memory needed than there is with an array because each node contains some pointer information.
- An operation that involves accessing elements of a linked list is not as simple as that in an array since elements of a linked list do not have indices that would help you jump to a given position directly.
- Reversing a linked list involves more than one level of pointer arrows in a singly linked list is not feasible or efficient.
Applications of Linked Lists:
The following are the applications of linked list:
- Linked list are commonly used to implement stacks and queues.
- It can be used to implement graphs, with the adjacent vertices stored in the nodes of the linked list.
- It can be used in dynamic memory allocation.
- It is used for representing sparse matrices.
- It can be used to store and manipulate polynomials.
- Linked list is used in operating systems to manage task scheduling.
- It is also used in compilers to build a symbol table.
Linked List is of 3 types:
i. Singly Linked List.
ii. Doubly Linked List.
iii. Circular Linked List
In Linked List we can perform various operations such of them are listed below:
a. Insertion of Node
b. Deletion of Nodes
c. Traverse
d. Search
e. Reverse etc.
Here are the detail and explanation about all types of linked list.
#Singly Linked List:
-> A singly linked list is a fundamental data structure in computer science and programming, it consists of nodes where each node contains a data field and a reference to the next node in the node. The last node points to null, indicating the end of the list.
Here is the code in C:
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*) malloc (sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory Allocation Failed!");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL)
{
*head = newNode;
}
else {
newNode->next = *head;
*head = newNode;
}
printf("%d Linked To Head Sucessfully!\n",data);
}
void insertAtPosition(struct Node** head, int data, int position){
struct Node* newNode = createNode(data);
if (position < 0)
{
printf("Invalid Position!");
return.
}
if (position == 0)
{
insertAtHead(head,data);
return;
}
struct Node* temp = *head;
for (int i = 0; i < position -1 && temp != NULL; i++)
{
temp =temp->next;
}
if (temp == NULL)
{
printf("Position Out of Range!\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
printf("%d Linked To Given Position SucessFully!\n",data);
}
void deleteAtHead(struct Node** head){
struct Node* temp = *head;
if (*head == NULL)
{
printf("Node is Empty!");
return;
}
*head = temp -> next;
free(temp);
printf("Node Deleted From Head Sucessfully!\n");
}
void deleteAtPosition(struct Node** head, int position){
if (*head == NULL)
{
printf("Linked List Is Empty!\n");
return;
}
if (position == 0)
{
deleteAtHead(head);
}
struct Node* temp = *head;
for (int i = 0; i < position - 1 && temp != NULL; i++)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("Position Out Of Range!\n");
return;
}
struct Node* next = temp->next->next;
free(temp->next);
temp->next = next;
printf("Node Deleted At Position SucessFully!\n");
return;
}
void reverseLL(struct Node** head){
struct Node* prev = NULL;
struct Node* next = NULL;
struct Node* current = *head;
while (current != NULL)
{
next = current -> next;
current -> next = prev;
prev = current;
current = next;
}
*head = prev;
}
int searchNode(struct Node** head, int k){
struct Node* temp = *head;
while (temp != NULL)
{
if (temp->data == k){
printf("Element Found IN Linked List!");
return 1;
}
temp = temp->next;
}
printf("Element Not Found In Linked List!");
return 0;
}
void traverseLL(struct Node* head) {
struct Node* temp = head;
while (temp!= NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main(){
struct Node* head = NULL;
int size;
printf("Enter The Size Of Linked List: ");
scanf("%d", &size);
//inserting value at the head by user:
printf("Enter %d Elements To get Linked : ",size);
for (int i = 0; i < size; i++)
{
int data;
scanf("%d", &data);
insertAtHead(&head, data);
}
insertAtPosition(&head, 7, 1);
traverseLL(head);
//deletion at head & given position
deleteAtHead(&head);
deleteAtPosition(&head, 1);
//traversing LL after performing some deletion at LL
traverseLL(head);
//reversing given linked list
reverseLL(&head);
printf("Reversed LL: ");
//after reversing LL get traversed again!
traverseLL(head);
//performing search operation in LL!
searchNode(&head, 5);
return 0;
}
Output Will be Like:
Comments
Post a Comment