Question

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

• 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 ).

You are required to write self commenting code for this Lab, refer to the Google Style Sheet if you haven't become familiar with it.

Answer 1

Answer:

Singly and Doubly linked list classes:

//Initially, declare the class NODE:
class Node
{
public:
 int data;
 Node *next;
};
class SLinkedList
{
private:
 Node *first;
public:
 SLinkedList(){first=NULL;}
 SLinkedList(int A[],int n);
 ~SLinkedList();

 void Display();
 void Insert(int index,int x);
 int Delete(int index);
 int Length();
};
SLinkedList::SLinkedList(int A[],int n)
{
 Node *last,*t;
 int i=0;

 first=new Node;
 first->data=A[0];
 first->next=NULL;
 last=first;
 
 for(i=1;i<n;i++)
 {
 t=new Node;
 t->data=A[i];
 t->next=NULL;
 last->next=t;
 last=t;
 }
}
SLinkedList::~SLinkedList()
{
 Node *p=first;
 while(first)
 {
 first=first->next;
 delete p;
 p=first;
 }
}
void SLinkedList::Display()
{
 Node *p=first;

 while(p)
 {
 cout<<p->data<<" ";
 p=p->next;
 }
 cout<<endl;
}
int SLinkedList::Length()
{
 Node *p=first;
 int len=0;

 while(p)
 {
 len++;
 p=p->next;
 }
 return len;
}
void SLinkedList::Insert(int index,int x)
{
 Node *t,*p=first;

 if(index <0 || index > Length())
 return;
 t=new Node;
 t->data=x;
 t->next=NULL;

 if(index==0)
 {
 t->next=first;
 first=t;
 }
 else
 {
 for(int i=0;i<index-1;i++)
 p=p->next;
 t->next=p->next;
 p->next=t;
 }
}
int SLinkedList::Delete(int index)
{
 Node *p,*q=NULL;
 int x=-1;

 if(index < 1 || index > Length())
 return -1;
 if(index==1)
 {
 p=first;
 first=first->next;
 x=p->data;
 delete p;
 }
 else
 {
 p=first;
 for(int i=0;i<index-1;i++)
 {
 q=p;
 p=p->next;
 }
 q->next=p->next;
 x=p->data;
 delete p;
 }
 return x;
}

DOUBLY LINKED LIST CLASS:

//Here, we make 2 pointers pointing to the previous and next node.
class Node{
public:
    Node* prev;
    int data;
    Node* next;
};
 
class DoublyLinkedList{
private:
    Node* head;
public:
    DoublyLinkedList();
    DoublyLinkedList(int A[], int n);
    ~DoublyLinkedList();
    void Display();
    int Length();
    void Insert(int index, int x);
    int Delete(int index);
    void Reverse();
};
 
 
DoublyLinkedList::DoublyLinkedList() {
    head = new Node;
    head->prev = nullptr;
    head->data = 0;
    head->next = nullptr;
}
 
DoublyLinkedList::DoublyLinkedList(int *A, int n) {
 
    head = new Node;
    head->prev = nullptr;
    head->data = A[0];
    head->next = nullptr;
    Node* tail = head;
 
    for (int i=1; i<n; i++){
        Node* t = new Node;
        t->prev = tail;
        t->data = A[i];
        t->next = tail->next; // tail->next is pointing to NULL
        tail->next = t;
        tail = t;
    }
}
 
void DoublyLinkedList::Display() {
    Node* p = head;
    while (p != nullptr){
        cout << p->data << flush;
        p = p->next;
        if (p != nullptr){
            cout << " <-> " << flush;
        }
    }
    cout << endl;
}
 
int DoublyLinkedList::Length() {
    int length = 0;
    Node* p = head;
    while (p != nullptr){
        length++;
        p = p->next;
    }
    return length;
}
 
void DoublyLinkedList::Insert(int index, int x) {
 
    if (index < 0 || index > Length()){
        return;
    }
 
    Node* p = head;
    Node* t = new Node;
    t->data = x;
 
    if (index == 0){
        t->prev = nullptr;
        t->next = head;
        head->prev = t;
        head = t;
    } else {
        for (int i=0; i<index-1; i++){
            p = p->next;
        }
        t->prev = p;
        t->next = p->next;
        if (p->next){
            p->next->prev = t;
        }
        p->next = t;
    }
}
 
int DoublyLinkedList::Delete(int index) {
    int x = -1;
    Node* p = head;
 
    if (index < 0 || index > Length()){
        return x;
    }
 
    if (index == 1){
        head = head->next;
        if (head){
            head->prev = nullptr;
        }
        x = p->data;
        delete p;
    } else {
        for (int i=0; i<index-1; i++){
            p = p->next;
        }
        p->prev->next = p->next;
        if (p->next){
            p->next->prev = p->prev;
        }
        x = p->data;
        delete p;
    }
    return x;
}
 
void DoublyLinkedList::Reverse() {
    Node* p = head;
    Node* temp;
    while (p != nullptr){
        temp = p->next;
        p->next = p->prev;
        p->prev = temp;
        p = p->prev;
 
        // Need to check the following condition again
        if (p->next == nullptr){
            p->next = p->prev;
            p->prev = nullptr;
            head = p;
            break;
        }
    }
}
 
DoublyLinkedList::~DoublyLinkedList() {
    Node* p = head;
    while (head){
        head = head->next;
        delete p;
        p = head;
    }
}
 
 

Note: The answers are provided by an expert based on his previous expertise and knowledge. This content is plagiarism free, feel free to cross verify.

And kindly upvote for the efforts that we make every single day to answer the questions

I wish you all the best for your future endeavours.

And if you need any clarification, feel free to ask