Write the following methods for a standard unordered singly linked list. There i
ID: 3724784 • Letter: W
Question
Write the following methods for a standard unordered singly linked list. There is a head pointer, but no tail pointer 7. // inserts the given key into the first position in the list (head) public void insertFirst (int key) // inserts the given key at the end of the list (there is no tail pointer) public void insertLast (int key) // inserts the keyl into the position immediately following the last instance of // key2 if key2 exists in the list. Otherwise, the keyl is inserted at the en of // the list. public void insertafter (int keyl, int key2) // removes the given key from the list if it exists, otherwise does nothing public void delete (int key)Explanation / Answer
/*
* C++ Program to Implement Singly Linked List
*/
#include<iostream>
using namespace std;
/*
* Node Declaration
*/
struct Node
{
int data;
struct Node *next;
}*head;
/*
* Class Declaration
*/
class sList
{
public:
Node* createNode(int);
void insertFirst(int);
void insertAfter(int ,int);
void insertLast(int);
void deleteNode(int);
void display();
sList()
{
head = NULL;
}
};
int main()
{
sList sl;
head = NULL;
sl.insertFirst(1);
sl.insertFirst(2);
sl.insertFirst(3);
sl.insertLast(4);
sl.insertFirst(5);
sl.display();
sl.insertAfter(4,5);
sl.display();
sl.deleteNode(1);
sl.display();
}
/*
* Creating Node
*/
Node *sList::createNode(int value)
{
struct Node *temp, *s;
temp = new(struct Node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->data = value;
temp->next = NULL;
return temp;
}
}
void sList::deleteNode( int key)
{
// Store head node
struct Node* temp =head, *prev;
// If head node itself holds the key to be deleted
if (temp != NULL && temp->data == key)
{
head = temp->next; // Changed head
free(temp); // free old head
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL);
else
{
// Unlink the node from linked list
prev->next = temp->next;
free(temp); // Free memory
}
}
/*
* Inserting element in beginning
*/
void sList::insertFirst(int value)
{
struct Node *temp, *p;
temp = createNode(value);
if (head == NULL)
{
head = temp;
head->next = NULL;
}
else
{
p = head;
head = temp;
head->next = p;
}
cout<<"Element Inserted at beginning"<<endl;
}
/*
* Inserting Node at last
*/
void sList::insertLast(int value)
{
struct Node *temp, *s;
temp = createNode(value);
s = head;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}
/*
* Insertion of node at a given position
*/
void sList::insertAfter(int k,int k2)
{
struct Node *temp, *s;
s = head;
while (s->data!=k && s != NULL)
{
s = s->next;
}
if(s==NULL)
{
cout<<"Key not found"<<endl;
}
else
{
/* 1. allocate new node */
temp = createNode(k2);
if(s->next!=NULL){
/* 4. Make next of new node as next of prev_node */
temp->next = s->next;
/* 5. move the next of prev_node as new_node */
s->next = temp;
}
else{
temp->next = NULL;
s->next = temp;
}
}
}
/*
* Display Elements of a link list
*/
void sList::display()
{
struct Node *temp;
if (head == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = head;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<"NULL"<<endl;
}
Output:-
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.