Linked Lists
P.J. Drongowski
27 October 2004

What is the nature of a list?

  * A list denotes membership (an item on a list is a member of the list)
  * A list may denote an ordering relationship between members
    + An item may follow another item
    + An item may precede another item
  * There are two distiguished members of a list
    + The first member (no other members precede it)
    + The last member (no other members follow it)

Using an array to represent a list

  * The precedes and follows relationships are implicit based upon
    position in the array, i.e., the member at i precedes the member at i+1
  * Placement in the array implies one of these relationships
  * There is a first member and a last member
    + The first member is usually at the lowest index
    + The last member is usually at the highest index
  * Disadvantages
    + Size of the list must be known in advance
    + Consider deletion or insertion: the other list members must be shuffled

Using a linked list to represent a list

  * Can use dynamic storage -- the list can grow/shrink as necessary
  * Don't need to shuffle members
  * Cannot access members randomly -- must traverse (walk) the list from
    the beginning to reach interior members

Linked list diagrams

  * Diagrams like the one below are used to visualize linked lists

      ---------      ---------     ---------
     | 45 |  -----> | 65 | -----> | 76 |NULL|
      ---------      ---------     ---------

  * Remember Dilip's rule! What do the boxes and arrows mean?
    + Each box is a node in a directed graph
    + The arcs (arrows) denotes the follows relationship between two nodes
    + This is a simple form of a graph and is "linear" in shape
  * Unlike arrays, linked lists explicitly represent the arrangement of
    list members
  * Representation in C/C++
    + Boxes are aggregated data items (either an object or a struct)
      - The first subbox holds the value associated with the node
        and is called the "data part"
      - The second subbox holds a pointer value, which points to the
        next node in the list
        * This pointer value represents the follows relationship
        * It is sometimes called the "next part"
      - The special pointer value NULL marks the end of the list
    + Pointers naturally represent the directed arcs in a graph
      - A pointer is inherently one-way
      - Can be used to represented directed arcs in complex graphs
    + A pointer to the first member of the list must also be maintained

C++ provides two ways to represent a node: struct and class

  * This file contains two example programs
    + class_list.h / class_list.cpp uses a class to define nodes
    + struct_list.h / struct_list.cpp uses a struct to define nodes
      - It also uses "free" functions to define the operations
      - It is an example of pure C programming (no use of classes at all!)

          typedef struct _Node {
            int data ;
            struct _Node *next ;
          } Node, *PtrNode ;

          class Node {
          public:
            int data ;
            Node *next ;
          } ;
          typedef Node *PtrNode ;

  * The struct representation is an alternative approach to using a private
    class to define linked list nodes

Minimum set of operations [Nyhoff]

  * Construction
  * Locate the first member
  * Given the location of any list member, find its successor
  * Locate the end of the list

