Scribd
Upload
49 views55 pages

Programs

Uploaded by

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

Programs

Uploaded by

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

Single LinkedList

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int val) {
data = val;
next = NULL;
}
};

class LinkedList {
private:
Node* head;

public:
LinkedList() {
head = NULL;
}

void insertAtStart(int val) {


Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}

void insertAtEnd(int val) {


Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

void insertAtIndex(int prevData, int newData) {


Node* newNode = new Node(newData);
Node* temp = head;
while (temp != NULL && temp->data != prevData) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Node with previous data not found." << endl;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}

void deleteFront() {
if (head == NULL) return;
Node* temp = head;
head = head->next;
delete temp;
}

void deleteLast() {
if (head == NULL) return;
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* prev = NULL;
Node* temp = head;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
delete temp;
}

void reverseList() {
Node* temp = head;
Node* prev = NULL;
while (temp != NULL) {
Node* next = temp->next;
temp->next = prev;
prev = temp;
temp = next;
}
head = prev;
}

bool searchElement(int item) {


Node* temp = head;
while (temp != NULL) {
if (temp->data == item) {
return true;
}
temp = temp->next;
}
return false;
}
int lengthList() {
int count = 0;
Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
cout << "Length of the list is: " << count << endl;
return count;
}

void displayListBasedOnLength() {
int length = lengthList();
if (length % 2 == 0)
{
cout<<"Number of nodes are even:"<<endl;
display();
} else {
cout<<"Number of nodes are odd:"<<endl;
reverseList();
display();

//to restore the original list we are reversing the list


reverseList();
}
}
int calculateSum() {
int sum = 0;
Node* temp = head;
while (temp != NULL) {
sum += temp->data;
temp = temp->next;
}
return sum;
}

void findHighestAndSecondHighest(int &highest, int &secondHighest) {


highest = 0;
secondHighest = 0;

Node* temp = head;


while (temp != NULL) {
if (temp->data > highest) {
secondHighest = highest;
highest = temp->data;
} else if (temp->data > secondHighest && temp->data != highest) {
secondHighest = temp->data;
}
temp = temp->next;
}
}
void display() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
LinkedList list;

[Link](2);
[Link](5);
[Link](6);

[Link](3);
[Link](4);

cout << "The total number of elements in the LinkedList:" << endl;
[Link]();
cout<<endl;
[Link](3, 7);
cout << "Insertion at given index in the linked list:" << endl;
[Link]();
cout<<endl;

bool found = [Link](4);


cout << (found ? "Found" : "Not found") << endl;
cout<<endl;

[Link]();
cout<<endl;

[Link]();
cout << "The elements in the linked list after reversal:" << endl;
[Link]();
cout<<endl;

[Link]();
cout<<endl;

[Link]();
cout << "Delete the element from the start of the linked list:" << endl;
[Link]();
cout<<endl;

[Link]();
cout << "Delete the element from the end of the linked list:" << endl;
[Link]();
cout<<endl;

int totalSum = [Link]();


cout << "Total sum: " << totalSum << endl;
cout<<endl;

/*int maxNumber = [Link]();


cout << "The greatest number in the list: " << maxNumber << endl;
cout<<endl;

int secondMax = [Link]();


cout << "The second highest value in the linked list: " << secondMax <<
endl;*/

int highest, secondHighest;


[Link](highest, secondHighest);

cout << "Highest: " << highest << endl;


cout << "Second Highest: " << secondHighest << endl;
return 0;
}

DubleLinked List
#include <iostream>
#include <climits>
using namespace std;

class Node {
public:
int data;
Node* next;
Node* prev;

Node(int val) {
data = val;
next = NULL;
prev = NULL;
}
};

class DoubleLinkedList {
public:
Node* head;
Node* tail;

DoubleLinkedList() {
head = NULL;
tail = NULL;
}

void insertAtBeginning(int val) {


Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}

void insertAtEnd(int val) {


Node* newNode = new Node(val);
if (tail == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}

void deleteAtBeginning() {
if (head == NULL) return;
Node* temp = head;
head = head->next;
if (head != NULL) head->prev = NULL;
else tail = NULL;
delete temp;
}

void deleteAtEnd() {
if (tail == NULL) return;
Node* temp = tail;
tail = tail->prev;
if (tail != NULL) tail->next = NULL;
else head = NULL;
delete temp;
}

int length() {
int len = 0;
Node* temp = head;
while (temp != NULL) {
len++;
temp = temp->next;
}
return len;
}

void display() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

void displayReverse() {
Node* temp = tail;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}

void displayBasedOnLength() {
int len = length();
if (len % 2 == 0) {
display();
} else {
displayReverse();
}
}
void findHighestAndSecondHighest(int &highest, int &secondHighest) {
highest = INT_MIN;
secondHighest = INT_MIN;

Node* temp = head;


while (temp != NULL) {
if (temp->data > highest) {
secondHighest = highest;
highest = temp->data;
} else if (temp->data > secondHighest && temp->data != highest) {
secondHighest = temp->data;
}
temp = temp->next;
}
}
};

int main() {
DoubleLinkedList dolist;
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);
[Link](60);
cout << "Display list in forward order:" << endl;
[Link]();

cout << "Display list in reverse order:" << endl;


[Link]();

cout << "Delete node at beginning:" << endl;


[Link]();
[Link]();

cout << "Delete node at end:" << endl;


[Link]();
[Link]();

cout << "Display list based on length (even -> forward, odd -> reverse):" <<
endl;
[Link]();

int highest, secondHighest;


[Link](highest, secondHighest);
cout << "Highest: " << highest << endl;
cout << "Second Highest: " << secondHighest << endl;

return 0;
}
Circular Linkedlist
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int val) {
data = val;
next = NULL;
}
};

