Implementing Lists

To implement any data structure we must consider:

  1. storage medium:  in this course we will deal only with structures stored in memory;
  2. representation of information:  this is provided by the programming language used,  eg: Java;
  3. a way of reserving space for nodes: several possibilities are discussed below;
  4. an access mechanism with unique access paths: various different mechanisms will be discussed.
  5. implementation of the primitives: this follows from c and d, but there may  be alternatives.

The first notion to come to mind for data representation is an array, but this not very suitable as all the elements of an array must be of the same type.

A record provides a much more suitable storage structure.  A record can be defined as a collection of named attributes or fields.  In Java we can declare a record type, Booknode, as follows:

class Booknode {
   public String author;
   public String title;
   public String publisher;
   public int year;
   public int pages;
   public enum cover {PAPER, CLOTH}

This effectively defines a model or template for storage of the given type.  To reserve an area of storage of this type, we require a declaration, eg:

Booknode mybook = new Booknode;
Booknode yourbook = new Booknode;

To access individual fields or attributes within the record we qualify the record name with the field name, eg:

mybook.pages = 200;
yourbook.cover = PAPER;

The statement

mybook = yourbook;

copies all the fields of yourbook into the corresponding fields of mybook.

In order to have lists of records (not necessarily all with different names) we will consider the use of arrays of records.  This is sometimes referred to as the static of reserving space for nodes.  The required storage is usually decided in advance and one large array is declared to give enough space for all the required records.  If we assume that a constant size gives the total number of nodes required we can write a declaration of the form:

bookstore = new Booknode[20]; 

The access variable type in this implementation is integer, and the access mechanism is array subscripting, eg:


is a record.  To refer to a field within the record the dot notation is used, eg: