Write a program in C to implement a Singly Linked List with the following operations:Insert Node at beginning insert Node at End Delete Node at beginning delete Node at End Display the Nodes Data Count the Nodes
Answers
Answer:
Create a new node and make sure that the address part of the new node points to NULL i.e. newNode->next=NULL.
Traverse to the last node of the linked list and connect the last node of the list with the new node, i.e. last node will now point to new node.
Skip to content
Search for:
C program to insert node at the end of Singly Linked List
September 24, 2015PankajData StructuresC, Data Structures, Linked List, Program, Singly Linked List
Write a C program to create a list of n nodes and insert a new node at the end of the Singly Linked List. How to insert a new node at the end of a Singly Linked List in C. Algorithm to insert node at the end of singly linked list. Steps to insert a new node at the end of singly linked list.
Singly linked list
Required knowledge
Basic C programming, Functions, Singly Linked List, Dynamic memory allocation
Algorithm to insert node at the end of Singly linked list
Algorithm to insert node at the end of a Singly Linked List
Begin:
createSinglyLinkedList (head)
alloc (newNode)
If (newNode == NULL) then
write ('Unable to allocate memory')
End if
Else then
read (data)
newNode.data ← data
newNode.next ← NULL
temp ← head
While (temp.next != NULL) do
temp ← temp.next
End while
temp.next ← newNode
End else
END
Answer:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//displaying the list
void printList() {
struct node *ptr = head;
printf("\n[ ");
//starting from the beginning
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//inserting link at the first location
void insertFirst(int key, int data) {
//createing a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//pointing it to old first node
link->next = head;
//pointing first to new first node
head = link;
}
//deleting first item
struct node* deleteFirst() {
//saving reference to first link
struct node *tempLink = head;
//marking next to first link as first
head = head->next;
//returning the deleted link
return tempLink;
}
//is list null
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
struct node *current;
for(current = head; current != NULL; current = current->next) {
length++;
}
return length;
}
//finding a link with given key
struct node* find(int key) {
//starting from the first link
struct node* current = head;
//if list is null
if(head == NULL) {
return NULL;
}
//navigating through list
while(current->key != key) {
//if it is in last node
if(current->next == NULL) {
return NULL;
} else {
//go to the next link
current = current->next;
}
}
//if data found then return the current Link
return current;
}
//deleteing a link with given key
struct node* delete(int key) {
//starting from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is null
if(head == NULL) {
return NULL;
}
//navigating through list
while(current->key != key) {
//if it is in last node
if(current->next == NULL) {
return NULL;
} else {
//storing reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//finding a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypassing the current link
previous->next = current->next;
}
return current;
}
void sort() {
int i, j, k, tempKey, tempData;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head;
next = head->next;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data;
current->data = next->data;
next->data = tempData;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//printing list
printList();
while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nRestored List: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
printf("\n");
sort();
printf("List after sorting the data: ");
printList();
reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
#SPJ2