Lists as an ADT

Lists: An Introduction

So far we have studied the ADT containers: stack and queue. Another one of the major ADT containers is the list. As an abstract data type, a list is a finite sequence (possibly empty) of elements with basic operations that vary from one application to another. The list container has a lot of uses. We might want to have a list of customers, a list of dates, a list of grades, a list of students or a list of charges this month on your credit card.

The question then arises what are the basic operations that are needed for these lists. In general the basic operations for a list commonly include:

Construction:	Allocate and initialize a list object (usually empty to begin with)
Empty:	Check to see if the list is empty
Traverse:	Visit each item of the list in the order stored
Insert:	Add an item to the list (at any point)
Delete:	Remove an item from the list (at any point)

What you may notice from the statements of these basic operations is that they are similar to those of the stack and the queue. The major difference is that the insertions and deletions of these two containers are at the ends while the insertion and deletion of a list may be at any point in the list.

Not all lists have each of these features. The minimal requirements for a list are:

• Locate the first element.

• Given the location of any list element, find its successor.

• Determine if an element is at the end of the list.

There are several constructs that can be used as the basis for a list for example an array. For the array-based implementation, we would achieve these minimal requirements in the following manner:

• The first element is at location 0

• The successor of the item at location numb is at location numb + 1

• You are at the start of the list if the location is: -1

For a minimum implementation, we could use dynamic memory allocation and a class aList to define such a list as in the following:

 class aList {   private:     datatype *ptr;     long top;     long max;   public:     aList(long maximum)     {       max = maximum;       ptr = new datatype[max];       top = -1;     }     ~aList()     {        delete [ ] ptr;     }     void addTo(datatype value)     {       if(!is_full())       {          ++top;          *(ptr+top) = value;       }       else       {          max += 10;          datatype* new_ptr = new datatype[max];          for(long index=0;index<=top;++index)            *(new_ptr+index)= *(ptr+index);          ++top;          *(new_ptr+top) = value;          delete [ ] ptr;          ptr = new_ptr;       }     }     datatype showElement(long position)     {       datatype value;       if((position-1) > top)          throw position;       else         value = *(ptr + (position-1));       return value;     }     void showAll()     {       cout << "The elements in the list are the following:"            << endl;       for(short index=0;index<=top;++index)         cout << *(ptr+index) << endl;     }     bool isEmpty()     {       return(top==-1);     }     bool isFull()     {       return(top==(max-1));     } }; 

In the above example, notice in the member function addTo( ) how we had to create and delete memory when adding one more element would have exceeded the number of possible positions in the list. Notice how a temporary pointer was created to create a new container, then elements are transferred from the old array into the new array and finally the old container was destroyed. In addition notice that a destructor ~aList( ) was needed because each object created memory using the new operator. The destructor then used the operator: delete to destroy the array before the program ended. See alist.h for the header that contains the class aList and see list1.cpp for a program that implements a test of the class aList.

However suppose that you wanted to add two more features not listed above in the basic operations: i.e. insertion and deletion to the minimal requirements. For array based lists (like the dynamically defined array based implementation above), there is a gross inefficiency caused by insertion and deletion. This inefficiency is caused because these two processes may require that elements be shifted. That is, suppose you wanted value to be placed in the list between elements (ptr + numb) and (ptr + (numb+1)). In order to do this, we would have to do something like the following:

 for(short index=top; index > numb;--index)    *(ptr + (index+1)) = *(ptr + index); 