class CircularLinkedList {
public:
Node* head;

CircularLinkedList() {
head = NULL;
}

void insertAtEnd(int val) {


Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}

void insertAtBeginning(int val) {


Node* newNode = new Node(val);
if (head == NULL) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;
}
}

void addToEmpty(int val) {


if (head != NULL) {
cout << "List is not empty. Cannot use addToEmpty function." << endl;
return;
}
Node* newNode = new Node(val);
head = newNode;
head->next = head;
}

void deleteFirst() {
if (head == NULL) {
cout << "List is empty. Nothing to delete." << endl;
return;
}
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
if (temp == head) {
delete head;
head = NULL;
} else {
Node* toDelete = head;
temp->next = head->next;
head = head->next;
delete toDelete;
}
}

int countNodes() {
if (head == NULL) {
return 0;
}
int count = 0;
Node* temp = head;
do {
count++;
temp = temp->next;
} while (temp != head);
return count;
}

int findGreatest() {
if (head == NULL) {
cout << "List is empty." << endl;
return -1;
}
int max_value = head->data;
Node* temp = head;
do {
if (temp->data > max_value) {
max_value = temp->data;
}
temp = temp->next;
} while (temp != head);
return max_value;
}

void display() {
if (head == NULL) {
cout << "List is empty." << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}

void displayReverse(Node* node) {


if (node == NULL) return;
Node* temp = node->next;
if (temp != head) {
displayReverse(temp);
}
cout << node->data << " ";
}

void displayReverse() {
if (head == NULL) {
cout << "List is empty." << endl;
return;
}
displayReverse(head);
cout << endl;
}

void displayBasedOnCount() {
int nodeCount = countNodes();
if (nodeCount % 2 == 0) {
cout << "Displaying list in forward direction (even number of nodes):" <<
endl;
display();
} else {
cout << "Displaying list in reverse direction (odd number of nodes):" <<
endl;
displayReverse();
}
}
};
int main() {
CircularLinkedList list;
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](5);

cout << "Original List: ";


[Link]();

[Link]();

cout << "List after deleting the first node: ";


[Link]();

cout << "Number of nodes: " << [Link]() << endl;

cout << "Greatest value in the circular linked list: " << [Link]() <<
endl;

[Link]();

return 0;
}
Static stack
#include<iostream>
using namespace std;

class Stack {
int top;
int size;
public:
int *a;
Stack(int n) {
size = n;
top = -1;
a = new int[size];
}
~Stack() {
delete[] a;
}
void push(int x) {
if(top >= size-1) {
cout<<"Stack Overflow\n";
return;
}
a[++top] = x;
}
void pop() {
if(top < 0) {
cout<<"Stack Underflow\n";
return;
}
top--;
}
int peek() {
if(top < 0) {
cout<<"Stack is empty\n";
return -1;
}

return a[top];
}
bool isEmpty() {
return (top < 0);
}
};

int main() {
Stack s(5);
[Link](1);
[Link](2);
[Link](3);
[Link](4);
[Link](5);
[Link]();
[Link](6);

while(![Link]()) {
int val = [Link]();
cout<<val<<" ";
[Link]();
}
[Link]();

[Link]();

return 0;
}

