Example of Linked List as Template

Example of Linked List as Template.

This code was compiled and tested on a Linux machine

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

List.cc:

#ifndef LIST_CC
#define LIST_CC

#include <iostream>

using namespace std;

template <typename T>
class Node {

	public:

		// Create a linked list node by setting its data to the input parameter
		// and the next node in the linked list to NULL (0)
		Node(const T& data_input);

		//The default constructor doesn't initialize the data members
		Node();

		//The default destructor doesn't initialize the data members
		~Node();

		// Contains the data of the linked list node
		T data;	

		// Contains a pointer to the next item in the linked list
		Node<T> *next;

		// Contains a pointer to the previous item in the linked list
		Node<T> *previous;

};

template <typename T>
class List {
	private:

		// Contains a pointer to the first node in the
		// linked list (the head of the list)
		Node<T> *head;	

		// Contains a pointer to the last node in the
		// linked list (the head of the list)
		Node<T> *tail;

		int num_elements;

	public:

		// Create a Linked list by initializing it's head to NULL (0)
		List(void);

		List(const List<T>& list);

		// Delete all the elements in the linked list when the list is deleted
		~List(void);

		bool isempty() const;

		// Takes an item as a parameter, appends that item to
		// the front of the list, and returns the list
		List<T> *addtofront(const T& data_input);

		// Takes an item as a parameter, appends that item to
		// the back of the list, and returns the list
		List<T> *addtoback(const T& data_input);

		// Returns a pointer to a copy of the first item in the list,
		// leaving it in the list
		Node<T> *getfirst() const;

		int size() const;

		// Takes no parameters, and returns a list containing
		// all but the first element of the list
		List<T> *getrest() const;

		// Print all the elements in the linked list
		void show();

};

// -------------------------------------
// ------------Node class---------------
// -------------------------------------

//
// Create a linked list node by setting its data to the input parameter
// and the next node in the linked list to NULL (0)
template <typename T>
Node<T>::Node(const T& data_input) {

   data = data_input;

    next = NULL;

    previous = NULL;

}

// Default constructor leaves data items unspecified
template <typename T>
Node<T>::Node() {

    next = NULL;

    previous = NULL;
}

// Default constructor leaves data items unspecified
template <typename T>
Node<T>::~Node() {
}

// -------------------------------------
// ------------List class---------------
// -------------------------------------

//
// Default constructor creates an empty list
//
template <typename T>
List<T>::List(void) {

    head = NULL;

	tail = NULL;

    num_elements = 0;

}

template <typename T>
List<T>::List(const List<T>& list){

    if ( list.head != NULL ){

		Node<T> *current_node = list.head;

		while (current_node != NULL){

			addtoback(current_node->data);

			current_node = current_node->next;

			num_elements++;
		}
	}
}

//
// Delete all the elements in the linked list when the list is deleted
//
template <typename T>
List<T>::~List(void) {

   Node<T> *next_node;

    Node<T> *current_node = head;

    while (current_node != NULL) {

       	next_node = current_node->next;

        delete(current_node);

        current_node = next_node;

    }	

}

template <typename T>
bool List<T>::isempty() const{
	return((num_elements < 1));
}

template <typename T>
int List<T>::size() const{
	return num_elements;
}

// Takes an item as a parameter, appends that item to
// the front of the list, and returns the list
template <typename T>
List<T> *List<T>::addtofront(const T& data_input){

    Node<T> *new_node;

    new_node = new Node<T>;

    new_node->data = data_input;

	// If list_head == 0 then assign new_node as the list_head
	// else point new_node->next to list_head. After make that
	// new node the list_head
    if (head == NULL) {

        head = new_node;

        tail = new_node;

    } else {

        new_node->next = head;

        head = new_node;	

    }

    num_elements++;

	return (this);
}

// Takes an item as a parameter, appends that item to
// the back of the list, and returns the list
template <typename T>
List<T> *List<T>::addtoback(const T& data_input){

    Node<T> *new_node;

    new_node = new Node<T>;

    new_node->data = data_input;

    if (tail == NULL) {

        tail = new_node;

	    if (head == NULL) {

	        head = new_node;

	    } else {

	        new_node->next = head;

	        head = new_node;	

	    }

    } else {

		tail->next = new_node;

		new_node->previous = tail;

		tail = new_node;

    }

    num_elements++; 

    //delete(new_node);

	return (this);
}

