Section 1 - Introduction to Linked Lists

7A.1.1 Overview

ADTs and Our Old Stack

In a prior week, you learned what a stack data structure was, and how to build one using inheritance. A stack is a kind of abstract data type, or ADT, since the pictures and operations that involve a stack can be described without reference to any particular language. Pushing to and popping from a stack are well understood no matter what programming language we decide to implement them in. So the stack was our first ADT.

One might argue that an array was also a kind of ADT, and one would have a point. Arrays are usually called vectors, informally, when discussed in terms of ADTs, but we'll wait a few minutes before we introduce the vector vocabulary, so just put that thought aside for the moment.

A New ADT: the List

In the first part of the week, we will meet our second, formal ADT, the linked list, or simply list. Lists are ubiquitous in computer science, so mastering their implementation and use is essential. We'll do this in this first lesson and do so in a way that parallels how we used inheritance to implement queues that can be used for a variety of data types.

STL Templates

In the second half of the week, we move forward to the C++ standard template library (stl).  The stl allows us to use certain built-in data structures (ADT)s, which are pre-designed; each ADT implemented in C++ is called a class template. The exciting thing about these templates is that they are type-neutral. We can use them to create, say, a stack of ints, a stack of Cards or a stack of Lizards, and do so in a single statement: no new classes or methods to write. Nothing to extend or inherit. As long as there is a stack template available for us, we can use it immediately.

Additional References on Vectors and Other STL "Containers"

7A.1.2 A General Linked List

We present a similar example to the list-based stack of a previous lesson, but now we  produce a more general linked list.

There are a few properties that distinguish a general linked list (or just list) from a stack data structure. The most important aspect of a stack is that there should only be one way to access data from it: pop(). If you want to get the top of the stack, you pop an item off, and then you can use it.

If you wish to store items in a list and access them, for example, by running through the list, visiting each list node one-at-a-time, without removing anything from the list, then you are no longer in a stack scenario.   For that we need a general linked list..

A list looks a lot like a stack in one respect:  it is made up of individual nodes that contain next pointers, and each node in a list points to its successor: 

head → ln1 → ln2 → ln3 → ln4 → null

The last node in the list has a null in its next field, which is how we know it is the end of the list.  The head is simply a pointer to the first Node.

With a stack we always pushed new items onto the top of the list.  So if we instantiated a new node lnNew, and pushed it onto the stack it would go at the top,  Here is the stack after a stk.push(lnNew):

head → lnNew → ln1 → ln2 → ln3 → ln4 → null

With general linked lists we insert rather than push, and we can insert anywhere.  To do that, we have to specify the node after which we want to insert the new node lnNew.   Let's say we want to insert after node ln3 in the original list.  We would design and use an insertAfter() method.  The before and after pictures of the list would be:

List before insertAfter( ...): 

head → ln1 → ln2 → ln3 → ln4 → null                                ^   Insert lnNew after ln3 here /  \

List after insertAfter(...): 

head → ln1 →  ln2 →  ln3 → lnNew → ln4 → null

So you can see that the only Nodes that need be changed in the list are ln3 and lnNew:

  1. We had to modify the next member of ln3 to point to lnNew, instead of ln4.  
  2. We also had to set lnNew's next field to point to ln4.

This suggests that we could place the insertAfter() method in the ListNode class, the building block class, rather than the higher level List class. And that is what we shall do.

7A.1.3 The Node Class

Here is the prototype and implementation of the "ListNode" class (which we will wisely call simply Node, because we can use it for more than just Lists).  We have made next private and not allowed a mutator for this class.  Only the friend class List may access it.  This is a security issue because we will be building lists with Nodes created and handed to us by our client, at least initially.  This means the client can "handle" the actual nodes in our list.  We want to reduce the likelihood that a malicious client will modify the next member of a node and thus destroy our list (can you see how that would be a potential problem?)   In a moment we will add some security by removing getNext() (since it won't be needed and it exposes our future List class), but for a simple test main() of the Node class we'll keep it in play.  We also declare the (to be written) List class to be a friend of the Node class, enabling all List methods access to Node's private data (namely, next).

Prototype:

// Node prototype --------------------------------
class Node
{
  friend class List;
private:
  Node *next;

public:
  Node();
  virtual ~Node();
  virtual void show();
  void insertAfter(Node *newNode);
  Node *removeAfter();
  Node *getNext();
};

Implementation:

// Node method definitions --------------------------
Node::Node()
{
  next = NULL;
}

Node::~Node()
{
  // nothing to delete
}

void Node::show()
{
  cout << "(generic node) ";
}

void Node::insertAfter(Node *newNode)
{
  if (!newNode)
    return;
  newNode->next = next;
  next = newNode;
}

Node *Node::removeAfter()
{
  Node *temp = next;

  if (temp != NULL)
    next = temp->next;
  return temp;
}

Node *Node::getNext()
{
  return next;
}

// end Node method definitions ---------------------

7A.1.4 A Test Client and Run

To test the class we use this main():

#include <iostream>
#include <string>
using namespace std;

// main method ---------------------------------------
int main()
{
  Node n1, n2, n3, *np;

  n1.insertAfter(&n2);  // insert n2 after n1
  n2.insertAfter(&n3);  // insert n3 after n2

  for (np = &n1; np; np = np->getNext())
    np->show();

  return 0;
}

Which produces this result

console shot