Dynamic Stack
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(){
data=0;
next=NULL;
}
Node(int data){
this->data=data;
this->next=NULL;
}
};
class Stack{
Node* head;
public:
//int top;
//Node* temp=new Node(data);
Stack(){
int top=NULL;
head=NULL;
}
void push (int data){
Node* temp=new Node(data);
temp->next=head;
head=temp;
//top++;
cout<<"Element"<<data<<"is inserted in stack."<<endl;
return;
}
void pop(){
/*if(top==-1){
cout<<"stack is empty."<<endl;
return false;
}*/
Node* temp=head;
head=head->next;
int data=temp->data;
//top--;
cout<<"element"<<data<<"popped out of stack"<<endl;
return;
}

int top(){
/*if(top==-1){
cout<<"stack is empty."<<endl;
return false;
}*/

cout<<"top element is"<<head->data<<endl;


return true;
}
};
int main(){
Stack s;
[Link](2);
[Link](4);
[Link](6);
[Link]();
[Link]();
}

Largest number in three linkedlist to stack


#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int data) {
this->data = data;
this->next = nullptr;
}
};

class LinkedList {
public:
Node* head;

LinkedList() : head(nullptr) {}

void insert(int data) {


Node* newNode = new Node(data);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}

int findMax() {
int maxNum = INT_MIN;
Node* temp = head;
while (temp) {
if (temp->data > maxNum) {
maxNum = temp->data;
}
temp = temp->next;
}
return maxNum;
}
};

class DynamicStack {
public:
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};

Node* head;

DynamicStack() : head(nullptr) {}

void push(int val) {


Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
cout << val << " is pushed into the dynamic stack." << endl;
}
};

class StaticStack {
public:
int stack[100], n = 100, top = -1;

void push(int val) {


if (top >= n - 1) {
cout << "Static Stack Overflow" << endl;
} else {
top++;
stack[top] = val;
cout << val << " is pushed into the static stack." << endl;
}
}
};

void pushLargestToDynamicStack(LinkedList& list, DynamicStack& stack) {


int largest = [Link]();
[Link](largest);
}

void pushLargestToStaticStack(LinkedList& list, StaticStack& stack) {


int largest = [Link]();
[Link](largest);
}

int main() {
LinkedList list1, list2, list3;
DynamicStack dynamicStack;
StaticStack staticStack;

[Link](10);
[Link](20);
[Link](30);

[Link](15);
[Link](25);
[Link](35);
[Link](45);

[Link](5);
[Link](15);
[Link](25);
[Link](35);
[Link](50);

pushLargestToDynamicStack(list1, dynamicStack);
pushLargestToDynamicStack(list2, dynamicStack);
pushLargestToDynamicStack(list3, dynamicStack);

pushLargestToStaticStack(list1, staticStack);
pushLargestToStaticStack(list2, staticStack);
pushLargestToStaticStack(list3, staticStack);

return 0;
}
//create a linklist of five elements traverse the list and
copy the contents of the list into another list but in
reverse order
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int data) {
this->data = data;
this->next = nullptr;
}
};

class LinkedList {
public:
Node* head;

LinkedList() : head(nullptr) {}

void insert(int data) {


Node* newNode = new Node(data);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}

void traverse() {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

LinkedList reverseCopy() {
LinkedList reversedList;
Node* temp = head;
while (temp) {
Node* newNode = new Node(temp->data);
newNode->next = [Link];
[Link] = newNode;
temp = temp->next;
}
return reversedList;
}
};

int main() {
LinkedList list1;
[Link](10);
[Link](20);
[Link](30);
[Link](40);
[Link](50);

cout << "Original List: ";


[Link]();

LinkedList list2 = [Link]();

cout << "Reversed Copy List: ";


[Link]();

return 0;
}
// cretae a linkdlist input number from user and
creates nodes by given formula n^2+n^3+n^4..(square
of first node" plus" cube of second node ...)
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};

class LinkedList {
private:
Node* head;

void insertNode(int newData) {


Node* newNode = new Node(newData);
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}

int calculateValue(int n) {
return n * n + n * n * n + n * n * n * n;
}

public:
LinkedList() {
head = nullptr;
}

void createList(int count) {


for (int i = 1; i <= count; ++i) {
int value = calculateValue(i);
insertNode(value);
}
}

void display() {
Node* temp = head;
cout << "Linked List generated using the formula n^2 + n^3 + n^4:\n";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
LinkedList list;
int count;
cout << "Enter the number of nodes: ";
cin >> count;
[Link](count);
[Link]();
return 0;
}

//write a c++ progra that cretaes a stack push n


number of values into the stack pop the values into
the linkedlist traverse the linked from head to the null

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;

Node(int data) {
this->data = data;
this->next = nullptr;
}
};

