Linked List section 2
Add member functions to the List class with the following specifications:
A public function .Recursive_List_Size( ) to call a recursive private function to
return the size of the list.
Answer:
int List_Size2(NodePointer h)
{if (h == NULL) return 0;
else return 1 + List_Size2(h->next);}
Public:
template <class keyType, class dataType>
int List<keyType,dataType> :: Recursive_List_Size( )
{ return List_Size2(head); }
Sheet 1
Q1- Assume the structure of a Linked List node is as follows.
Struct node
{intdata;
struct node *next;
};
Explain the functionality of following C functions.
1. What does the following function do for a given Linked List?
Void fun1(struct node* head)
{ if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
Answer:
fun1() prints the given Linked List in reverse manner. For Linked List 1->2->3->4-
>5, fun1() prints 5->4->3->2->1.
Q3- Write a function that returns the maximum integer value of a linked without affecting
the original linked list.
Answer:
int maxInt(struct node *head)
{ int max=0;
while(head!=NULL)
{if(max<head->data)
max=head->data;
head=head->next;
}
return max;
}
Q6. Suppose that p is a pointer to a node in a linked list, and *p is not the tail node. What
are the steps to removing the node after *p? Use one short English sentence for each step.
Answer:
1. define a temporary pointer to Node and assign the value in p->link to the temporary
pointer.
2. assign the value in data member next of the temporary pointer to the data member next of
p.
3. delete node pointed to by the temporary pointer.
In C++ the code will look the following way
1) Node *temp = p->next;
2) p->next = temp->next;
3) delete temp;
Q8-Implement the following function as a new function for the linked list toolkit. (Use the
usual node definition with member variables called data and link.)
size_t count_42s(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the number of occurrences
// of 42 in the data field of a node on the linked list.
// The list itself is unchanged.
Answer:
int count_42s(const node* head_ptr)
{int count =0;
while (head_ptr!=Null)
{if (head_ptr->data == 42)
count++;
head_ptr= head_ptr->link;
}
return count;
}
Q9-Implement the following function as a new function for the linked list toolkit. (Use the
usual node definition with member variables called data and link. The data field is an int.)
int sum(const node* head_ptr);
// Precondition: head_ptr is the head pointer of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the sum of all the data components
// of all the nodes. NOTE: If the list is empty, the function returns 0.
Answer:
int sum(const node* head_ptr)
{node *p;
int sum=0;
for(p= * head_ptr;p!=NULL;p=p->link)
sum+=p->data;
return sum;
}
Previous exercise in Linked List
Given a Linked List of integers, write a function to modify the linked list such that all even
numbers appear before all the odd numbers in the modified linked list. Also, keep the order
of even and odd numbers same.
Answer:
void List::EvenOdd(List &L)
{List lEven,lOdd;
int d;
L.toFirst();
while(!L.curIsEmpty())
{L.retrieveData(d);
if(d%2==0)
lEven.insertEnd(d);
else
lOdd.insertEnd(d);
L.advance();
}
L.makeListEmpty();
lEven.toFirst();
while (! lEven.curIsEmpty() )
{ lEven.retrieveData(d); L.insertEnd (d);
lEven.advance ( );
}
lOdd.toFirst();
while(! lOdd.curIsEmpty() )
{ lOdd.retrieveData (d); L.insertEnd (d);
lOdd.advance ( );
}
}
Write a class Student which contains private members "char* Stud-name, int Stud-ID, float
Total , float Perc". Perc will be calculated using this formula for each student " Perc = Total
/ 500 * 100. The class has only two public methods , "GetStudDetails, PutStudDetails". After
creating the class, use it to read and print multiple student details using linked list of objects.
Answer:
class Student{
string studname;
int studid;
float total,perc;
public:
void GetStudDetails(string &name,int &id,float &t,float &p)
{
name = studname ;
id = studid;
t = total;
p = perc;
}
void PutStudDetails(string name,int id,float t)
{studname = name;
studid=id;
total=t;
perc=(t/500)*100;
}
};
#include"LinkedList.cpp"
int main() {
LinkedList<Student> list;
Student st;
st.PutStudDetails('a', 1, 400);
list.InsertAfter(st);
st.PutStudDetails('b', 2, 300);
list.InsertAfter(st);
st.PutStudDetails('c', 3, 450);
list.InsertAfter(st);
return 0;
}
