Scribd
Upload
25 views17 pages

Linked List

The document contains C programs for various linked list operations including inserting nodes at the beginning and end, searching for a node, deleting a node, inserting at a specific position, and reversing a linked list. Each section provides code snippets and explanations for the respective operations. The main function demonstrates the usage of these linked list operations.

Uploaded by

priyashreebanerjee2105
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views17 pages

Linked List

The document contains C programs for various linked list operations including inserting nodes at the beginning and end, searching for a node, deleting a node, inserting at a specific position, and reversing a linked list. Each section provides code snippets and explanations for the respective operations. The main function demonstrates the usage of these linked list operations.

Uploaded by

priyashreebanerjee2105
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

------------------------------------------------------------------

-----------------------------------------
Program to insert a node at the beginning of linked list
------------------------------------------------------------------
-------------------------------------------
------------------------------------------------------------------
-------------------------------------------

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

void addFirst(struct node **head, int val)


{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;

newNode->next = *head;

*head = newNode;
}

void printList(struct node *head)


{
struct node *temp = head;

//iterate the entire linked list and print the data


while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
struct node *head = NULL;
addFirst(&head,10);
addFirst(&head,20);
addFirst(&head,30);

printList(head);

return 0;
}
------------------------------------------------------------------------------------------------------------------------

Implementation of inserting a node at the end of a linked


list
--------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

void addLast(struct node **head, int val)


{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;

//if head is NULL, it is an empty list


if(*head == NULL)
*head = newNode;
//Otherwise, find the last node and add the newNode
else
{
struct node *lastNode = *head;

//last node's next address will be NULL.


while(lastNode->next != NULL)
{
lastNode = lastNode->next;
}
//add the newNode at the end of the linked list
lastNode->next = newNode;
}

void printList(struct node *head)


{
struct node *temp = head;

//iterate the entire linked list and print the data


while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
struct node *head = NULL;

addLast(&head,10);
addLast(&head,20);
addLast(&head,30);

printList(head);

return 0;
}

--------------------------------------------------------------------------

Searching a node in singly linked list


-----------------------------------------------------------------------------------
-----------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

void addLast(struct node **head, int val)


{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;

//if head is NULL, it is an empty list


if(*head == NULL)
*head = newNode;
//Otherwise, find the last node and add the newNode
else
{
struct node *lastNode = *head;

//last node's next address will be NULL.


while(lastNode->next != NULL)
{
lastNode = lastNode->next;
}

//add the newNode at the end of the linked list


lastNode->next = newNode;
}

int searchNode(struct node *head,int key)


{
struct node *temp = head;

//iterate the entire linked list and print the data


while(temp != NULL)
{
//key found return 1.
if(temp->data == key)
return 1;
temp = temp->next;
}
//key not found
return -1;
}

int main()
{
struct node *head = NULL;
addLast(&head,10);
addLast(&head,20);
addLast(&head,30);

//change the key and try it yourself.


if(searchNode(head,20) == 1)
printf("Search Found\n");
else
printf("Search Not Found\n");

return 0;
}

--------------------------------------------------------------------------

Deleting a node in linked list


--------------------------------------------------------------
------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

void addLast(struct node **head, int val)


{
//create a new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;

//if head is NULL, it is an empty list


if(*head == NULL)
*head = newNode;
//Otherwise, find the last node and add the newNode
else
{
struct node *lastNode = *head;

//last node's next address will be NULL.


while(lastNode->next != NULL)
{
lastNode = lastNode->next;
}

//add the newNode at the end of the linked list


lastNode->next = newNode;
}

void deleteNode(struct node **head, int key)


{
//temp is used to freeing the memory
struct node *temp;

//key found on the head node.


//move to head node to the next and free the head.
if((*head)->data == key)
{
temp = *head; //backup to free the memory
*head = (*head)->next;
free(temp);
}
else
{
struct node *current = *head;
while(current->next != NULL)
{
//if yes, we need to delete the current->next node
if(current->next->data == key)
{
temp = current->next;
//node will be disconnected from the linked list.
current->next = current->next->next;
free(temp);
break;
}
//Otherwise, move the current node and proceed
else
current = current->next;
}
}
}
void printList(struct node *head)
{
struct node *temp = head;

//iterate the entire linked list and print the data


while(temp != NULL)
{
printf("%d ->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
struct node *head = NULL;

addLast(&head,10);
addLast(&head,20);
addLast(&head,30);
printf("Linked List Elements:\n");
printList(head);

//delete first node


deleteNode(&head,10);
printf("Deleted 10. The New Linked List:\n");
printList(head);

//delete last node


deleteNode(&head,30);
printf("Deleted 30. The New Linked List:\n");
printList(head);

//delete 20
deleteNode(&head,20);
printf("Deleted 20. The New Linked List:\n");
printList(head);

return 0;
}

-----------------------------------------------------------------------------------------------------------------------
Insert Any position
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
/Linked list insertion at specific position in C
#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *next;
};

// required for insertAfter


int getCurrSize (struct Node *node)
{
int size = 0;

while (node != NULL)


{
node = node->next;
size++;
}
return size;
}

//function to insert after nth node


void insertPosition (int pos, int data, struct Node **head)
{
int size = getCurrSize (*head);

struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));


newNode->data = data;
newNode->next = NULL;
// Can't insert if position to insert is greater than size of Linked List
// can insert after negative pos
if (pos < 0 || pos > size)
printf ("Invalid position to insert\n");

// inserting first node


else if (pos == 0)
{
newNode->next = *head;
*head = newNode;
}

else
{
// temp used to traverse the Linked List
struct Node *temp = *head;

// traverse till the nth node


while (--pos)
temp = temp->next;

// assign newNode's next to nth node's next


newNode->next = temp->next;
// assign nth node's next to this new node
temp->next = newNode;
// newNode inserted b/w 3rd and 4th node
}
}

void display (struct Node *node)


{

printf ("Linked List : ");

// as linked list will end when Node is Null


while (node != NULL)
{
printf ("%d ", node->data);
node = node->next;
}
printf ("\n");
}

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);
//Inserts data: 15 after the 1st node
insertPosition (1, 15, &head);

//Inserts data: 25 after the 3rd node


insertPosition (3, 25, &head);

//Inserts data: 35 after the 5th node


insertPosition (5, 35, &head);

//Inserts data: 25 after the 7th node


insertPosition (7, 45, &head);

display (head);

// Invalid: can't insert after -2 pos


insertPosition (-2, 100, &head);

// Invalid: Current size 8, trying to enter after 10th pos


insertPosition (10, 200, &head);

return 0;
}

