Chapter 16: An Introduction to Data Structures

Chapter Goals

• To be able to write programs with standard lists and iterators
• To understand the advantages and disadvantages of the list data structure
• To be able to implement linked lists
• To learn about stacks and queues
• To become familiar with common containers and algorithms from the Standard Template Library

Linked Lists

• Suppose you are maintaining a vector of sorted objects (such as employees)
  • Many elements will need to be shifted back if an new object is inserted in the middle.
  • Many elements will need to be shifted forward if an object is deleted from the middle.
• Moving a large number of records can involve a substantial amount of computer time.
• Rather than store a sequence of values in one long block of memory (like a vector or an array) a linked list stores each value in its own memory block, together with the locations of the neighboring blocks in the sequence.

Linked Lists

• Inserting an element into a list now requires no shifting, merely reassigning new locations to adjacent objects.

Linked Lists

• Removing an element from the list doesn't require shifts either.

Linked Lists

• The standard C++ library has an implementation of the linked list structure.
  • First we will learn how to use the standard list.
  • Later we will find out how to implement lists.
• Doubly linked lists (as shown in the illustrations) have links going in both directions.
• Singly linked lists only link elements in one direction.

Linked Lists

• Just like the vector, the standard list is a template.
• You can use push_back to add elements to the list.

  list<string> staff;
  
  staff.push_back("Cracker, Carl");
  staff.push_back("Hacker, Harry");
  staff.push_back("Lam, Larry");
  staff.push_back("Sandman, Susan");

• You cannot directly access elements using subscript access (e.g. staff[3]).
• Instead you must start at the beginning of the list, and visit each element in turn using a list iterator.

  list<string>::iterator pos;
  pos = staff.begin();
  

Linked Lists

• To move an iterator forward in the list, use the ++ operator.

  pos++;

• To move an iterator backward in the list, use the -- operator.

  pos--;

• You can find the value that is stored in the position with the * operator.

  string value = *pos;

• The value *pos represent the value that is stored in the list.

  *pos = "Van Dyck, Vicki";

• To insert another string before the iterator position, use the insert function.

  staff.insert(pos, "Reindeer, Rudolph");

Linked Lists

• Each list has an end position that does not correspond to any value in the list but that points past the list's end.

  pos = staff.end(); /* points past the end of the list */
  staff.insert(pos, "Yaglov, Yvonne");
     /* insert past the end of list */

• The end position does not point to any value, so you cannot look up the value at that position.

  string value = *(staff.end()); /* ERROR */

• Compare to accessing s[10] in a vector with 10 elements.

Linked Lists

• The end position is useful for stopping a traversal of the list.

  pos = staff.begin();
  while (pos != staff.end())
  {
     cout << *pos << "\n";
     pos++;
  }

• The traversal can be described more concisely with a for loop:

  for (pos = staff.begin(); pos != staff.end(); pos++)
     cout << *pos << "\n";

• Compare this to a traversal of a vector.

  for (i = 0; i < s.size(); i++)
     cout << s[i] << "\n";

• To remove an element from a list, you move an iterator to the position you want to remove, then call the erase function.

  pos = staff.begin();
  pos++;
  staff.erase(pos);

Linked Lists(list1.cpp)

Implementing Linked Lists (The Classes for Lists, Nodes, and Iterators)

• We will start with a linked list of strings.
• A linked list stores each value in a separate object called a node.

  class Node
  {
  public:
     Node(string s);
  private:
     string data;
     Node* previous;
     Node* next;
  friend class List;
  friend class Iterator;
  };

• The friend declarations indicate the List and Iterator member functions are allowed to inspect and modify the data members of the Node class.
• A class should not grant friendship to another class lightly, because it breaks the privacy protection.

Implementing Linked Lists (The Classes for Lists, Nodes, and Iterators)

• The list object holds the locations of the first and last nodes in the list.

  class List
  {
  public:
     List();
     void push_back(string s);
     void insert(Iterator pos, string s);
     Iterator erase(Iterator pos);
     Iterator begin();
     Iterator end();
  private:
     Node* first;
     Node* last;
  };

