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 .

Linked List in C

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.

Linked List in C Node

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

  1. Singly Linked Lists
  2. Double Linked Lists
  3. 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:-

  1. Node:- for storing data
  2. 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?

singly linked list in c

Code for Implementing Singly Linked List in C

Run
// 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?

C Circular linked list

Basic Operations on Linked Lists

  • Insertion
  • Deletion
  • Searching
  • Printing

The below program shows all the following –

Run
#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

  1. No restriction of size:  Unlike arrays, we do not have to declare the size of the linked list before creating it.
  2. 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.
  3. 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.
  4. Insertion and Deletion Operation in Linked Lists are pretty easy and less complicated.

Disadvantages of using Linked List

  1. Although insertion and deletion are not difficult tasks in Linked List, searching in Linked List is very difficult.
  2. We cannot use efficient searches like Binary Search.
  3. It takes more space, as it stores the address also.
  4. Linked lists are not cached friendly as arrays are stored in the contiguous format they can be cached easily
  5. 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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

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
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end 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 –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • 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 –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly 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 given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java