// Returns a pointer to a copy of the first item in the list,
// leaving it in the list
template <typename T>
Node<T> *List<T>::getfirst() const{
	return (new Node<T>(head->data));
}

// Takes no parameters, and returns a list containing
// all but the first element of the list
template <typename T>
List<T> *List<T>::getrest() const{

	List<T> *rlist = new List<T>();

	Node<T> *current_node;

	if (head->next != NULL){

		current_node = head->next;

		while (current_node != NULL){

			rlist->addtoback(current_node->data);

			current_node = current_node->next;
		}
	}

	return (rlist);
}

//
// Print all the elements in the linked list
//
template <typename T>
void List<T>::show() {

    cout << 'List of ' << num_elements << ' elements: ' ;

    Node<T> *current_node = head;

    while (current_node != NULL) {

        cout << current_node->data << ' ';

        current_node = current_node->next;

    }

    cout << endl;
}

#endif

MainDriver.cpp

#include <iostream>
#include <string>
#include 'List.cc'

using namespace std;

template <typename T>
List<T> *reverse(List<T>& list);

int main (int argc, char *argv[]) {

	List<string> my_list;

	List<string> *my_list_2;

	cout << endl << 'BUILD ORIGINAL---------------------------' << endl;

	my_list.addtoback('one(1)');
	my_list.addtofront('nine(9)');
	my_list.addtoback('eight(8)');

	my_list.show();

	cout << endl << 'REVERSE ORIGINAL---------------------------' << endl;

	my_list_2 = reverse<string>(my_list);

	cout << endl << 'New: ';

	my_list_2->show();

	delete my_list_2;

	return 0;
}

// Write a templated reverse() function
// (not a member function of your class, but instead
// a standalone templated function)
// that operates on a doubly linked list object
// (that you implemented for Part 1).
// Your reverse function should take as input a
// doubly linked list object,
// and return a copy of the list,
// but in reverse order. 

// Your function must be recursive,
// and must use the four functions above.

// A reversed list can be built by taking an element off one side,
// reversing the list without that element in it,
// and then putting that element back into the list,
// on the other side.... use that reasoning to design your recursive
// reverse function. 