• When the list is empty the first and last pointers are NULL.
• A list object stores no data; it just knows where to find the node objects that store the list contents.

Implementing Linked Lists (The Classes for Lists, Nodes, and Iterators)

• An iterator denotes a position in the list.

  class Iterator
  {
  public:
     Iterator();
     string get() const;     /* use instead of * */
     void next();            /* use instead of ++ */
     void previous();        /* use instead of -- */
     bool equals(Iterator b) const; /* use instead of == */
  private:
     Node* position;
     Node* last;
  friend class List;
  };

• We will enable the operators ++, --, * and == in the next chapter.
• If the iterator points past the end of the list, then the position pointer is NULL.
• The iterator stores a pointer to the last element of the list, so that the previous method can move the iterator back from the past-the-end position to the last element of the list.

Implementing Linked Lists (Implementing Iterators)

• Iterators are created by the begin and end functions of the List class.

  Iterator List::begin()
  {
     Iterator iter;
     iter.position = first;
     iter.last = last;
     return iter;
  }
  
  Iterator List::end()
  {
     Iterator iter;
     iter.position = NULL;
     iter.last = last;
     return iter;
  }

Implementing Linked Lists (Implementing Iterators)

• The next function advances the iterator to the next position.

Implementing Linked Lists (Implementing Iterators)

• Note that it is illegal to advance the iterator once it is in the past-the-end position.

  void Iterator::next()
  {
     assert(position != NULL)
     position = position->next;
  }

• The previous function is similar.
• When the iterator points to the first element in the list, it is illegal to move it further backward.

  void Iterator::previous()
  {
     if (position == NULL)
        position = last;
     else
        position = position->previous;
     assert(position != NULL);
  }

Implementing Linked Lists (Implementing Iterators)

• The get function simply returns the data value of the node to which position points.

  string Iterator::get() const
  {
     assert(position != NULL);
     return position->data;
  }

• The equals function compares two position pointers.

  bool Iterator::equals(Iterator b) const
  {
     return position == b.position;
  }

Implementing Linked Lists (Implementing Insertion and Removal)

• For the push_back function, we must first make a new node.

  Node* newnode = new Node(s);

• The node must point back to the old end of the list, while the old end must point to it.

  newnode->previous = last;
  last->next = newnode;
  last= newnode;

• There is a special case when last is NULL (the list is empty).

  if (last == NULL)
  {
     first = newnode;
     last = newnode;
  }

Implementing Linked Lists (Implementing Insertion and Removal)

Implementing Linked Lists (Implementing Insertion and Removal)

• To insert an element in the middle of the list requires manipulating both elements on either side of the new node.

Implementing Linked Lists (Implementing Insertion and Removal)

• There is a special case when the list is empty.

  if (iter.position == NULL)
  
  {
     push_back(s);
     return;
  }

• Otherwise we create pointers to track the surrounding nodes.

  Node* after = iter.position;
  Node* before = after->previous;

• We tell the new node where it belongs in the list.

  newnode->previous = before;
  newnode->next = after;

• Then update the surrounding nodes.

  after->previous = newnode;
  if (before == NULL) /* insert at beginning */
     first = newnode;
  else
     before->next = newnode;

• When know that after is not NULL, but before could be.

Implementing Linked Lists (Implementing Insertion and Removal)

• As with insertion, we will need to work with both the element before and after the one to be removed.

Implementing Linked Lists (Implementing Insertion and Removal)

Of course we cannot remove a node that is not there.

assert(iter.position != NULL)

We create pointers to track all three nodes we need to work with.

Node* remove = iter.position;
Node* before = remove->previous;
Node* after = remove->next;

We disconnect the node to be removed from the one before it; note the special case when we delete from the front of the list.

if (remove == first)
   first = after;
else
   before->next = after;

We repeat the process with the node after the one to delete.

if (remove == last)
   last = before;
else
   after->previous = before;

Finally we delete the node.

delete remove;

Implementing Linked Lists (list2.cpp)

Stacks and Queues

