Question

[C++] Create three functions for a singly linked list:

- Function 1: Insert a string into the linked list

- Function 1: Insert a node after a given node (Node* curNodeptr, Node* newNodePtr)

- Function 2: Delete the node passed to it by a pointer, it will take in the head and curPtr '(Node*, Node*)'

struct Node{

string data;

Node *next;

};

Answer 1

Program for singly linked list in c++:

#include <bits/stdc++.h>
#include<string>
using namespace std;
  
// A linked list node
class Node
{
public:
string data;
Node *next;
};
  
/* Given a reference (pointer to pointer)
to the head of a list and an int, inserts
a new node on the front of the list. */
void push(Node** head_ref, string new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
  
/* 2. put in the data */
new_node->data = new_data;
  
/* 3. Make next of new node as head */
new_node->next = (*head_ref);
  
/* 4. move the head to point to the new node */
(*head_ref) = new_node;
}
  
/* Given a node prev_node, insert a new node after the given
prev_node */
void insertAfter(Node* prev_node, string new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL)
{
cout<<"the given previous node cannot be NULL";
return;
}
  
/* 2. allocate new node */
Node* new_node = new Node();
  
/* 3. put in the data */
new_node->data = new_data;
  
/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;
  
/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}
  
void deleteNode(struct Node **head_ref, int position)
{
// If linked list is empty
if (*head_ref == NULL)
return;
  
// Store head node
struct Node* temp = *head_ref;
  
// If head needs to be removed
if (position == 0)
{
*head_ref = temp->next; // Change head
free(temp); // free old head
return;
}
  
// Find previous node of the node to be deleted
for (int i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;
  
// If position is more than number of ndoes
if (temp == NULL || temp->next == NULL)
return;
  
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
struct Node *next = temp->next->next;
  
// Unlink the node from linked list
free(temp->next); // Free memory
  
temp->next = next; // Unlink the deleted node from list
}
  

  
// This function prints contents of
// linked list starting from head
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}
  
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
push(&head, "qwe");
  push(&head, "ewr");
  
push (&head,"vfl");
push(&head,"hjv");
push(&head,"jul");

insertAfter(head->next, "fgh");
  
puts("Created Linked List: ");
printList(head);
deleteNode(&head, 4);
puts("\nLinked List after Deletion at position 4: ");
printList(head);
  
return 0;
}