List

Values:	Elements of any type.
Operations:	Name/Operator Arguments Returns Constructor A new instance. insert element The element to insert into the list index The position of the new element isEmpty true if the list is empty and false o/w remove index The position of the element retrieve index The position of the element The element at the specified position size The number of elements in the list

• Approach:
  • Use an array
• An Observation:
  • Many operations require shuffling

cppexamples/linkedlist/Node.hpp

#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
        

cppexamples/linkedlist/List.hpp

#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
        

• Traditional Pointers:
  • When we use traditional pointers in a linked list we are pointing to an absolute address
• An Alternative Approach:
  • Use an offset from the current memory location (i.e., a relative address
• Where this Might Arise:
  • An array based implementation that uses relative indexes

• Are there other operations that you would include?
• Where might you use operator overloading?
• Could you create an ADT that provides the services of a stack, queue, and list?