• Stacks and queues are special data types that allow insertion and remove of items at the ends only, not in the middle.
• A stack lets you insert and remove elements at one end only, traditionally called the top of the stack.
• To visualize a stack, think of a stack of books.
• Since items can only be added or removed from the top of the stack, they are removed in the order that is opposite from the order they were added.
• This is called last in, first out or LIFO order.
• The addition and removal operations are called push and pop.

Stacks and Queues

• The is a stack template in the standard C++ library.

  stack<string> s;
  s.push("Tom");
  s.push("Dick");
  s.push("Harry");
  while (s.size() > 0)
  {
     cout << s.top() << "\n";
     s.pop();
  }

Stacks and Queues

• A queue is similar to a stack, except that you add items to one end of the queue (the back) and remove them from the other end of the queue (the front).
• To visualize a queue, think of people lining up.
• Queues store items in a first in, first out or FIFO fashion.
• The standard queue template implements a queue in C++.

  queue<string> q;
  q.push("Tom");
  q.push("Dick");
  q.push("Harry");
  while (q.size() > 0)
  {
     cout << q.front() << "\n";
     q.pop();
  }

Stacks and Queues (fifolifo.cpp)

Other Standard Containers

• The standard library contains several other useful containers.
• The set always keeps its elements in order, no matter in which order you insert them.

  set<string> s;
  
  s.insert("Tom");
  s.insert("Dick");
  s.insert("Harry");
  
  set<string>::iterator p;
  for (p = s.begin(); p!= s.end(); p++)
     cout << *p << "\n";

• The above code displays the strings in sorted order: Dick, Harry, Tom.
• The set data structure keeps the values in a special tree shaped structure; each time an element is inserted, the tree is reorganized.

Other Standard Containers

• The C++ set ignore duplicates; if you insert an element into the set that is already present, the insertion has no effect.
• The count function returns the number of times that an element is contained in a set (should always be 1).

  set<string> s;
  
  s.insert("Tom");
  s.insert("Tom");
  cout << s.count("Tom") << "\n"; /* displays 1 */

• If you want to be able to keep track of multiple occurrences of identical values, use a multiset instead.
• The count function works for multiset, with expected results.

  multiset<string> m;
  
  m.insert("Tom");
  m.insert("Tom");
  cout << m.count("Tom") << "\n"; /* displays 2 */

Other Standard Containers

• A map is similar to a vector, but you can use another data type for the indices.

  map<string, double> scores;
  scores["Tom"] = 90;
  scores["Dick"] = 86;
  scores["Harry"] = 100;

Standard Algorithms

• Why iterators?
• It is possible to supply generic functions that can carry out a task with the elements in any container that uses iterators.
• Example: The accumulate function can compute the sum of all elements in a vector or a list.

  vector<double> data;
  /* do something with data */
  
  double vsum = 0;
  accumulate(data.begin, data.end(), vsum);
  /* now vsum contains the sum of the elements in the vector */
  list<double> salaries;
  /* do something with salaries */
  
  double lsum = 0;
  accumulate(salaries.begin(), salaries.end(), lsum);
  /* now lsum contains the sum of the elements in the list */

Standard Algorithms

• The standard library also supplies a find algorithm.
• The find algorithm returns the second iterator if the search fails.

  /* search for a certain name on the staff */
  list<string>::iterator it =
     find(staff.begin(), staff.end(), name);

• The first two parameters can be other iterators for the list (if you don't want to search the entire list).

Standard Algorithms

• The standard library provides a wealth of ready-to-use and fully debugged data structures and algorithms.
  • for_each applies a function to each element
  • find (as above)
  • find_if locates the first element fulfilling a condition
  • count (as above)
  • equal tests if containers have the same elements in the same order
  • replace/replace_if replace all matching elements with a new one
  • unique remove adjacent identical values
  • min_element, max_element finds the smallest and largest elements
  • next_permutation rearranges the elements; call it n! times iterates through all permutations
  • sort sorts the elements; stable_sort performs better if the container is already almost sorted
  • random_shuffle randomly rearranges the elements
  • nth_element find the nth element without sorting the container.
  • plus many more...
• Before writing a lot of code from scratch, check whether the standard library already has what you need.