class LinkedList {
public:
Node* head;

LinkedList() : head(nullptr) {}

void insert(int data) {


Node* newNode = new Node(data);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}

void traverse() {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

class Stack {
public:
int stack[100], n = 100, top = -1;

void push(int val) {


if (top >= n - 1) {
cout << "Stack Overflow" << endl;
} else {
top++;
stack[top] = val;
cout << val << " is pushed into the stack." << endl;
}
}
void popAndInsertIntoLinkedList(LinkedList& list) {
while (top >= 0) {
int poppedValue = stack[top];
[Link](poppedValue);
top--;
}
}
};

int main() {
int n;
cout << "Enter the number of values to push into the stack: ";
cin >> n;

Stack stack;
LinkedList list;

for (int i = 1; i <= n; i++) {


[Link](i);
}

[Link](list);

cout << "Linked list elements: ";


[Link]();

return 0;
}

Static to dynamic
#include <iostream>
using namespace std;

class StaticStack {
public:
int stack[100], n = 100, top = -1;

void push(int val) {


if (top >= n - 1)
cout << "Static Stack Overflow" << endl;
else {
top++;
stack[top] = val;
cout << val << " is pushed into the static stack." << endl;
}
}

int pop() {
if (top <= -1) {
cout << "Static Stack Underflow" << endl;
return -1;
} else {
int popped = stack[top];
top--;
return popped;
}
}
};

class DynamicStack {
class Node {
public:
int data;
Node* next;

Node(int data) {
this->data = data;
this->next = nullptr;
}
};

Node* head;

public:
DynamicStack() : head(nullptr) {}

void push(int val) {


Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
cout << val << " is pushed into the dynamic stack." << endl;
}

void popFromStaticStackAndPush(StaticStack& staticStack) {


int poppedValue = [Link]();
if (poppedValue != -1) { // If stack is not empty
push(poppedValue);
} else {
cout << "Cannot pop from empty static stack." << endl;
}
}
};

int main() {
StaticStack staticStack;
DynamicStack dynamicStack;

[Link](10);
[Link](20);
[Link](30);

[Link](staticStack);
[Link](staticStack);
[Link](staticStack);

return 0;
}

Queue
#include<iostream>
using namespace std;
//enQueue(): This operation adds a new node after the rear and moves the
rear to the next node.
//deQueue(): This operation removes the front node and moves the front to
the next node.
class Node {
public:
int data;
Node* next;
};

class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = NULL;
rear = NULL;
}
void enqueue(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;

if (rear == NULL) {
front = newNode;
rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}

int dequeue() {
if (front == NULL) {
cout << "Queue is empty!" << endl;
return -1;
}

int data = front->data;


Node* temp = front;
front = front->next;

if (front == NULL) {
rear = NULL;
}

delete temp;
return data;
}

bool isEmpty() {
return (front == NULL);
}

void Display() {
Node* temp;
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}

void frontd(){
if(front != NULL){
cout<<front->data <<endl;
}
else
{
return ;
}

};

int main() {
Queue q;

[Link](1);
[Link](2);
[Link](3);
[Link]();
cout << "Queue Front : " << endl;
[Link]();

cout << "Dequeued: " << [Link]() << endl;


cout << "Dequeued: " << [Link]() << endl;
cout << "Dequeued: " << [Link]() << endl;
cout << "Is Empty? " << ([Link]() ? "Yes" : "No") << endl;

cout << "Queue Front : " << endl;


[Link]();

return 0;
}

List to queue
#include<iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
};

class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = NULL;
rear = NULL;
}

void enqueue(int data) {


Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;

if (rear == NULL) {
front = newNode;
rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}

int dequeue() {
if (front == NULL) {
cout << "Queue is empty!" << endl;
return -1;
}

int data = front->data;


Node* temp = front;
front = front->next;
if (front == NULL) {
rear = NULL;
}

delete temp;
return data;
}

bool isEmpty() {
return (front == NULL);
}

void display() {
Node* temp = front;
if (front == NULL) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements are: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() {
head = NULL;
}

void insert(int data) {


Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

void display() {
Node* temp = head;
if (head == NULL) {
cout << "Linked list is empty" << endl;
return;
}
cout << "Linked list elements are: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

Queue copyToQueue() {
Queue q;
Node* temp = head;
while (temp != NULL) {
[Link](temp->data);
temp = temp->next;
}

Queue reversedQ;
while (![Link]()) {
[Link]([Link]());
}
return reversedQ;
}

void copyFromQueue(Queue q) {
while (![Link]()) {
insert([Link]());
}
}
};

int main() {
LinkedList list;
[Link](1);
[Link](2);
[Link](3);

cout << "Original Linked List: ";


[Link]();

Queue queue = [Link]();


cout << "Copied Queue from Linked List: ";
[Link]();

LinkedList newList;
[Link](queue);
cout << "Linked List copied from Queue: ";
[Link]();
[Link]();
return 0;
}

You might also like