Approach

  * Our goal is define an abstract datatype (ADT) with the operations:
      List() ;                   // List constructor
      List(const List &old) ;    // Copy constructor
      ~List() ;                  // Destructor
      void prepend(int value) ;  // Add value to front of the list
      void append(int value) ;   // Add value to end of the list
      void print() ;             // Display the list
  * The abstraction provided by the ADT is a list of values
  * The list and values must be represented in some way
    + Each value will be stored in a "Node," where a Node has two parts:
      - A value (integer in this case, but could be a string, ...)
      - A pointer to the next Node in the list (representing the "follows"
        relationships between the Node and the Nodes following it in the list
    + Nodes will be dynamically allocated and deleted as needed
    + A pointer to the first Node in the list will be needed to remember
      where the list is in memory
    + A count will be kept to remember the number of Nodes in the list
      (just a handy thing to have)

class_list.h (See full code below)

  * Declares the public method functions for the list operations
  * The private part of the class declaration declares:
    + A private class called "Node" to represent list Nodes
      - A Node has an integer member "data" to hold a data value
      - A Node has a pointer to the next Node in the list
      - The Node constructor zeroes the data member and sets the next
        pointer to NULL; NULL will be used to represent "end of list"
    + A private datatype "PtrNode" to represent pointers to list Nodes
    + A PtrNode "first" to point to the first Node in the list
    + An integer "length" to remember the number of Nodes in the list

List::List()

  * Constructor for a List object
  * Sets the pointer first to NULL signifying an empty list
  * Sets the length to zero

List::List(const List &old)

  * Copy constructor for a List object
  * When using dynamic storage, the programmer is responsible for making
    copies of any dynamically allocated data items
  * This constructor is invoked when a copy of a List object must be created
  * It copies over the length
  * It allocates and makes an exact copy of the original list (old)

List::~List()

  * Destructor for a List object
  * When using dynamic storage, the programmer is responsible for releasing
    (deallocating) storage when done with it
  * Steps through the linked list and deletes each Node
  * It takes care to remember the pointer to the next Node before
    deleting it

void List::prepend(int value)

  * Adds a new Node to the beginning of the list
  * Performs these steps
    + Allocates a new Node using new
    + Sets the data member of the new Node to value
    + Sets the next member of the Node to the first Node in the current list
    + Makes first point to the new Node
    + Increments the length by one

void List::append(int value)

  * Adds a new Node to the end of the list
  * Performs the following steps
    + Allocates a new Node
    + Sets the data member of the new Node to value
    + Set the next member of the new Node to NULL; the new Node will be
      the new end of the list
    + Handles two cases:
      - The empty list: Just adds the new Node to the list by making
        first point to the new node
      - A non-empty list: Scans through the list to find the last Node;
        Adds the new node after the current last Node

void List::print()

  * Prints the values in the list from front to back
  * Use the working pointer (pn) to traverse the list, Node by Node
  * Walks the list until it hits the end (the working pointer is NULL)
  * Prints each data value as it encounters them

****************************************************
Example C++ code: class_list.h
****************************************************

#ifndef CLASS_LIST_H
#define CLASS_LIST_H

class List {
public:
  List() ;                   // List constructor
  List(const List &old) ;    // Copy constructor
  ~List() ;                  // Destructor

  void prepend(int value) ;  // Add node to front
  void append(int value) ;   // Add node to end
  void print() ;             // Display the list

private:
  class Node {
    public:
      int data ;
      Node *next ;
      Node() { data = 0 ; next = NULL ; }
  } ;

  typedef Node *PtrNode ;

  PtrNode first ;
  int length ;
} ;

#endif


****************************************************
Example C++ code: class_list.cpp
****************************************************

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

#include "class_list.h"

List::List()
{
  first = NULL ;
  length = 0 ;
}

List::List(const List &old)
{
  PtrNode pn, opn, plast ;

  first = NULL ;
  length = old.length ;
  plast = NULL ;

  for (opn = old.first ; opn != NULL ; opn = opn->next) {
    pn = new Node() ;
    pn->data = opn->data ;
    pn->next = NULL ;
    if (first == NULL) {
      first = pn ;
    } else {
      plast->next = pn ;
    }
    plast = pn ;
  }
}

List::~List()
{
  PtrNode pn, pnn ;

  for (pn = first ; pn != NULL ; pn = pnn) {
    // Remember next node before delete current node
    pnn = pn->next ;
    // Deallocate the current node
    delete pn ;
  }
}

void List::prepend(int value)
{
  PtrNode pn ;

  pn = new Node() ;
  pn->data = value ;
  pn->next = first ;
  first = pn ;

  length += 1 ;
}

void List::append(int value)
{
  PtrNode pNew, pS ;

  pNew = new Node() ;
  pNew->data = value ;
  pNew->next = NULL ;

  if (first == NULL) {
    first = pNew ;
  } else {
    for (pS = first ; pS->next != NULL ; pS = pS->next) ;
    assert(pS->next == NULL) ;
    pS->next = pNew ;
  }

  length += 1 ;
}

void List::print()
{
  PtrNode pn ;

  for (pn = first ; pn != NULL ; pn = pn->next) {
    cout << pn->data << endl ;
  }
}


****************************************************
Example C-style code using structs: struct_list.h
****************************************************

typedef struct _Node {
  int data ;
  struct _Node *next ;
} Node, *PtrNode ;


****************************************************
Example C-style code using structs: struct_list.cpp
****************************************************


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

#include "cstruct_list.h"

// Create and add a new node for value at
// the end of the list. Return a pointer to
// new first element in the list
PtrNode prepend(PtrNode pList, int value)
{
  PtrNode pNode ;

  pNode = new Node() ;
  pNode->data = value ;
  pNode->next = pList ;

  return(pNode) ;
}

// Create and add a new node for value at
// the end of the list. Return a pointer to
// the first element in the list
PtrNode append(PtrNode pList, int value)
{
  PtrNode pNew, pNode ;

  pNew = new Node() ;
  pNew->data = value ;
  pNew->next = NULL ;

  if (pList == NULL) {
    pList = pNew ;
  } else {
    pNode = pList ;
    while (pNode->next != NULL) {
      pNode = pNode->next ;
    }
    assert(pNode->next == NULL) ;
    pNode->next = pNew ;
  }

  return(pList) ;
}

void print_list(PtrNode pList)
{
  PtrNode pn ;

  for (pn = pList ; pn != NULL ; pn = pn->next) {
    cout << pn->data << endl ;
  }
}

int main(int argc, char *argv[])
{
  int i ;
  PtrNode pList, pNode ;

  // User must provide at least one argument
  if (argc < 2) {
    cerr << "Too few arguments" << endl ;
    exit( 1 ) ;
  }

  // Initialize the list pointer and the
  // pointer to the last node to NULL
  pList = NULL ;

  // Make a list of the integer provided
  // on the command line

  for (i = 1 ; i < argc ; i++) {
    pList = append(pList, atoi(argv[i])) ;
  }

  // Print the list
  print_list(pList) ;
}