In: Computer Science
In C++ please:
In this lab we will creating two linked list classes: one that is a singly linked list, and another that is a doubly linked list ( This will be good practice for your next homework assignment where you will build your own string class using arrays and linked list ) .
These LinkedList classes should both be generic classes. and should contain the following methods:
Add - Adds element to the end of the linked list.
IsEmpty
Push - Adds element to the beginning of the linked list
InsertAt - Inserts an element at a given position
Clear - Removes all elements from the linked list
Contains - Returns true if element is in the linked list
Get - Returns a value at a specific position
IndexOf - Returns the first position where an element occurs, -1 if not
LastOf - Returns the last position where an element occurs, -1 if not
Remove - Removes the last item added to the list
RemoveAt - Removes an element at a specific position
RemoveElement - Removes the first occurrence of a specific element
Size
Slice - Returns a subset of this linked list given a beginning position start and end position stop.
You will also count the number of operations that is performed in each method and will calculate the RUN-TIME of each method, as well as calculating the BIG O, OMEGA and THETA notation of each method. This information should be written in a comment block before each method ( you may count the number of operations on each line if you want ).
SINGLY LINKED LIST PROGRAM
#include <iostream>
using namespace std;
template<typename T>
struct node {
node<T>* next;
T data;
};
template<typename T>
class SinglyLinkedList
{
public:
node<T>* first;
SinglyLinkedList<T>() {
first = NULL;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
void Print(){
node<T>* curr = this->first;
while(curr != NULL){
cout<<curr->data<<" ";
curr = curr->next;
}
cout<<endl;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void Add(T data) {
if(first == NULL) {
// The list is empty
first = new node<T>;
first->data = data;
first->next = NULL;
}
else {
// The list isn't empty
node<T>* curr = first;
while(curr->next != NULL){
curr = curr->next;
}
node<T>* temp = new node<T>;
temp->data = data;
temp->next = NULL;
curr->next = temp;
}
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
bool isEmpty(){
if(this->first == NULL){
return true;
}
return false;
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Push(T data){
if(first == NULL) {
// The list is empty
first = new node<T>;
first->data = data;
first->next = NULL;
}
else{
node<T>* temp = new node<T>;
temp->data = data;
temp->next = first;
first = temp;
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void InsertAt(T data, int pos){
if(pos==0){
Push(data);
}
else{
node<T>* curr = first;
for(int i=1;i<pos-1;i++){
curr = curr->next;
}
node<T>* temp = new node<T>;
temp->data = data;
temp->next = curr->next;
curr->next = temp;
}
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Clear(){
this->first = NULL;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
bool Contains(T data){
node<T>* curr = first;
while(curr != NULL){
if(curr->data == data){
return true;
}
curr = curr->next;
}
return false;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
T get(int index) {
if(index == 0) {
// Get the first element
return this->first->data;
} else {
// Get the index'th element
node<T>* curr = this->first;
for(int i = 0; i < index; ++i) {
curr = curr->next;
}
return curr->data;
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
int IndexOf(T data){
int index = -1;
node<T>* curr = this->first;
while(curr != NULL){
if(curr->data == data){
return index+1;
}
curr = curr->next;
index++;
}
return -1;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
int LastOf(T data){
int index = 0;
int ans = -1;
node<T>* curr = this->first;
while(curr != NULL){
if(curr->data == data){
ans = index;
}
index++;
curr = curr->next;
}
return ans;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
void Remove(){
node<T>* prev = NULL;
node<T>* curr = first;
while(curr->next != NULL){
prev = curr;
curr = curr->next;
}
prev->next = NULL;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void RemoveAt(int pos){
node<T>* curr = this->first;
node<T>* prev = NULL;
if(pos==0){
first = first->next;
}
else{
for(int i=1;i<pos;i++){
prev = curr;
curr = curr->next;
}
prev->next = curr->next;
curr->next = NULL;
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void RemoveElement(T data){
if(first->data == data){
first = first->next;
}
else{
node<T>* curr = this->first;
node<T>* prev = NULL;
while(curr != NULL){
prev = curr;
curr = curr->next;
if(curr->data == data){
prev->next = curr->next;
break;
}
}
}
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
int Size(){
int cnt = 0;
node<T>* curr = this->first;
while(curr != NULL){
cnt++;
curr = curr->next;
}
return cnt;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
node<T>* Slice(int start,int end){
int l = end - start + 1;
node<T>* curr = this->first;
for(int i=1;i<start;i++){
curr = curr->next;
}
return curr;
}
};
int main() {
SinglyLinkedList<std::string> list;
list.Add("Hello");
list.Print();
list.Push("Hi");
list.Print();
list.InsertAt("Bye",1);
list.Print();
list.Add("Akash");
list.Print();
if(list.isEmpty()){
cout<<"List is Empty "<<endl;
}
else{
cout<<"List is not empty"<<endl;
}
cout<<"Size = "<<list.Size()<<endl;
cout<<"Element at position 1 is "<<list.get(1)<<endl;
if(list.Contains("X")){
cout<<"List contains X"<<endl;
}
else{
cout<<"List does not contain X"<<endl;
}
cout<<"Position of the word Akash is "<<list.IndexOf("Akash")<<endl;
cout<<"Last Position of the word Akash is "<<list.LastOf("Akash")<<endl;
list.RemoveElement("Akash");
cout<<"After removing Akash from the list "<<endl;
list.Print();
return 0;
}
SAMPLE OUTPUT
Hello Hi Hello Hi Bye Hello Hi Bye Hello Akash List is not empty Size = 4 Element at position 1 is Bye List does not contain X Position of the word Akash is 3 Last Position of the word Akash is 3 After removing Akash from the list Hi Bye Hello
DOUBLY LINKED LIST PROGRAM
#include <iostream>
using namespace std;
template<typename T>
struct node {
node<T>* next;
node<T>* prev;
T data;
};
template<typename T>
class DoublyLinkedList
{
public:
node<T>* first;
node<T>* last;
DoublyLinkedList<T>() {
first = NULL;
last = NULL;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
void Print(){
node<T>* curr = this->first;
while(curr != NULL){
cout<<curr->data<<" ";
curr = curr->next;
}
cout<<endl;
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Add(T data) {
if(first == NULL) {
// The list is empty
first = new node<T>;
first->data = data;
first->next = NULL;
first->prev = NULL;
last = first;
}
else {
// The list isn't empty
if(last == first) {
// The list has one element
last = new node<T>;
last->data = data;
last->next = NULL;
last->prev = first;
first->next = last;
} else {
// The list has more than one element
node<T>* temp = new node<T>;
temp->data = data;
temp->next = NULL;
temp->prev = last;
last->next = temp;
last = temp;
}
}
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
bool isEmpty(){
if(this->first == NULL){
return true;
}
return false;
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Push(T data){
if(first == NULL) {
// The list is empty
first = new node<T>;
first->data = data;
first->next = NULL;
first->prev = NULL;
}
else{
node<T>* temp = new node<T>;
temp->data = data;
temp->next = first;
temp->prev = NULL;
first->prev = temp;
first = temp;
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void InsertAt(T data, int pos){
if(pos==0){
Push(data);
}
else{
node<T>* curr = first;
for(int i=1;i<pos-1;i++){
curr = curr->next;
}
node<T>* temp = new node<T>;
temp->data = data;
temp->next = curr->next;
temp->prev = curr;
curr->next->prev = temp;
curr->next = temp;
}
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Clear(){
this->first = NULL;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
bool Contains(T data){
node<T>* curr = first;
while(curr != NULL){
if(curr->data == data){
return true;
}
curr = curr->next;
}
return false;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
T get(int index) {
if(index == 0) {
// Get the first element
return this->first->data;
} else {
// Get the index'th element
node<T>* curr = this->first;
for(int i = 0; i < index; ++i) {
curr = curr->next;
}
return curr->data;
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
int IndexOf(T data){
int index = -1;
node<T>* curr = this->first;
while(curr != NULL){
if(curr->data == data){
return index+1;
}
curr = curr->next;
index++;
}
return -1;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
int LastOf(T data){
int index = 0;
int ans = -1;
node<T>* curr = this->first;
while(curr != NULL){
if(curr->data == data){
ans = index;
}
index++;
curr = curr->next;
}
return ans;
}
// OMEGA = Ω(1)
// THETA = Θ(1)
// BIG O = O(1)
void Remove(){
this->last = last->prev;
last->next = NULL;
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void RemoveAt(int pos){
node<T>* curr = this->first;
node<T>* prev = NULL;
if(pos==0){
first = first->next;
}
else{
for(int i=1;i<pos;i++){
prev = curr;
curr = curr->next;
}
if(curr->next==NULL){
last = last->prev;
last->next = NULL;
}
else{
curr->next->prev = prev;
prev->next = curr->next;
}
}
}
// OMEGA = Ω(1)
// THETA = Θ(n)
// BIG O = O(n)
void RemoveElement(T data){
if(first->data == data){
first = first->next;
}
else{
node<T>* curr = this->first;
node<T>* prev = NULL;
while(curr != NULL){
prev = curr;
curr = curr->next;
if(curr->data == data){
if(curr->next==NULL){
last = last->prev;
last->next = NULL;
}
else{
curr->next->prev = prev;
prev->next = curr->next;
}
break;
}
}
}
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
int Size(){
int cnt = 0;
node<T>* curr = this->first;
while(curr != NULL){
cnt++;
curr = curr->next;
}
return cnt;
}
// OMEGA = Ω(n)
// THETA = Θ(n)
// BIG O = O(n)
node<T>* Slice(int start,int end){
int l = end - start + 1;
node<T>* curr = this->first;
for(int i=1;i<start;i++){
curr = curr->next;
}
return curr;
}
};
int main() {
DoublyLinkedList<std::string> list;
list.Add("Hello");
list.Print();
list.Add("Hi");
list.Print();
list.InsertAt("Bye",1);
list.Print();
list.Add("Akash");
list.Print();
if(list.isEmpty()){
cout<<"List is Empty "<<endl;
}
else{
cout<<"List is not empty"<<endl;
}
cout<<"Size = "<<list.Size()<<endl;
cout<<"Element at position 1 is "<<list.get(1)<<endl;
if(list.Contains("X")){
cout<<"List contains X"<<endl;
}
else{
cout<<"List does not contain X"<<endl;
}
cout<<"Position of the word Akash is "<<list.IndexOf("Akash")<<endl;
cout<<"Last Position of the word Akash is "<<list.LastOf("Akash")<<endl;
list.RemoveElement("Akash");
cout<<"After removing Akash from the list "<<endl;
list.Print();
return 0;
}
SAMPLE OUTPUT
Hello Hello Hi Hello Bye Hi Hello Bye Hi Akash List is not empty Size = 4 Element at position 1 is Bye List does not contain X Position of the word Akash is 3 Last Position of the word Akash is 3 After removing Akash from the list Hello Bye Hi