implement the ListLinked ADT (the declaration is given in ListLinked.h)(60 point

Question

implement the ListLinked ADT (the declaration is given in ListLinked.h)(60 points)

- implement the following operations:

- constructor, assignment operator, destructor

- insert, remove, replace, clear

- isFull, isEmpty

- gotoBeginning, gotoEnd, gotoNext, gotoPrior, getCursor

implement the function moveToBeginning() that removes the data item marked by the cursor and reinserts it at the beginning of the list

- implement the function insertBefore(..) that will insert the new data item before the cursor or if the list is empty as the first element of the list

#include "ListLinked.h"

// ListNode member functions

template
List::ListNode::ListNode(const DataType& nodeData, ListNode* nextPtr)
{
   this->dataItem = nodeData;
   this->next = nextPtr;
}

// List member functions

template
List::List(int ignored = 0)
{
}

template
List::List(const List& other)
{
}

template
List& List::operator=(const List& other)
{
}

template
List::~List()
{
}

template
void List::insert(const DataType& newDataItem) throw (logic_error)
{
}

template
void List::remove() throw (logic_error)
{
}

template
void List::replace(const DataType& newDataItem) throw (logic_error)
{
}

template
void List::clear()
{
}

template
bool List::isEmpty() const
{
   return false;
}

template
bool List::isFull() const
{
   return false;
}

template
void List::gotoBeginning() throw (logic_error)
{
}

template
void List::gotoEnd() throw (logic_error)
{
}

template
bool List::gotoNext() throw (logic_error)
{
   return false;
}

template
bool List::gotoPrior() throw (logic_error)
{
   return false;
}

template
DataType List::getCursor() const throw (logic_error)
{
   DataType t;
   return t;
}

template
void List::moveToBeginning () throw (logic_error)
{
}

template
void List::insertBefore(const DataType& newDataItem) throw (logic_error)
{
}

#include "show5.cpp"

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node
{
   int data;
   Node *next;
};
Node *tail=NULL;

Node* Insert_atHead(Node *head, int data)
{
Node *temp=new Node;
temp->data=data;
temp->next=head;
head=temp;
return head;
}

Node* Insert_atTail(Node *head, int data)
{
Node *tail=head;
       if(tail==NULL)
{
Node *temp = new Node;
temp->data=data;
temp->next=NULL;
head=temp;
return head;
}
while(tail!= NULL)
{
if(tail->next==NULL)
{
Node *temp=new Node;
temp->data=data;
temp->next=NULL;
tail->next=temp;
return tail;
}
else
{
tail=tail->next;
}
}
}

Node *Insert_atPosition(Node *head, int data, int position)
{
int i=0;
int j=position-1;

if(position==0)
{
Node *temp = new Node;
temp->data=data;
temp->next=head;
head=temp;
return head;
}
else
       {
Node *temp=head;
while(i<j)
{
temp=temp->next;
i++;
}

Node *temp1 = new Node;
temp1->data=data;
temp1->next=temp->next;
temp->next=temp1;
return head;
}
return head;

}

Node* Delete(Node *head, int position)
{
Node *temp=head;
int i=1;
int j=position;
if(j==0)
{
head=head->next;
return head;
}
Node *temp1 = new Node;
while(j>0)
{
temp1=temp;
temp=temp->next;
j--;
}
temp1->next=temp->next;
delete temp;
return head;
}

int GetNode(Node *head,int positionFromTail)
{
Node *tail=head;
int l=0;
while(tail->next!=NULL)
{
tail=tail->next;
l++;
}

int i=(l-positionFromTail);
Node *temp=head;

while(i>0)
{
temp=temp->next;
i--;
}
return temp->data;
}

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

Node *Reverse_LinkedList(Node *head)
{
Node *temp1 = head;
       Node *tail = NULL;
       Node *head1= new Node;

while(head!=NULL)
{
           head1=head;
temp1=temp1->next;
head->next=tail;
tail=head;
head=temp1;
}
   head=head1;      
}

int CompareLists(Node *headA, Node* headB)
{
Node *tempA=headA;
Node *tempB=headB;
  
while(tempA!=NULL && tempB!=NULL)
{
if(tempA->data==tempB->data)
{
tempA=tempA->next;
tempB=tempB->next;
}
else
{
return 0;
}
}
if(tempA==NULL && tempB==NULL)
{
return 1;
}
else
{
return 0;
}
}

int FindMergeNode(Node *headA, Node *headB)
{
Node *tempA=headA;
Node *tempB=headB;
int m=0;
int n=0;;
  
while(tempA!=NULL)
{
tempA=tempA->next;
m++;
}
while(tempB!=NULL)
{
tempB=tempB->next;
n++;
}
tempA=headA;
tempB=headB;
int Data;
if(m>n)
{
int p=m-n;
while(p>0)
{
tempA=tempA->next;
p--;
}
while(tempA!=tempB)
{
tempA=tempA->next;
tempB=tempB->next;
}
Data=tempA->data;
}
else
{
int p = n-m;
while(p>0)
{
tempB=tempB->next;
p--;
}
while(tempA!=tempB)
{
tempA=tempA->next;
tempB=tempB->next;
}
Data=tempA->data;
}   
return Data;
}  

Node* RemoveDuplicates(Node *head)
{
Node *temp=head;
Node *temp1 = new Node;
while(temp->next!=NULL)
{
if(temp->data!=(temp->next)->data)
{
temp=temp->next;
}
else
{
temp1=temp->next;
temp->next=temp1->next;
delete temp1;
}
}
return head;
}
  
Node* MergeLists(Node *headA, Node* headB)
{
Node *temp = new Node;
Node *head = new Node;
if(headA==NULL || headB==NULL)
{
if(headA==NULL)
{
head=headB;
}
else
{
head=headA;
}
return head;
}
if(headA->data<=headB->data)
{
temp=headA;
headA=headA->next;
}
else
{
temp=headB;
headB=headB->next;
}
head=temp;
  
while(headA!=NULL && headB!=NULL)
{
if(headA->data<=headB->data)
{
temp->next=headA;
temp=temp->next;
headA=headA->next;
}
else
{
temp->next=headB;
temp=temp->next;
headB=headB->next;
}
}
  
if(headA==NULL && headB!=NULL)
{
temp->next=headB;
}
if(headA!=NULL && headB==NULL)
{
temp->next=headA;
}
  
return head;
}  
  
int HasCycle(Node* head)
{
Node *temp1=head;
Node *temp2=head;
int X=0;
if(head==NULL || head->next==NULL)
{
X=0;
}
else
{
temp1=temp1->next;
temp2=(temp2->next)->next;
while(temp1!=temp2)
{
if(temp2->next==NULL || (temp2->next)->next==NULL)
{
X=0;
break;
}
temp1=temp1->next;
temp2=(temp2->next)->next;
X=1;
}

}
if(X==0)
{
return 0;
}
else
{
return 1;
}
  
}  
  
  
void Print(Node *head)
{
   Node *temp = head;
   while(temp!= NULL)
{
cout<<temp->data<< " --> ";
temp=temp->next;
}
cout<< "NULL";
}

void ReversePrint(Node *head)
{   
Node *temp1 = head;
       Node *tail = NULL;
       Node *head1= new Node;

if(head!=NULL)
{
while(head!=NULL)
{
           head1=head;
temp1=temp1->next;
head->next=tail;
tail=head;
head=temp1;
}

   Node *temp=head1;
   while(temp!= NULL)
{
cout<<temp->data<< " ";
temp=temp->next;
}
}
}     
     
int main() {
int data;
Node *head=NULL;

int H;
cout<< "No. of Node Insertion at Head: ";
cin>>H;
while(H>0)
{
cin>>data;
head=Insert_atHead(head, data);
H--;
}

int T;
cout<< "No. of Node Insertion at Tail: ";
cin>>T;
while(T>0)
{
cin>>data;
Insert_atTail(head,data);
T--;
}

int P;
cout<< " ";
cout<< "Add Node at Position: ";
cin>>P;
cout<< " ";
cout<< "data: ";
cin>>data;
Insert_atPosition(head,data,P);

cout<< " ";
cout<< "Delete Node at Position: ";
cin>>P;
Delete(head,P);
cout<< " ";
Print(head);

Reverse_LinkedList(head);
head=tail;
cout<< " ";
Print(head);

cout<< " ";
cout<< "Size of LinkedList: "<<Size_ofLinkedList(head);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.