template <typename T>
List<T> *reverse(List<T>& list){		

	if (list.size() < 1){

		List<T> *rlist = new List<T>;

		return (rlist);

	}else{

		Node<T> *node;

		List<T> *rlist = new List<T>;

		node = list.getfirst();

		rlist = list.getrest();

		rlist = reverse<T>(*rlist);

		rlist->addtoback(node->data);		

		delete (node);

		return (rlist);
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share

Example of Linked List

Example of Linked List

This code was compiled and tested on a Linux machine

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

List.h:

#include <iostream>
using namespace std;

#ifndef LIST
#define LIST

typedef int ElementType;

class Node {
   public:

   // Create a linked list node by setting its data to the input parameter
   // and the next node in the linked list to NULL (0)
   Node(ElementType data_input);

   //The default constructor doesn't initialize the data members
   Node();

   // Contains the data of the linked list node
   ElementType data;	

   // Contains a pointer to the next item in the linked list
   Node *next;
};

class List
{
   private:

      // List class's private data member:
      Node *list_head;	// Contains a pointer to the first node in the
                        // linked list (the head of the list)

      int num_elements;

      // takes out the node with the smallest data member from this list,
      // and returns a pointer to it.
      Node *extractLargest(); 

   public:
      // Create a Linked list by initializing it's head to NULL (0)
      List();

      // Delete all the elements in the linked list when the list is deleted
      ~List();

      // Add a single element to the head of the linked list
      void insert(ElementType data_input);

      // Remove a single element from the head of the linked list
      void remove();	

      // Print all the elements in the linked list
      void show();

      // This function splits the list in half, adding the those half of
      // the elements with the largest values into a new linked list, and
      // keeping only those half of the elements with the smallest values
      // in the list on which this function is called. The function
      // returns a pointer to the new (heap allocated) list with the 
      // larger elements in it. If the original list contains an odd 
      // number of elements, then the returned list contains one
      // fewer element than the list on which this function is called.
      // If the original list is empty, the function returns a pointer
      // to a new empty List (not a NULL pointer).
      List *splitBigSmall();

      // This function splits the list in two, adding the the elements
      // with odd integer values into a new linked list, and keeping only
      // those elements with even integer values in the list on which
      // this function is called. The function returns a pointer to
      // the new (heap allocated) list with the odd elements in it. If the
      // original list is empty, or if there are no odd elements, the
      // function returns a pointer to a new empty List (not a NULL
      // pointer). 
      List *splitOddEven();
};

#endif

List.cpp:

#include 'List.h'

#include <string>

using namespace std;

// -------------------------------------
// ------------Node class---------------
// -------------------------------------

// 
// Create a linked list node by setting its data to the input parameter
// and the next node in the linked list to NULL (0)
Node::Node(ElementType data_input) {

    data = data_input;

    next = 0;

}

// Default constructor leaves data items unspecified
Node::Node() {
}

// -------------------------------------
// ------------List class---------------
// -------------------------------------

//
// Default constructor creates an empty list
//
List::List() {

    list_head = NULL;

    num_elements = 0;

}

//
// Delete all the elements in the linked list when the list is deleted
//
List::~List() {

    Node *next_node;

    Node *current_node = list_head;

    while (current_node != NULL) {

        next_node = current_node->next;

        delete(current_node);

        current_node = next_node;

    }	

}

//
// Add a single element to the head of the linked list
//
void List::insert(ElementType data_input) {

    Node *new_node = new Node(data_input);

	// If list_head == 0 then assign new_node as the list_head
	// else point new_node->next to list_head. After make that 
	// new node the list_head
    if (list_head == 0) {

        list_head = new_node;

    } else {

        new_node->next = list_head;

        list_head = new_node;	

    }

    num_elements++;

}

//
// Remove a single element from the head of the linked list
//
void List::remove() {

    if (list_head == NULL)
        return;	

	// Make new_head the node that is pointed by list_head->next
    Node *new_head = list_head->next;

	// Delete the node list_head 
    delete(list_head);

    //Make the new_head, the new list_head
    list_head = new_head;

    num_elements--;

}

//
// Print all the elements in the linked list
//
void List::show()
{

    cout << 'List of ' << num_elements << ' elements: ' ;

    Node *current_node = list_head;

    while (current_node != NULL) {

        cout << current_node->data << ' ';

        current_node = current_node->next;

    }

    cout << endl;
}

//
// splitOddEven()
//
List *List::splitOddEven()
{

	List *rlist = new List();

	if (num_elements > 0){

		Node *current_node = list_head;

		while (current_node != NULL){

			if (current_node->data % 2 == 1){

				rlist->insert(current_node->data);

				if (current_node == list_head){

					current_node = list_head->next;

					remove();

					current_node = current_node->next;

				}else{

					Node* previous_node = list_head;

					while (previous_node->next != current_node){
						previous_node = previous_node->next;
					}

					previous_node->next = current_node->next;

					// Delete the node list_head 
					Node *temp = current_node;
					current_node = current_node->next;
				    delete(temp);

					num_elements--;

				}

			}else{

				current_node = current_node->next;
			}
		}

	}
    return(rlist);

}

//
// extractLargest()
//
Node *List::extractLargest()
{

	Node *current_node = list_head;

	Node *largest_node = list_head;

	if (list_head != NULL){

		// Search Largest
		while(current_node != NULL ){

			if (largest_node->data < current_node->data){
				largest_node = current_node;
			}

			current_node = current_node->next;
		}

		current_node = largest_node;

		if (current_node == list_head){

			current_node = list_head->next;

			current_node = list_head;

			list_head = list_head->next;

		}else{

			Node* previous_node = list_head;

			while (previous_node->next != current_node){
				previous_node = previous_node->next;
			}

			previous_node->next = current_node->next;

		}

		//delete(current_node);

		num_elements--; 
	}

	return (largest_node); 
}

//
// splitBigSmall()
//
List *List::splitBigSmall()
{	
	List *rlist = new List();

	int numExtract;

	numExtract = num_elements / 2;

	if (num_elements > 0){

		Node *current_node = list_head;	

		//	2a. If original list have odd number of elements	
		//		then return list with larger elements in it, 
		//		should contain  one fewer element than 
		//		the list obj which this function is called.
		// 		This is already done by the division

		for (int i = 0; i < numExtract; i++){

			current_node = extractLargest();

			if (current_node != NULL)
				rlist->insert(current_node->data);

			//delete (current_node);
		}
	}

   return(rlist);

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share

Code Examples in C++

Here are some code examples written in C++
Even do they are written in C++, I would advice to compile them in Linux as I did. If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. I do not take responsibilities of how they are used.

Share