Question
In: Computer Science
In C++ please: In this lab we will creating two linked list classes: one that is...
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:
-
Print
-
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 ).
Solutions
Expert Solution
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
venereology answered 1 year agoRelated Solutions
In C++ In this lab we will creating two linked list classes: one that is a...
In C++
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:
Print
Add - Adds element to the end of the linked list.
IsEmpty...
In Java In this lab we will creating two linked list classes: one that is a...
In Java
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:
Print
Add - Adds element to the end of the linked list.
IsEmpty...
C++ Linked Lists Practice your understanding of linked lists in C++ by creating a list of...
C++ Linked Lists
Practice your understanding of linked lists in C++ by creating a
list of songs/artist pairs. Allow your user to add song / artist
pairs to the list, remove songs (and associated artist) from the
list and be sure to also write a function to print the list! Have
fun!
Make sure you show your implementation of the use of vectors in
this lab (You can use them too )
You MUST modularize your code ( meaning, there...
In C++ In this lab we will be creating a stack class and a queue class,...
In C++
In this lab we will be creating a stack class and a queue class,
both with a hybrid method combining linked list and arrays in
addition to the Stack methods(push, pop, peek, isEmpty, size,
print) and Queue methods (enqueue, deque, peek, isEmpty, size,
print).
DO NOT USE ANY LIBRARY, implement each method from scratch.
Both the Stack and Queue classes should be generic classes.
Don't forget to comment your code.
Please use C++ and linked list to solve this problem Linked list 1 -> 3 ->...
Please use C++ and linked list to solve this problem
Linked list 1 -> 3 -> 4 -> 5-> 6 ->7
replaceNode( 5 , 6) // Replace 5 with 6
result 1 -> 3 -> 4 -> 6 -> 6
->7
Base code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *next;
Node(int da = 0, Node *p = NULL) {
this->data =
da;
this->next = p;
}
};...
Please use C++ and linked list to solve this problem Linked list 1 -> 2 ->...
Please use C++ and linked list to solve this problem
Linked list 1 -> 2 -> 3 -> 4 -> 5-> 6 ->7
replaceNode( 5 , 6) // Replace 5 with 6
result 1 -> 2 -> 3 -> 4 -> 6
-> 6 ->7
Base code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *next;
Node(int da = 0, Node *p = NULL) {
this->data =
da;
this->next =...
C++ Only Please 10.15 LAB: Warm up: Contacts You will be building a linked list. Make...
C++ Only Please
10.15 LAB: Warm up: Contacts
You will be building a linked list. Make sure to keep track
of both the head and tail nodes.
(1) Create three files to submit.
ContactNode.h - Class declaration
ContactNode.cpp - Class definition
main.cpp - main() function
(2) Build the ContactNode class per the following
specifications:
Parameterized constructor. Parameters are name followed by phone
number.
Public member functions
InsertAfter() (2 pts)
GetName() - Accessor (1 pt)
GetPhoneNumber - Accessor (1 pt)
GetNext()...
In this lab, we will build a couple of classes, where one will be composed into...
In this lab, we will build a couple of classes, where one will
be composed into the other. Work in pairs if you wish.
Problem
We saw Point.java in class last week. Do the following,
one step at a time, making sure it works before you go on
to the next step. Be sure to get help if you have any
difficulties.
You may use Point.java from last week or build a new one of
your own. If you are...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked
list
In this lab you will implement the functionality of a stack and
a queue using a linked list. Your program must use of the
declaration of the Stack and Queue class in Stack.h and Queue.h
You have to implement the functionalities of queue (enq, deq,
displayQueue) in a file called Queue.cpp. All the functions in
Queue.cpp should follow the prototypes declared in Queue.h.
Your code should make use...
In C++: In this lab we will creating twos arrays of Generic objects, searching through those...
In C++:
In this lab we will creating twos arrays of Generic objects,
searching through those arrays using BINARY and SEQUENTIAL sorts,
calculate the run-time of each method, and determine the BIG O,
OMEGA and THETA notation.
In our object we should have some way to compare elements to
determine if one element is LESS THAN, GREATER THAN, and EQUAL TO.
After this Generic Class is defined with a method that allows for
comparison is completed, then you will create...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- Calendars imprints calendars with college names. The company has fixed expenses of $ 1 comma 065...
- The daily intake of calcium was measured (in milligrams) from a random sample of 16 women...
- Mount Alberta in Jasper National Park, Alberta, has an elevation of 3620 m above sea level....
- Reflect on what you have learned in this module by answering these questions: As a Human...
- Chapter 3 discusses social behavior, and some of the variables that allow humans to be “ultrasocial”...
- Example Problem: [Ch 9, Q36] Consider the following hypothesis test: ?0: ? ≥ 0.75; ??: ?...
- Consider a gaseous feed, CA0=100, CB0=200, enters a flow reactor at T0=1000 K and ?0= 5...
ADVERTISEMENT