## Highlights of this lab:

In this lab,  you will:

## Lab Exercise:

Click the little computer above for a detailed description.

NOTE: There will be questions on the lab test based on the lab material.

If you need help during the week, you are welcome to go to CL119 during Office Hours posted for lab instructors.

We worked on singly linked list last week. Now let's look at the doubly linked list this week. For some problems, the singly linked list is too restrictive. One difficulty with the singly linked lists is that if we are poiting to a specific node, say p, then we can move only in the direction of the links. The only way to find the node that preceds p is to start at the beginning of the list. If you want to delete a node, you need to know the preceding node or previus node. With a doubly linked list, we can move in either direction instead of only one direction.

Each element in a linked list is referred to as a node. In a doubly linked list, each element consists of three members.

• Data member - contains the data
• Link member - contains the pointer to the next node
• Link member - contains the pointer to the previous node
Here is an example to show you how to use a STRUCT to define a node.
```/*************************************************
*   FileName: ~ftp/pub/class/170/ftp/cpp/dllist.h
*   Purpose:  header file for llist.cpp
*************************************************/
typedef int Element_Type;

{
Element_Type data_member;
};

```
The last node in any linked list contains a null pointer in the forward link member. This null pointer is used to determine the end of the list. The following diagram illustrates a doubly linked list.

What follows here, are very rough algorithms on the basic operations that you would perform on a linked list. In actually implementing list operations, you would have to consider conditions such as: Is the list empty? What happens if I get to the null pointer and haven't found a data member that is supposed to be in the list? The algorithms here are just to provide you with an overview of the concepts involved in simple operations. Creating a dummy node which is pointed by the head pointer would bring you lot's of convenience in inserting a node or deleting a node.
• Creating a List
```            First create a new empty node as a dummy node.
Set up a current-pointer to the dummy node.
Get a data value for the first node.
Create a new node.
Assign a data value to the new data member.
Set the current-pointer's forwards link member to this new node.
Set the new node's backwards link member to the current node.
Bump the current-pointer to this new node.
Set the forward link member of the last node to NULL.
```
```                  Find the end of the list.
i.e. Set current-pointer to the head.
While current-pointer link member not NULL
bump the current-pointer.
Create a new empty node.
Assign a data value to the data member of that node.
Set the forwards link member of the new node to NULL. (New tail.)
Set the new node's backwards link member to current node.
Set the current-pointe's forward link member to the new node.
```
• Printing Nodes
```                  Set the current-pointer to the head node.
Until you hit a null pointer:
print the data member of the current node
bump the pointer to the next node.
```
• Inserting Nodes
This algorithm assumes that you want to insert a node into a list of ordered values. Let's say you have two values, 12 and 24. A new value of 14 should be inserted between these existing values so that the final list will contain the values 12, 14, and 24.
```
Get the value to insert.
Create a new node.
Assign a data value to the data member of that node.
Set a previous-pointer to NULL.
Set a current-pointer to the Head.
While the new data member > current-pointer value
Bump both pointers along to the next nodes.
i.e.
make the previous-pointer point to the current-node
change the current-pointer to point to the next node
Set the forward link member in the previous_pointer to the new node.
Set the backward link member in the new node ito the previous_pointer node.
Set the forward link member of the new node to the node pointed
Set the backward link member of the current node to the new node.
```
This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.
• Deleting Nodes.

This routine assumes that the item you are searching for is, in fact, in the list.

```          Get the data value to delete.
check from the current node pointed by the current-pointer.
Until the target is found.
Change the link of the backward and forward pointers
to the link of the item to be deleted.
Delete the node.
```
This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.

## Lab Exercise -- C++ Simple Linked Lists

• Transfer the dllist.cpp dllist.h files from the CS Dept's anonymous ftp site to your Hercules account space. Do that by:
1. Entering the commands:
``` cp /net/data/ftp/pub/class/170/ftp/cpp/dllist.cpp dllist.cpp
cp /net/data/ftp/pub/class/170/ftp/cpp/dllist.h dllist.h
```
2. OR, by doing a copy and paste from the screen to an edit session,
3. OR, by using the command line FTP program using this information:
The path: pub/class/170/ftp/cpp
The files: dllist.cpp, dllist.h

The purpose of the program is to demonstrate operations on a doubly linked list.

• Examine the header file and the program carefully.

• With the experience of singly linked list from last week's lab, now you should be ready to start adding code to the program DLlist.cpp.
• First, add the code to print out the doubly linked list as indicated in the comments in the program. (There is an outline for a PRINT function at the end of the file. Just add the while loop to it.)
• Compile and run this C++ program.

• Now add the code to add a single node to the end of the list.
• Compile and run this C++ program.

• Add the code to delete a node from the list.
• Compile and run this C++ program.