A) Linked list implementation The following is a simplified implementation of li
ID: 3590699 • Letter: A
Question
A) Linked list implementation
The following is a simplified implementation of linked list and a demonstration of its usage.
list.h
node.h
list.cpp
node.cpp
list_demo.cpp
Makefile.list
Copy and examine the files. Compile and test them.
THE QUESTIONS ARE LISTED BELOW: (1 & 2)
1. Wrtie a demo function to illustrate the use of all the implemented lists and iterator member functions, including empty(), size(), insert(), erase(), ++, *, pop_front() ..... Check if there're any bugs in the implementation. Fix them if you find any.
2. Implement the member function find() of list. find() takes a data element as input and returns an iterator that points to the node that contains the element. If the element is not in the list, the returned iterator points to NULL.
-----------------------------------------------------------------------------
------------------------------------------------------------------
----------------------------------------------------------------------
--------------------------------------------------------------------------------------
-----------------------------------------------------------
-----------------------------------------------------------------------------------
Copy and examine the files. Compile and test them.
THE QUESTIONS ARE LISTED BELOW: (1 & 2)
1. Wrtie a demo function to illustrate the use of all the implemented lists and iterator member functions, including empty(), size(), insert(), erase(), ++, *, pop_front() ..... Check if there're any bugs in the implementation. Fix them if you find any.
2. Implement the member function find() of list. find() takes a data element as input and returns an iterator that points to the node that contains the element. If the element is not in the list, the returned iterator points to NULL.
-----------------------------------------------------------------------------
//list.h #ifndef LIST_H #define LIST_H template class Node; //forward declaration template class listIterator; //forward declaration template class List { protected: Node *first; Node *last; public: //type definition typedef T value_type; typedef listIterator iterator; //constructor and destructor List (); virtual ~List(); //operations bool empty(); int size(); T &front(); //returns first element T &back(); //returns last element void push_front ( T & ); //insert from the front void push_back( T & ); //insert from the back void pop_front(); //remove first element void pop_back(); //remove last element iterator begin(); iterator end(); void sort(); void insert( iterator &, T &); void erase( iterator & ); void erase( iterator &, iterator &); }; template class listIterator { typedef listIterator iterator; protected: List *theList; Node *currentNode; friend class List; public: //constructor listIterator (); listIterator ( List *tl, Node *cl ); T &operator * (); //dereferencing bool operator != ( iterator &rhs ); iterator & operator ++ ( int ); //prefix iterator operator ++ (); //postfix }; #endif ------------------------------------------------------------------
//Node.h #ifndef NODE_H #define NODE_H template class List; //forward declaration template class listIterator; //forward declaration //a Node is a node ( cell ) template class Node { private: Node ( T &v ); //constructor T value; Node *next; Node *prev; //allow lists and iterators to access members friend class List; friend class listIterator; }; #endif ----------------------------------------------------------------------
//list.cpp #include #include "list.h" #include "node.h" #include using namespace std; template List::List() { first = last = 0; //null list } template bool List::empty() { return first == 0; } template int List::size() //count the number of elements in collection /* Comments from Tong: This is NOT a good implementation as it takes time to traverse the list. A better way is to include a field called 'size' in the List class; when elements are inserted or deleted, size is adjusted. */ { int count = 0; Node *p; for ( p = first; p != 0; p = p->next ) count++; return count; } template void List::push_front( T &a ) { Node *newNode = new Node ( a ); if ( empty() ) first = last = newNode; else { first->prev = newNode; newNode->next = first; first = newNode; } } template void List::pop_front() { Node *temp = first; first = first->next; if ( first != 0 ) first->prev = 0; else last = 0; delete temp; } template List::~List() { Node *p = first; while ( p != 0 ) { Node *temp = p; p = p->next; delete temp; } } template listIterator List::begin() { return iterator ( this, first ); } template listIterator List::end() { return iterator ( this, 0 ); //points beyond last } //listIterator //constructors template listIterator::listIterator() { } template listIterator::listIterator( List *lp, Node *lkp ) { theList = lp; currentNode = lkp; } template T & listIterator::operator * () { return currentNode->value; } template bool listIterator::operator != ( iterator &rhs ) { return currentNode != rhs.currentNode; } template listIterator & listIterator::operator ++ (int) { currentNode = currentNode->next; return *this; } template listIterator listIterator::operator ++ () //postfix form of increment ( e.g. assigned, then increment ) { //make an old copy listIterator clone ( theList, currentNode ); currentNode = currentNode->next; //advance pointer return clone; //return old iterator } template void List::insert( listIterator &itr, T &a ) { Node *p = new Node ( a ); Node *current = itr.currentNode; if ( empty() ) { //empty list first = last = p; return; } //assert ( current ); if ( current == 0 ){ //point to end, thus append to list last->next = p; p->next = 0; p->prev = last; last = p; return; } //otherwise, always insert before p->next = current; p->prev = current->prev; current->prev = p; current = p->prev; if ( current != 0 ) current->next = p; else first = p; } template void List::erase ( listIterator &start, listIterator &stop ) //remove elements from the range ( before stop ) { Node *p = start.currentNode; Node *q = p->prev; Node *stopNode = stop.currentNode; if ( q == 0 ) { //removing initial portion of list first = stopNode; if ( stopNode == 0 ) //pointing to end last = 0; //whole list is deleted else stopNode->prev = 0; } else { q->next = stopNode; if ( stopNode == 0 ) last = q; else stopNode->prev = q; // q->prev = q; } //now delete the atoms while ( start != stop ) { listIterator next = start; ++next; delete start.currentNode; start = next; } } --------------------------------------------------------------------------------------
//node.cpp #include "node.h" #include "list.h" using namespace std; template Node::Node( T &v ) { value = v; prev = next = 0; } -----------------------------------------------------------
//list_demo.cpp /* Because of the use of template when defining the List and node classes, unfortunately, we do need to include the .cpp files here for the current compilers. */ #include #include "list.cpp" #include "node.cpp" using namespace std; template void print_list( List &aList ) { typename List::iterator start, stop; start = aList.begin(); stop = aList.end(); while ( start != stop ){ cout << *start << ", "; ++start; } cout << endl; } int main() { typedef double T; List aList; //a list T n; while ( true ) { cout << "Enter a number, -99 to terminate: "; cin >> n; if ( n == -99 ) break; aList.push_front( n ); //insert into list at front } //while cout << "You have entered the list: " << endl; print_list( aList ); return 0; } -----------------------------------------------------------------------------------
#Makefile EXEC=list_demo SRCS=list.cpp node.cpp list_demo.cpp OBJS=$(SRCS:.cpp=.o) $(EXEC): $(OBJS) g++ -o $@ $(OBJS) #$< evaluates to the target's dependencies, #$@ evaluates to the target $(OBJS): g++ -c $*.cpp clean: rm $(OBJS)
Explanation / Answer
Answer :-
1) Functions used with List :
front() – Returns reference to the first element in the list
back() – Returns reference to the last element in the list
push_front(g) – Adds a new element ‘g’ at the beginning of the list
push_back(g) – Adds a new element ‘g’ at the end of the list
pop_front() – Removes the first element of the list, and reduces size of the list by 1
pop_back() – Removes the last element of the list, and reduces size of the list by 1
begin() – Returns an iterator pointing to the first element of the list
end() – Returns an iterator pointing to the theoretical last element which follows the last element
empty() – Returns whether the list is empty(1) or not(0)
insert() – Inserts new elements in the list before the element at a specified position
erase() – Removes a single element or a range of elements from the list
assign() – Assigns new elements to list by replacing current elements and resizes the list
remove() – Removes all the elements from the list, which are equal to given element
reverse() – Reverses the list
size() – Returns the number of elements in the list
sort() – Sorts the list in increasing order
2)
Simple Member functions
These are the basic member function, which dont have any special keyword like static etc as prefix. All the general member functions, which are of below given form, are termed as simple and basic member functions.
Static Member functions
Static is something that holds its position. Static is a keyword which can be used with data members as well as the member functions. We will discuss this in details later. As of now we will discuss its usage with member functions only.
A function is made static by using static keyword with function name. These functions work for the class as whole rather than for a particular object of a class.
It can be called using the object and the direct member access . operator. But, its more typical to call a static member function by itself, using class name and scope resolution :: operator.
Example :
These functions cannot access ordinary data members and member functions, but only static data members and static member functions.
It doesn't have any "this" keyword which is the reason it cannot access ordinary members. We will study about "this" keyword later.
Const Member functions
We will study Const keyword in detail later, but as an introduction, Const keyword makes variables constant, that means once defined, there values can't be changed.
When used with member function, such member functions can never modify the object or its related data members.
Inline functions
All the member functions defined inside the class definition are by default declared as Inline. We will study Inline Functions in details in the next topic.
Friend functions
Friend functions are actually not class member function. Friend functions are made to give private access to non-class functions. You can declare a global function as friend, or a member function of other class as friend.
Example :
Hence, friend functions can access private data members by creating object of the class. Similarly we can also make function of other class as friend, or we can also make an entire class as friend class.
When we make a class as friend, all its member functions automatically become friend functions.
Friend Functions is a reason, why C++ is not called as a pure Object Oriented language. Because it violates the concept of Encapsulation.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.