------------------------------------------------------------------------------------------------------------------------
Reverse Link List
------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------
/**
* C program to reverse a Singly Linked List
*/

#include <stdio.h>
#include <stdlib.h>
/* Structure of a node */
struct node {
int data; //Data part
struct node *next; //Address part
}*head;

/* Functions used in the program */


void createList(int n);
void reverseList();
void displayList();

int main()
{
int n, choice;

/*
* Create a singly linked list of n nodes
*/
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);

printf("\nData in the list \n");


displayList();

/*
* Reverse the list
*/
printf("\nPress 1 to reverse the order of singly linked list\n");
scanf("%d", &choice);
if(choice == 1)
{
reverseList();
}

printf("\nData in the list\n");


displayList();

return 0;
}

/*
* Create a list of n nodes
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;

if(n <= 0)
{
printf("List size must be greater than zero.\n");
return;
}

head = (struct node *)malloc(sizeof(struct node));

/*
* If unable to allocate memory for head node
*/
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
/*
* Read data of node from the user
*/
printf("Enter the data of node 1: ");
scanf("%d", &data);

head->data = data; // Link the data field with data


head->next = NULL; // Link the address field to NULL

temp = head;

/*
* Create n nodes and adds to linked list
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));

/* If memory is not allocated for newNode */


if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("Enter the data of node %d: ", i);
scanf("%d", &data);

newNode->data = data; // Link the data field of newNode with data


newNode->next = NULL; // Link the address field of newNode with NULL

temp->next = newNode; // Link previous node i.e. temp to the newNode


temp = temp->next;
}
}

printf("SINGLY LINKED LIST CREATED SUCCESSFULLY\n");


}
}

/*
* Reverse the order of nodes of a singly linked list
*/
void reverseList()
{
struct node *prevNode, *curNode;

if(head != NULL)
{
prevNode = head;
curNode = head->next;
head = head->next;

prevNode->next = NULL; // Make first node as last node

while(head != NULL)
{
head = head->next;
curNode->next = prevNode;

prevNode = curNode;
curNode = head;
}

head = prevNode; // Make last node as head

printf("SUCCESSFULLY REVERSED LIST\n");


}
}

/*
* Display entire list
*/
void displayList()
{
struct node *temp;

/*
* If the list is empty i.e. head = NULL
*/
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while(temp != NULL)
{
printf("Data = %d\n", temp->data); // Print the data of current node
temp = temp->next; // Move to next node
}
}
}

You might also like