CSCI-1200 Computer Science II
Summer, 2002
Worksheet 16
;''Introduction to Linked Lists

Reading: Deitel & Deitel 15.1 - 15.4

One of the Abstract Data Types discussed in the previous worksheet was a List (often called a sequence), an ordered set of elements.

So far, the only implementation of the ADT List that we have discussed is an array implementation, in which adjacent elements in the sequence are store in adjacent memory. There is another, very different implementation of a sequence, called a linked list, in which adjacent elements are not necessarily stored in adjacent memory. Rather, each element in the list has a pointer to the memory location where the next element is stored. Typically, whenever a new element is added to the list, new memory is obtained from the heap to store this element.

A trivial example of a linked list is a shopping list. Here is some code to create a linked list of items that we need to buy at the grocery store. The first step in creating a linked list is generally to define a class called a node which contains all of the information for a particular element in the list, plus a pointer to the next element. The type of next is a pointer to a node.

class node {
public:
    char element[32];
    node *next;
    node () { }           // default constructor
    node(char *value) {   // another constructor
       strcpy(element, value);
       next = NULL;
    }
};

List nodes are usually drawn like this:

Now let's define a class shoppinglist. We only need one private data member, a pointer to the head of the list. Notice that this one pointer points to a list of arbitrary length. Each item in the linked list consists of a node containing an element of the sequence and a pointer to the next node. We signify the end of the linked list by setting the next field of the last node in the list to NULL.

We will also define two member functions, a constructor function which sets head to NULL; and a member function void Insertathead(char newelement[]) which inserts a new node at the head of the list, with the value newelement.

#include "node.h"
class shoppinglist {
private:
   node *head;
public:
   shoppinglist() {head = NULL;} // constructor
   void Insertathead(char newelement[]) {
        node *temp;
        temp = new node(newelement); // initializes node with data passed in
        temp->next = head;
        head = temp;
   }
};

Here's what Insertathead does. We want to add a new element at the head of the list, so we allocate memory for a new node using new. The pointer variable temp points to this memory, that is, it contains the address of the new node. We copy the food item to the element field of temp. Since we are inserting the new element at the head of the list, we set the value of the next field of temp to the old head, and then set head to temp. Initially, head is NULL, so the value of the next field is set to NULL. If the first food to be inserted is Apples, the list can be diagrammed like this after this function call.

If you have difficulty understanding this code, try substituting numbers for addresses. A call to new returns an address. Suppose that the address returned is 4800. This means that the variable temp has the value 4800. Initially, head has the value 0 (NULL). Thus, the line
temp->next = head
says, ``Set the next field at the node at address 4800 to the value of head (which is 0)''. The line
head = temp;
says ``Assign the value of temp (4800) to the variable head.'' Thus, head now has the value 4800, the address of the new node.

Let's add Burritos to the list by calling the Insertathead function. We make a call to new to get memory for a new node. Suppose this call returns the address 5100. Now temp has the value 5100. We copy the string ``Burritos'' to the element field using the strcpy function. We then set the value of the next field in the node at address 5100 to the value of head which is 4800. Finally, we set the value of head to the address of temp, which is 5100. Our list now looks like this:

The variable head has the address 5100, the address of the node containing Burritos. The next field of this node has the value 4800, the address of the node containing Apples. The next field of the Apples node has the value NULL.