where top is the current number of elements in the array and top < max. Then we would need the following statements:

 ++top; *(ptr + (numb+1) = value; 

Similar types of statements would be needed for a deletion of say item: ptr + numb. In this case we would need something like the following:

 for(short index=numb;index<top;++index)   *(ptr + index) = *(ptr + (index+1)); 

and then we would need a statement like the following to complete our deletion:

 --top; 

To see the changes look at list2.cpp and anewlist.h

 Note:  There are other constructs that can be solutions to this problem. To be discussed later are: linked lists and the STL list.

Linked Lists

To overcome the problems of constructing a list discussed in the last section, we need to remove the requirement that the list elements be stored in consecutive memory locations as one would have for an array. What is needed would be a "link" that connects each element of the list to its successor. A way to do this would be to use a construct called a linked list. A linked list is an ordered collection of elements called nodes each of which has two parts:

Data part:	Stores an element of the list.
Next part:	Stores a link (pointer) to the next list element.

For those cases where there is no next element, we need a special NULL value. To implement these ideas, we could create a class node similar to the following:

 class node {   public:     datatype data;     node * next;     node(datatype value,node* ptr)     {       data = value;       next = ptr;     } }; 

 Note:  The class node could be replaced by a structure since all of the members are in the public access section. Frequently writers use the class construct rather than the structure when member functions are involved. However this is not a requirement.

Notice that the pointer next is defined in terms of the class node. Notice further that the member data and the pointer next are both in the public access section of the class because we will need to get access to them in our construction of the list below. Even though the data members are in the public access section, the constructor node( ) is needed because of the way the list will be created and the manner in which the nodes will be created with dynamic memory allocation.

In addition, we need an external link to be maintained that permits us to locate the node that is the first element of the list. The value of first will have the value NULL, if the list is empty. That is to start, we need:

 datatype* first; first = NULL; 

As the list begins to develop, the pointer first will be attached to the first node like the following:

 node* ptr1 = NULL; node node1(value1,ptr1); first = &node1; 

and the next pointer of node1 would have to be connected to NULL. However instead of this exact code, dynamic memory allocation will be used as you will see below.

Suppose we wanted to store as a linked list, the list of shorts 29, 17, 11, 24 and 34. The following graphic would be a pictorial representation of the linked list.

We now need to look at the Basic Operations for a list discussed previously and determine how they would be implemented for a linked list. The Basic Operations interpreted in a linked list would be:

Construction: Empty: Traverse:	first = NULL; return (first == NULL) ptr = first; while (ptr != NULL) { // Process data part of node pointed to by ptr; // where ptr = address of next element; // contained in the next part of node pointed to by ptr; }
Insert & Delete:	Both of these operations necessitate the changing of the links. For these operations, the address of the predecessor of the node needs to be added or removed using the operators new and delete.

To implement the first three of these features, we need a class node and a class List defined like the following:

 class node {   public:     datatype data;     node * next;     node(datatype value,node* ptr)     {       data = value;       next = ptr;     } }; class List {   private:     node* first;   public:     List()     {       first = NULL;     }     empty()     {       return (first==NULL);     }     display()     {        node * ptr = first;        while(ptr != NULL)        {          cout << ptr->data << endl;          ptr = ptr->next;        }     } }; 

Next we need to implement insertion into the linked list. We will consider three cases: (1) in the middle of the list, (2) at the end of the list and (3) at the beginning of the list.

1. Insertion in the middle: Suppose that we are going to insert a node with data: 20 after the node with data: 12 in the preceding linked list example.

First we need to find the node that contains 12. This could be done like the following:

 node * preptr = first; while(((preptr->next)!=NULL) && ((preptr->data)!=value))   preptr = preptr->next 

At this point, we now have preptr pointing to the node that contains 12 as the data.

Next we need to create a node to contain the new_value: 20. We do this by dynamically allocating an object of node with a statement like following:

 node * newptr = new node(new_value,preptr->next); 

Notice the two arguments of the node( ). The constructor is being used here. This statement not only dynamically creates the new node but initializes it as well. It assigns the node to have new_value (whose value is 20) for data but the next pointer will contain the address that the next pointer did for the node that contained 12.

To complete this process, the node that contains 12 needs to point to the node that contains 20. This would be accomplished by the following line:

 preptr->next = newptr; 

and finally putting these two together and checking to see if there is a node with the value needed, we would get:

 if((preptr->data)==value) {    node * newptr = new node(new_value,preptr->next);    preptr->next = newptr; } 

2. Insertion at the end: Next let's consider the same process at the end of the list, e.g. insert the new_value: 65 at the end. Following the pattern from the previous case we could have the following lines:

    node * newptr = new node(new_value,NULL); if(first!=NULL) {    node * preptr = first;    while((preptr->next)!=NULL)      preptr = preptr->next;    preptr->next = newptr; } else    first = newptr; 

The conditional was needed for the case where the list contained no elements.

3. Insertion at the front: For the last case, let's consider how we would insert the new_value: 25 at the beginning. This case would require the following code:

    node * newptr = new node(new_value,first); first = newptr; 

To complete our analysis we must consider how we would delete a node from a List. Again, we will consider three cases: (1) in the middle of the list, (2) at the end of the list and (3) at the beginning of the list.

1. Deletion in the middle: Suppose that we are going to delete the node with data: 12 in the preceding linked list example. We could first find the node like the following:

    node *ptr; node *preptr = first; while((preptr->next)!=NULL                   && (preptr->data)!=value)    preptr = preptr->next; ptr = preptr->next; if(ptr!=NULL && ((preptr->data)==value)) {    preptr->next = ptr->next;    delete ptr; } 

2. Deletion at the end: Suppose that we are going to delete the node with data: 65 in the preceding linked list example that was inserted at the end. We could first find the node, switch the previous pointer and then delete the memory. For example:

    if((first->next)==NULL) {    delete first;    first = NULL; } else {    node *ptr;    node *preptr = first;    while(((preptr->next)->next)!=NULL)      preptr = preptr->next;    ptr = preptr->next;    preptr -> next = NULL;    delete ptr; } 

In addition to the code above, it would also be necessary to check to see if the list is empty.

3. Deletion at the front: Suppose that we are going to delete the node with data: 25 in the preceding linked list example that was inserted at the beginning.

    node *ptr = first; first = first->next; delete ptr; 

In addition to the code above, this case would also require that the function check to determine whether the list is empty.

You will notice that each of the elements of the list was created dynamically. Therefore a destructor must be defined that deletes each element of the list prior to terminating the program. The destructor would look like the following:

 node * ptr; while(first!=NULL) { ptr = first;   first = first->next;   delete ptr; } 

Putting all of this code together should accomplish a minimal list. For a description of List see linked.h and for a description of the implementation program, see linked.cpp.

To make this example complete, additional member functions should be added. For example a constructor that has as arguments two pointers (to the same data type as the list) that point to beginning and the end of an array of nodes, a constructor that has as arguments a shortnumber (for the number of nodes to be added) and an element value (of the same data type as the list) that would make the list have number copies of the element value, a copy constructor and an assignment operator. For a self exercise, consider how each of these would be done.

Advantages and Disadvantages of a linked list:

Advantages of linked lists:

• store items "sequentially" without restrictions on location

• access to any item as long as an external link to first item is maintained

• insert a new item without shifting

• delete an existing item without shifting

• size can expand/contract throughout use

Disadvantages of linked lists:

• overhead of links: used only internally, pure overhead

• if the list is dynamic, then the code must provide a destructor and a copy constructor

• no longer have direct access to each element of the list

List-processing algorithms that require fast access to each element cannot (usually) be done as efficiently with linked lists, e.g.:

• Binary search

• Sorting

Stacks and Queues based upon Linked Lists

In the previous discussion we considered linked lists which consisted of a collection of nodes each of which was linked to the next node by a pointer. To traverse the list it was necessary to start at the pointer first and go in only one direction. In some applications it is desirable to have linked lists that permit the program to move in either direction. This can be done by including in a node a link not only to the successor node but one to the preceding node as well. This type of linked list is called a doubly linked list. This and other types of linked lists will be not considered in this lecture. However, this section will consider linked stacks and queues.

Our earlier introduction to stacks and queues was dependent on arrays. Having arrays as the basis for these containers restricted how they could be used. First there was a limit on the size of the containers and how new elements could be added. Additional there was wasted space in the container because when elements of the array were no longer needed they could not be eliminated and the memory could not be recovered. However these limitations are no longer a restriction with linked lists.

First let's consider the linked list as a basis for a stack. Recall from our previous discussion that a stack needs the following properties:

• Constructor: Initializes an empty stack.

• Empty operation: Determines if stack contains any values

• Full operation: Determines if the stack can hold any more elements.

• Push operation: Modifies a stack by adding a value to top of stack

• Top operation: Retrieves the value at the top of the stack

• Pop operation: Modifies a stack by removing the top value of the stack

What needs to be done is to determine how to implement these operations while using the linked list example as our basis.

Let's consider our linked list example from the previous chapter. Instead of using the pointer first, we can call it myTop to be consistent with our stack example. Therefore all occurrences of first will be replaced with myTop. In the constructor we would have:

 myTop = NULL; 

The linked list example had a function empty( ) to determine whether the list is empty and in our modification for the stack we need only to rewrite the function to check the truth value of the following:

 myTop == NULL; 

In our linked list implementation, the Full( ) operation will not be needed. This operation was only required because the basis for that stack was an array and we needed to ensure that we would not have stack overflow.

Since a stack is a LIFO container, our example will need to add the new nodes at the front. The function insert_front( ) from our linked list example can be renamed: Push( ) because they achieve the same goals. We can eliminate insert_middle( ) and insert_back( ), since they will not be needed for a LIFO container.

In our linked list example there was no member function equivalent to Top( ). Since the stack is LIFO, the function will need to return the first element of the linked list. Therefore we would need to write Top( ) like the following:

 datatype Top() {   return myTop->data; } 

Next we need to be able to remove nodes. In a LIFO container the first element must be removed. For this operation, the delete_front( ) function from the linked list example would achieve the same goal. Therefore, we can rename it: Pop( ). The function delete_back( ) and delete_middle( ) can be eliminated because they will not be needed.

The destructor needs to be included in this example of a stack although it was not required in the array based stack.

Using the same implementation program from the earlier stack example with only a few modifications, the example of a linked list stack would therefore be the program: stack1.cpp and the required header is: stack1.h.

Because this example is based on a linked list, the only modifications that are still needed for this example to be useful would be a copy constructor and an assignment operator. These two functions are required because of the nature of linked lists. The default copy constructor and the default assignment operator will produce inaccurate assignments so they must be replaced. I will leave that to you as a self exercise.

Now that we have used the linked list example to implement a stack, let's now look at what must be done to implement a queue as a linked list. First recall the basic operations of a queue from our previous discussion. A queue's basic operations are:

• constructor: Create an empty queue.

• empty: Check to see if the queue is empty.

• full: Check to see if the queue is full.

• add: Add a data item to the back of the queue.

• front: Retrieve the value of the data item from the front of the queue.

• remove: Remove the data item at the front of the queue.

As with the stack linked list above, what needs to be done is to determine how to implement these operations while using the linked list example as our basis.

The major difference between a stack and a queue is that a queue is a FIFO container. Because it is this type of container, the queue nodes need to be added to the back of the linked list and be removed from the front. The only difference between this example of a linked list and the one above for the stack will be that the member function for add( ) should use the linked list member function: insert_back( ). Otherwise these two linked lists are the same.

The following example uses the same implementation as the queue example in the array based example with a few modifications. As with the example for stack, the program does not need to determine whether the queue is full before inserting additional nodes. See the implementation program: queue1.cpp and the header: queue1.h. As with the stack example above, this example should include a copy constructor and an assignment operator.

If the queue has a large number of nodes, the function Push( ) has to work too hard. It has to move the pointer all the way from myTop to the last node. A modification that would make this process work more efficiently would be to add an additional pointer: myBack as a data member so that it would point to the last node. This approach would require modifications to the definition of the class to add the new data member myBack and to the member functions: Queue( ) and Push( ).

The constructor Queue( ) would be modified as in the following:

 Queue() {   myTop = myBack = NULL; } 

The member function: Push( ) would be modified as in the following:

 void Push(datatype new_value) {   node * newptr = new node(new_value,NULL);   if(!empty())   {      node * preptr = myBack;      preptr->next = myBack = newptr;   }   else      myTop = myBack = newptr; } 

The implementation would remain the same. The only change required would be in the header file. See queue2.h.

In an earlier discussion of queues, a model for the queue was as a circular array. A similar circular model for a queue can be based upon a linked list. For this case, the next pointer of the last node would point to the first node rather than to the NULL pointer. If the queue only had one node, then this sole node would point to itself. The circular queue model would change the structure of the queue class discussed above (the first example of a queue based on a linked list.) The changes would require that the member functions: ~Queue( ), display( ), Pop( ) and Push( ) be rewritten to reflect this different point of view. To observe the changes, see: queue3.h. The implementation does not need to be changed.