Linked List in C
Linked Lists in C Programming Language
Linked List in C is a linear type of data structure, which has some major advantages over arrays and other linear data structures.
Eventhough Linked List are linear Data Strucutres, the nodes of a Linked Lists need not be stored in a contiguous manner and can be scatter in memory. Linked is constructed of two parts node & pointer .
Why do we prefer Linked Lists ?
Linked Lists are a preferred over data structures if you want to store large amount of data. Since, insertion & deletion operations are easy to code and have lesser time complexity.
What do Linked Lists Consists
For constructing a Linked List in C. We use a user-defined data type.
- We make a structure in C for using Linked List. We design a user-defined struct data type.
- That contains the following –
- Data: A data type, for storing the desired data
- Next Pointer: Pointer variable for storing the address of the next node in the Linked List.
Syntax for creating a node in Linked List in C
struct Node { int data; struct Node* next; };
The above code will create a new node in a Linked List which will store an integer datatype.
Types of Linked Lists
There are three type of linked lists in C
- Singly Linked Lists
- Double Linked Lists
- Circular Linked Lists
Singly Linked List
Singly linked List is used for storing data in an easy and efficient way. It comprises of two parts:-
- Node:- for storing data
- Pointer:- for storing the address of the next node
How is a Singly Linked List constructed?
For constructing a singly linked list, structure keyword (struct) is used.
Syntax:-
struct Node { int Data; Struct Node *next; };
What is Singly Linked List?
Code for Implementing Singly Linked List in C
// Linked List in C Implementation code #include <stdio.h> #include <stdlib.h> //stdlib is included because we will be using 'malloc' // creating a node in linked list struct Node { int data; struct Node *next; // Pointer pointing towards next node }; //function to print the linked list void display (struct Node *node) { while (node != NULL) { printf (" %d ", node->data); node = node->next; } } // main function int main () { //creating 4 pointers of type struct Node //So these can point to address of struct type variable struct Node *head = NULL; struct Node *node2 = NULL; struct Node *node3 = NULL; struct Node *node4 = NULL; // allocate 3 nodes in the heap head = (struct Node *) malloc (sizeof (struct Node)); node2 = (struct Node *) malloc (sizeof (struct Node)); node3 = (struct Node *) malloc (sizeof (struct Node)); node4 = (struct Node *) malloc (sizeof (struct Node)); head->data = 10; // data set for head node head->next = node2; // next pointer assigned to address of node2 node2->data = 20; node2->next = node3; node3->data = 30; node3->next = node4; node4->data = 40; node4->next = NULL; display (head); return 0; }
Output 10 20 30 40
Doubly Linked List in C
A unique Data Structure type is where a chain of nodes are connected using pointers. Each individual node comprises of three components, Data, Previous Pointer, and Next Pointer.
Syntax for creating a node:-
struct Node { int data; struct Node *next; struct Node *prev; };
What is Doubly Linked List?
Circular Linked List in C
Circular Linked List connects elements together with pointers, such that each node will contain a data value and address to the next node in the link.
Syntax for Singly Circular Linked List:-
struct Node { int data; struct Node *next; }
What is Circular Linked List?
Basic Operations on Linked Lists
- Insertion
- Deletion
- Searching
- Printing
The below program shows all the following –
#include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next; }; void insertFirst (struct Node **head, int data) { // dynamically create memory for this newNode struct Node *newNode = (struct Node *) malloc (sizeof (struct Node)); // assign data value newNode->data = data; // change the next node of this newNode // to current head of Linked List newNode->next = *head; //re-assign head to this newNode *head = newNode; } void deleteFirst (struct Node **head) { struct Node *temp = *head; // if there are no nodes in Linked List can't delete if (*head == NULL) { printf ("Linked List Empty, nothing to delete"); return; } // move head to next node *head = (*head)->next; printf ("\n%d deleted\n\n", temp->data); free (temp); } void display (struct Node *node) { printf ("Linked List : \n"); // as linked list will end when Node is Null while (node != NULL) { printf ("%d ", node->data); node = node->next; } printf ("\n\n"); } void search (struct Node *node, int key) { int pos = 1; int flag = 0; while (node != NULL) { if (node->data == key) { flag = 1; break; } node = node->next; pos++; } if (flag) printf ("%d present at %d position\n", key, pos); else printf ("%d not present\n"); } // Note by default insertion/deletion happens at starting node // of Linked List int main () { struct Node *head = NULL; // Need '&' i.e. address as we need to change head insertFirst (&head, 50); insertFirst (&head, 40); insertFirst (&head, 30); insertFirst (&head, 20); insertFirst (&head, 10); // no need of '&' as we are not changing head just displaying Linked List display (head); search (head, 30); search (head, 100); deleteFirst (&head); display (head); return 0; }
Output
Linked List : 10 20 30 40 50 30 present at 3 position 100 not present 10 deleted Linked List : 20 30 40 50
Advantages of using Linked List
- No restriction of size: Unlike arrays, we do not have to declare the size of the linked list before creating it.
- No memory wastage: Unlike arrays, in Linked List, we can add or delete nodes and their memory dynamically, however in arrays, the whole initialized memory is consumed even if we are using the first few indexes to store values.
- Linked List does not need contiguous memory: If one node has an address of 1000 then the next node may have the address 2000, we can simply connect these non-contiguous memories using pointers.
- Insertion and Deletion Operation in Linked Lists are pretty easy and less complicated.
Disadvantages of using Linked List
- Although insertion and deletion are not difficult tasks in Linked List, searching in Linked List is very difficult.
- We cannot use efficient searches like Binary Search.
- It takes more space, as it stores the address also.
- Linked lists are not cached friendly as arrays are stored in the contiguous format they can be cached easily
- Loss of data threat is there, if we lose one pointer location the rest of the linked list can’t be accessed.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Login/Signup to comment