CS-253 Data Structures and Algorithms
Assignment 1: Linked Lists
Name: Arham Siddiqui
CMS ID: 428887
Instructor: Engr. Naema Asif
1. Write a C++ program to create and display a Singly Linked List. Test Data:
The list contains the data entered: 12 9 6 4 2 1
CODE:
#include<iostream>
using namespace std;
class node{
public:
int value=0;
node* next;
node(int value){
this->value =value;
next = nullptr;
}
};
class linkedlist{
private:
node* head= NULL;
public:
void InsertAtHead (int value) {
node *newnode= new node(value);
newnode->next = head;
head = newnode;
}
void display (){
node * temp=head;
while (temp!=NULL){
cout << temp->value<<" ";
temp=temp->next;
}
cout<<endl;
}
};
int main (){
linkedlist list;
list.InsertAtHead(1);
list.InsertAtHead(2);
list.InsertAtHead(4);
list.InsertAtHead(6);
list.InsertAtHead(9);
list.InsertAtHead(12);
cout<< "The list contains the following data: ";
list.display();
return 0;
}
Output:
2. Write a C++ program to find the middle element of a given Linked List.
Test Data: Original list: 7 5 3 1
Middle element of the said list: 3
Original list: 9 7 5 3 1
Middle element of the said list: 5
CODE:
#include<iostream>
using namespace std;
class node{
public:
int value=0;
node* next;
node(int value){
this->value =value;
next = nullptr;
}
};
class linkedlist{
private:
node* head= NULL;
public:
void InsertAtHead (int value) {
node *newnode= new node(value);
newnode->next = head;
head = newnode;
}
void display (){
node * temp=head;
while (temp!=NULL){
cout << temp->value<<" ";
temp=temp->next;
}
cout<<endl;
}
void getmiddle (){
int count=0;
node*temp=head;
while (temp!=NULL){
temp=temp->next;
count++;
}
count/=2;
int location=0;
temp=head;
while (location!=count){
temp=temp->next;
location++;
}
cout<<temp->value<<endl;
};
int main (){
linkedlist list;
list.InsertAtHead(1);
list.InsertAtHead(3);
list.InsertAtHead(5);
list.InsertAtHead(7);
cout<< "The list contains the following data: ";
list.display();
list.getmiddle();
//list.display();
return 0;
}
OUTPUT:
3. Write a C++ program to get Nth node in a given Singly Linked List.
Test Data:
Original list: 7 5 3 1
Position: 1 Value: 7
Position: 2 Value: 5
Position: 3 Value: 3
Position: 4 Value: 1
CODE:
#include<iostream>
using namespace std;
class node{
public:
int value=0;
node* next;
node(int value){
this->value =value;
next = nullptr;
}
};
class linkedlist{
private:
node* head= NULL;
public:
void InsertAtHead (int value) {
node *newnode= new node(value);
newnode->next = head;
head = newnode;
}
void display (){
node * temp=head;
while (temp!=NULL){
cout << temp->value<<" ";
temp=temp->next;
}
cout<<endl;
}
void getnode(int location){
node*temp=head;
int i=1;
while (i!=location){
temp=temp->next;
i++;
}
cout<<temp->value<<endl;
};
int main (){
linkedlist list;
list.InsertAtHead(1);
list.InsertAtHead(3);
list.InsertAtHead(5);
list.InsertAtHead(7);
cout<< "The list contains the following data: ";
list.display();
cout<< "Position 3: ";
list.getnode(3);
return 0;
}
OUTPUT:
4. Write a C++ program to insert a new node at any position of a Singly Linked List.
Test Data:
Original list: 7 5 3 1
Position: 1, Value: 12
Updated list: 12 7 5 3 1
CODE:
#include<iostream>
using namespace std;
class node{
public:
int value=0;
node* next;
node(int value){
this->value =value;
next = nullptr;
}
};
class linkedlist{
private:
node* head= NULL;
public:
void InsertAtHead (int value) {
node *newnode= new node(value);
newnode->next = head;
head = newnode;
}
void display (){
node * temp=head;
while (temp!=NULL){
cout << temp->value<<" ";
temp=temp->next;
}
cout<<endl;
}
void InsertNewNode (int location, int value){
node*temp=head;
int i=0;
if (location==1){
node *newnode= new node(value);
newnode->next = head;
head = newnode;
}
while (i<location-2){
temp=temp->next;
i++;
}
node* newnode= new node(value);
newnode->next=temp->next;
temp->next=newnode;
}
};
int main (){
linkedlist list;
list.InsertAtHead(1);
list.InsertAtHead(3);
list.InsertAtHead(5);
list.InsertAtHead(7);
list.InsertAtHead(17);
list.InsertAtHead(78);
cout<< "The list contains the following data: ";
list.display();
list.InsertNewNode(3,19);
list.display();
return 0;
}
OUTPUT:
