#include <iostream>
using namespace std;
struct Node {
int info;
Node* next;
};
typedef Node* PNode;
typedef Node* LinkedList;
void initializeList(LinkedList& list) {
list = NULL;
}
bool IsEmpty (LinkedList list){
return(list == NULL);
}
void InsertBegin(LinkedList &list, int K){
PNode Q = new Node;
Q-> info = K;
if(list == NULL){
Q->next = NULL;
list = Q;
}
else{
Q->next = list;
list = Q;
}
}
PNode SearchNode(LinkedList& list, int K){
PNode P = list;
while(P != 0){
if(P->info==K)
return P;
}
return 0;
}
PNode InsertAfter(LinkedList& list, PNode P, int K){
PNode Q = new Node;
Q->info = K;
if(list == NULL){
Q->next = NULL;
list = Q;
}
else {
if (P==NULL) return NULL;
Q->next = P->next;
P->next = Q;
}
return Q;
}
PNode InsertBefore(LinkedList& list, PNode P, int K){
PNode Q = new Node;
Q->info = K;
if(list==NULL){
list = Q;
Q->next = NULL;
return Q;
}
else {
if(P==NULL) return NULL;
Q->info = P->info;
P->info=K;
Q->next = P->next;
P->next = Q;
}
return P;
}
void DeleteNode (LinkedList& list, PNode P){
if (list == NULL) cout << "NULL"<<endl;
else {
P = list;
list = list->next;
delete P;
}
}
void DeleteValue(LinkedList& list, int K) {
PNode P = list;
PNode prev = NULL;
while (P != NULL && P->info == K) {
// Delete the node at the beginning
list = P->next;
delete P;
P = list;
}
while (P != NULL) {
while (P != NULL && P->info != K) {
prev = P;
P = P->next;
}
if (P == NULL) {
return; // Element not found
}
// Unlink the node with value K
prev->next = P->next;
delete P;
P = prev->next;
}
}
float average(LinkedList list){
float avg = 0;
int count = 0;
PNode P = list;
while(P != NULL){
avg += P->info;
P = P->next;
count++;
}
return avg/count;
}
void display(LinkedList list){
PNode P = list;
while(P != NULL){
cout << P->info << " ";
P = P->next;
}
cout <<endl;
}
int main(){
LinkedList N;
initializeList (N);
InsertBegin (N, 23);
InsertBegin (N,24);
InsertBegin (N,25);
InsertBegin (N,24);
InsertBegin (N,26);
InsertBegin (N,29);
InsertBegin (N,69);
InsertBegin (N,24);
display(N);
cout << average(N) <<endl;
// Delete nodes with value 24
int valueToDelete = 24;
DeleteValue(N, valueToDelete);
cout << "After deleting nodes with value " << valueToDelete << ": ";
display(N);
//PNode nodeToDelete = SearchNode(N, 23);
DeleteNode(N, SearchNode(N,23));
display (N);
cout << average(N) <<endl;
int valueToInsertBefore = 24;
PNode nodeToInsertBefore = SearchNode(N, 29);
int newValueBefore = 25;
InsertBefore(N, nodeToInsertBefore, newValueBefore);
cout << "After inserting " << newValueBefore << " before " << "29" << ": ";
display(N);
int valueToInsertAfter = 24;
//PNode nodeToInsertAfter = SearchNode(N, valueToInsertAfter);
int newValueAfter = 49;
//InsertAfter(N, nodeToInsertAfter, newValueAfter);
cout << "After inserting " << newValueAfter << " after " << valueToInsertAfter << ": ";
display(N);
}