CS170 Lab: C++ Doubly Linked Lists

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.


Advantage of Doubly Linked Lists.

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.

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;

struct LinkNode;
typedef LinkNode* Node_Ptr;

struct LinkNode
{
    Element_Type data_member;
    Node_Ptr    flink_member;
    Node_Ptr    blink_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.

Operations on Linked Lists.

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.

Lab Exercise -- C++ Simple Linked Lists


CS Dept Home Page
CS Dept Class Files
CS170 Class Files

This page last modified: Friday, 21-Sep-2012 18:14:52 CST
Copyright: Department of Computer Science, University of Regina.