Suppose the next item to be inserted is Carrots. We call new to get memory for a new node, and suppose that the memory is at address 4600. This is the value of temp. We copy Carrots to the element field of the node at address 4600, set the value of its next field to the current value of head (5100, the address of the Burritos node, and then set the value of head to 4600, the address of the Carrots node. Our list now looks like this:

This is how linked lists are typically diagrammed, but the list looks like this in the physical memory of the computer.

address	xx00 - xx31	xx32
4500
4600	Carrots	5100
4700
4800	Apples	0
4900
5000
5100	Burritos	4800
5200

Notice that the only way to get to a node in the center of the list is to start at the head and traverse the list, one link at a time. To print out all of the elements of a linked list, create a variable iterator of type node* which is initially set to head. Using a while loop, print out the value of the element field of the node at the address of iterator, and then set the value of iterator to its own next field. Continue this until iterator has the value NULL.

Exercise 1: Write a member function void printlist() which prints out the elements in the list, one per line. Here is some code to test your function: (All code for this worksheet is in the directory \dept\cs\cs2\wksht16).

#include "shoppinglist.h"
main()
{
     char *food[] = {"Apples", "Burritos", "Carrots", "Dog food",
                    "Eggs","Fudge"};
     shoppinglist thingstobuy;
     for (int i=0;i<6;i++)
         thingstobuy.Insertathead(food[i]);
     thingstobuy.printlist();
}

Note that this will print the items in the reverse order from the order in which they were inserted because each item is inserted at the head of the list.

To find a particular element in a linked list, it is necessary to traverse the list in order (linear search). This is $O(n)$. This is no less efficient than a linear search of an array.

Exercise 2: Write a member function node *find(char target[]) which returns a pointer to the node corresponding to the item target. If there is no node with the value target in the list, it should return a NULL pointer. This will entail moving along the list with an iterator until either the correct node is found (remember to use the strcmp function) or the end of the list is reached.

Here is some code to test your function.

#include "shoppinglist.h"
main()
{
     char *food[] = {"Apples", "Burritos", "Carrots", "Dog food",
                    "Eggs","Fudge"};
     shoppinglist thingstobuy;
     for (int i=0;i<6;i++)
         thingstobuy.Insertathead(food[i]);
     node *temp;
     char *morefood[] = {"Dog food", "Apples", "Fudge", "Guacamole"};
     for (i=0;i<4;i++) {
          temp = thingstobuy.find(morefood[i]);
          if (temp != NULL)
              cout << "We found " << temp->element << endl;
          else 
              cout << morefood[i] << " is not in the list" << endl;
     }
}

It may seem as though linked lists are a lot of work, but they have a major advantage over implementing a list in an array; inserting a new element in the middle of the list is quite easy. To insert a new element into an array, it is necessary to copy every element above the new element up by one, and this can be very time consuming for a large list. This algorithm is $O(n)$ - it increases linearly with the number of elements in the array. The algorithm for inserting a new node into a linked list after a node is a constant time algorithm $O(1)$, i.e., insertion is independent of the number of elements in the array. Here is the algorithm:

   allocate memory for a new node
   copy the new value(s) into the element field of the new node
   set the value of the next field of the new node to the value
       of the next field of the previous node
   set the value of the next field of the previous node to
       the address of the new node

This can be diagrammed as follows. Suppose our list looks like this:

We would like to insert a new node with the string eggs after dog food and before fudge.

Following our algorithm, we get space for a new node using new. Assume that the address of this new memory is 5000. Copy the string eggs to the element field of this node.

Next, we copy the value of the next field of the dog food node to the next field of the new node. (This is a pointer to the fudge node).

Finally, set the value of the next field of the dog food node to the address of the new node. The list now looks like this.

Exercise 3: Write a member function
void InsertNode (node *before, char element[])
which inserts a new node containing the string element after the node before in the list.

Deleting from a linked list can also be done in constant time. The only tricky part is that you need a pointer to the predecessor node, i.e, the node which directly precedes the node to be deleted. All you have to do is to change the value of the next field of the predecessor node to the value of the next field of the node that you want to delete, and then return the memory for the node that was just deleted to the heap using the delete statement.

Here is the algorithm:

   Find the node where the value of the node pointed to by its "next"
       field is equal to the element to be deleted.
   Save a pointer to the node to be deleted in a temporary variable
   Set the value of the next field of the predecessor node to the value
       of the next field of the node to be deleted.
   Return the memory used by the deleted node to the heap.

Suppose we want to delete the eggs node from the above list. If we have a temp pointer to the dog food node, all that needs to be done to delete eggs from the list is to set the next field of the dog food node to point to the fudge node. The list can be diagrammed like this:

The only other thing that needs to be done is to delete the memory allocated for the eggs node.

Exercise 4: Write a member function int deletenode(char element[]) which deletes the node from the list where the string value is element. It returns 1 if the delete was successful and 0 if there was no node with the string value element in the list.

If you were writing a program that required using the ADT sequence, when would you use an array implementation, and when would you use a linked list implementation? The answer depends on the frequency of the various operations that would be done. In any application where inserting new elements into the middle of a sequence is commonly done, a linked list implementation would be preferred. One example would be a word processing program of some sort. Suppose you have a file consisting of 1,000 lines of text, and you would like to insert some new lines into the middle. Clearly, storing each line of text into an array of lines would be terribly inefficient, while storing each line as a node in a linked list would make insertions and deletions very fast. On the other hand, if you will hardly ever be inserting new elements into the middle of the sequence, or if you will be doing a lot of random access (e.g. "What is the 345th element in the sequence?") an array implementation is more efficient.

Strong suggestion: It is easy to get your pointers confused and tangled when working with linked lists. Always start by making a drawing of how your list is supposed to look. Diagram every step of what your function is supposed to do, as you are coding it. Keep the diagrams handy so you can refer to them when debugging. Make use of the debugger to step through the function. You can type expressions like head, temp->element, and temp->next into the Watch window to help you see which nodes have what values and where they are pointing.

Template linked lists

The examples in this worksheet did not use templates in order to keep the code as simple as possible. However, writing a template linked list class is not difficult. Here is the code for the node class:

template <class T>
class node {
public:
    T element;
    node<T> *next;
    node () {next = NULL; }           // default constructor
    node(T item) {   // another constructor
         element = item;
         next = NULL;
    }
};

and here is the code for the linkedlist class. Remember that if your type T is a class type, you may need overloaded operators to use your class inside a template class.

template <class T>
class linkedlist {
private:
   node<T> *head;
public:
   linkedlist() {head = NULL;} // constructor
   void Insertathead(T item) {
        node<T> *temp = new node<T>(item);
        temp->next = head;
        head = temp;
   }
};

The remaining member functions can be implemented similarly.

Once you have a template class, you can use it to create linked lists that hold any type of data, e.g.:

int main()
{
   linkedlist<int> intlist;
   linkedlist<soda> sodalist; // user-defined `soda' class
...

Doubly Linked Lists

One problem with the linked list implementation that we discussed above is that it is only possible to move in one direction in the list; there is no way to go backwards. There is a simple solution to this, a doubly linked list. Each node of a doubly linked list has two pointers, one to the next node in the list and one to the previous node. This makes it possible to traverse a list in either direction easily. Inserting new nodes and deleting nodes from this list requires a little more work though.

A node might be defined like this:

template <class T>
class Node
{
public:
   T data;
   Node<T> *next, *prev;
   Node(){ next = prev = NULL;} // default constructor
   Node(T Item) {
       data = Item;
       next = prev = NULL;
   }
};

A node of this type can easily be drawn in this way:

Typically the prev field of the first node in the list is set to NULL. and the next field of the last element of the list is set to NULL. This means that you have to check whether these fields are NULL before trying to access them in order to avoid crashing your program.

As before, a Doubly Linked List would have only a single private data member, a pointer to the head, although it might have a pointer to the tail as well.

Here is the code for deleting a node from the list. The item to be deleted is passed as an argument; the function returns true if the node was deleted and false if there was no such node in the list. Note that you first have to check to see if the node to be deleted is the first node of the list (the head), and if it is, this must be treated as a special case.

 1  bool DeleteNode(T Item)
 2  {
 3      Node<T> *iterator = head;
 4      Node<T> *tobedeleted = NULL;
 5      if (head == NULL) return false;
 6      if (head->data == Item) {
 7         tobedeleted = head;
 8         if (head->next != NULL) {
 9              head->next->prev = NULL;
10         }
11         head = head->next;
12      }
13      else {
14          while (iterator->next != NULL) {
15              if (iterator->next->data == Item) {
16                  tobedeleted = iterator->next;
17                      if (tobedeleted->next != NULL) {
18                        tobedeleted->next->prev = iterator;
19                      }   
20                  iterator->next = tobedeleted->next;
21                  break;
22              }
23              else iterator = iterator->next;
24          } // end of while
25      } // end of else
26      if (tobedeleted != NULL) {
27           delete tobedeleted;
28           return true;
29      }
30      else return false;
31  }

Let's go through this code line by line:
1 bool DeleteNode(T Item)
2 {
3 Node<T> *iterator = head;
Create an iterator which will advance through the list to find the item be be deleted.
4 Node<T> *tobedeleted = NULL;
Create a pointer which will point to the node to be deleted. This is initialized to NULL because we haven't found the node yet.
5 if (head == NULL) return false;
If the list is empty, return false.
6 if (head->data == Item) {
Check to see if the node to be deleted is the first item in the list (the head). This is a special case which must be treated differently.

7 tobedeleted = head;
8 if (head->next != NULL) {
9 head->next->prev = NULL;
10 }
11 head = head->next;
12 }
Set tobedeleted to head, and if the next item in the list is not NULL, set its prev so it points to NULL, because this will become the new head. Then set head so that it points to the next item. Note that this works even if the next item is NULL.
13 else {
14 while (iterator->next != NULL) {
If the node to be deleted is not the head, find the node to be deleted by moving the iterator along the list. Note that we will stop when iterator is pointing to the node preceding the node to be deleted.
15 if (iterator->next->data == Item) {
We have found the node to be deleted. It is the node after iterator.

16 tobedeleted = iterator->next;
17 if (tobedeleted->next != NULL) {
18 tobedeleted->next->prev = iterator;
19 }
Set tobedeleted to the node to be deleted. If the node's next pointer is not NULL (i.e. it is not the last node in the list), set the prev pointer of the successor node to point to the iterator. Note the syntax here; there are two arrow operators.
20 iterator->next = tobedeleted->next;
Make the next pointer of iterator skip the node being deleted.
21 break;
Since we have found what we are looking for, break out of the while loop.
22 }
23 else iterator = iterator->next;
24 } // end of else
25 } // end of while loop
Move the iterator pointer to the next node and go back to the while loop test.
26 if (tobedeleted != NULL) {
27 delete tobedeleted;
28 return true;
29 }
30 else return false;
If tobedeleted is not NULL, return the memory to the heap with delete and return true. If it is NULL, we did not find the node to be deleted, so return false.

Here is the algorithm to insert a new node into a doubly linked list, assuming that you have the address of the predecessor node:

   1.  Allocate new memory for the node
   2.  Copy the data to the data area of the node
   3.  Set the next field of the new node to the value of the next  
       field of the predeccesor node
   4.  Set the prev field of the new node to the address of the
       predecessor node
   5.  Set the value of the prev field of the successor node
       to the address of the new node
   6.  Set the value of the next field of the predecessor node to
       the address of the new node

Exercise 5: Define a template class doublylinkedlist. As with a singly linked list, your class should have two private data members node *head and node *tail. The class should have the following public member functions.

• doublylinkedlist() a constructor which sets head to NULL.
• void InsertAtHead(T elt) which inserts a new node with the value elt at the head.
• void InsertAtTail(T elt) which inserts a new node with element elt at the end of the list.
• node<T> *find(T elt) returns a pointer to the first instance of a node in the list with the value elt. If there is no node with element elt in the list, return NULL.
• void insertafter(node<T> *n, T elt) inserts a new node after the node pointed to by n.
• node<T>*forward(node <T> *n) return a pointer to the node immediately after the node pointed to by n. (Note: technically this is not necessary, because you could just get the value of $n->next$, but this is a preferred way to advance through the list. Note that this will return NULL if n points to the last node in the list.
• node<T>*back(node <T> *n) return a pointer to the predecessor node of n in the list. Note that this will return NULL if n points to the first node in the list.
• node<T>*first() returns a pointer to the first item in the list.
• bool deletenode(T elt) (Provided for you)

There is some code to test your class in the file
/dept/cs/cs2/wksht16/main.cpp

Copy Constructors and Destructors of Linked Lists

Writing a copy constructor or a destructor for a linked list is not a trivial exercise. For the copy constructor, it is necessary to iterate through the list to be copied, allocate new memory for each node, and set the pointers properly. The code for the overloaded assignment operator would be the same.

To write a destructor for a linked list, you need to return each node to the heap.