Lists (Contiguous and Linked)
An Introduction with Examples in C++ |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
Values: | Elements of any type. | |||||||||||||||||||||||||||||||||
Operations: |
|
#ifndef edu_jmu_cs_Node_h #define edu_jmu_cs_Node_h #include <stdlib.h> /** * A Node (containing int values) in a linked list. * * @author Prof. David Bernstein, James Madison University */ template<class E> class Node { public: /** * Default constructor. */ Node(void); private: int element; Node<E> *next; friend class List; }; template<class E> Node<E>::Node(void) { element = NULL; next = NULL; } #endif
#ifndef edu_jmu_cs_List_hpp #define edu_jmu_cs_List_hpp #include "Node.hpp" /** * A linked implementation of a list * * @author Prof. David Bernstein, James Madison University */ template<class E> class List { private: E length; Node<E> *first; public: /** * Default Constructor. */ List(void); /** * Destructor */ ~List(void); /** * Insert an element * * @param index The index of the element * @param value The value to insert */ void insert(const int index, const E value); /** * Is this List empty? * * @return true if this List is empty; false otherwise */ bool isEmpty(void); /** * Remove an element * * @param index The index of the element to remove */ void remove(const int index); /** * Retrieve an element of the list * * @param index The index of the element to retrieve * @return The element */ E retrieve(const int index); /** * Return the size of the list * * @return The size */ int size(void); }; template<class E> List<E>::List(void) { first = NULL; length = 0; } template<class E> List<E>::~List(void) { Node<E> *current, *next; current = first; for (int i = 0; i < length; i++) { next = current->next; delete current; current = next; } first = NULL; length = 0; } template<class E> void List<E>::insert(const int index, const E value) { int i, result; Node<E> *newNode, *tmp, *prev; newNode = new Node<E>(); newNode->element = value; // If this index makes sense if (index <= length) { i = 0; prev = NULL; tmp = first; // Find the element with this index while (i != index) { prev = tmp; tmp = tmp->next; i++; } newNode->next = tmp; if (prev == NULL) first = newNode; else prev->next = newNode; length++; } } template<class E> bool List<E>::isEmpty(void) { return (length == 0); } template<class E> void List<E>::remove(const int index) { int i, result; Node<E> *tmp, *prev; // If this index is in the list if (index < length) { i = 0; prev = NULL; tmp = first; // Find the element with this index while (i != index) { prev = tmp; tmp = tmp->next; i++; } // The first node is a special case if (prev == NULL) { first = tmp; } else // Other nodes { prev->next = tmp->next; } delete tmp; length--; } } template<class E> E List<E>::retrieve(const int index) { E result; int i; Node<E> *tmp; // If this index is in the list if (index < length) { i = 0; tmp = first; // Find the element with this index while (i != index) { tmp = tmp->next; i++; } result = tmp->element; } else { result = NULL; } return result; } template<class E> int List<E>::size(void) { return length; } #endif