Working with Doubly-Linked Lists

On this page, we'll be working with doubly-linked lists. Most of the techniques useful for working with singly-linked lists, what we just called "linked lists" before, also work well for doubly-linked lists. This is because a doubly-linked list is just an augmented singly-linked list. Each node in a doubly-linked list not only has a pointer to the next node in the list but also another pointed to the previous node in the list.

We'll again work with lists of numbers and so use the following definition for our nodes (from DLList.h):

//A node in a doubly-linked list.
struct DLNode {
    //The value of this Node.
    int data;
    
    //The previous Node in the list,
    //NULL if there is no such node, ie,
    //if this is the first Node in the list.
    DLNode* previous;
    
    //The next Node in the list,
    //NULL if there is no such node, ie,
    //if this is the last Node in the list.
    DLNode* next;
};

Using just this definition, how could you create the list (1 2)?

DLNode* head = new DLNode;
head->data = 1;
head->previous = NULL;

DLNode* last = new DLNode;
last->data = 2;
last->previous = head;
last->next = NULL;

head->next = last;

How could you create the list (7 7 7)?

Iterating over doubly-linked lists

We may iterate forwards over a doubly-linked list the same way as we did with a singly-linked list:

for (DLNode* current = head; head != NULL; current = current->next) {
    //Do stuff.
}

However, each node's pointer back to the previous element opens up new possibilities. With doubly-linked lists, we can just as easily traverse a list backwards as forwards:

//Iterate backwards over a list:
//last is the last element of the list.
for (DLNode* current = last; last != NULL; current = current->previous) {
    //Do stuff.
}

For example, here is a function that counts the number of even numbers in a list by going backwards over the elements of a list.

//Pre: last points to the last element of a valid list.
//Post: Returns the number of even numbers in the list.
int countEvens(DLNode* last)
{
    int count = 0;
    Node* current = last;
    while (current != NULL) {
        if ((current->data % 2) == 0) {
            ++count;
        }
        current = current->previous;
    }
    return count;
}

Here is a function that goes backwards over a list. It takes each number, converts it to a char, then prints it out to the given ostream. For example, if x is ('g' 'n' 'o' 'e' 'y' 'n' 'A'), reversePrintChar(x, out) prints Anyeong on out.

//Pre: out is not errored and last points to an
//element in a valid list.
//Post: Print the char values of each element of the list
//to out in reverse order.
void reversePrintChar(DLNode* last, ostream& out)
{
    for (DLNode* current = last; current != NULL; current = current->previous) {
        out << static_cast<char>(current->data);
    }
}

Problems

1. Write a function that takes the last element of a list and counts the number of elements equal in value to that last element. If the list is empty, ie, the last element is NULL, the count is 0.

2. Write a function that deletes the elements of a list given the list's last element.

Answers

Recursion

We can also recurse both forwards and backwards (basically as we can iterate forwards and backwards over a list). However, note that unlike with singly-linked lists, the next node in a doubly-linked list is never a list. Only the first element of the list is a list because the head of a doubly-linked list must have its previous link equal to NULL. This is only true for the first element of any linked list. Therefore, doubly-linked lists are not recursive data structures. The implications of this are especially important when we are building lists.

Recursing over doubly-linked lists

//Pre: aNode is an element in a valid list.
//Post: Returns the number of nodes from aNode back to the
//head of the list, inclusive. For example, if x is the node
//for 2 in the list (1 2 3), reverseLength(x) returns 2.
//reverseLength(NULL) is 0.
int reverseLength(DLNode* aNode)
{
    if (aNode == NULL) {
        return 0;
    }
    else {
        return 1 + reverseLength(aNode->previous);
    }
}

Here's a function that computes the product of all the nodes previous to and including the given one. We define the product of the empty list to be 1:

//Pre: aNode is an element in a valid list.
//Post: Returns the product of the nodes previous to and including aNode.
//Returns 1 if aNode is the empty list.
int reverseProduct(DLNode* aNode)
{
    if (aNode == NULL) {
        return 1;
    }
    else {
        return aNode->data * reverseProduct(aNode->previous);
    }
}

Here's a function that tests whether the portions of the two lists from the given nodes back to the heads of the lists are equal. For example, if x is the node for 2 in (3 1 2) and y is the node for 2 in (3 1 2 4), reverseEquals(x, y) returns true:

//Pre: node1 and node2 are elements in valid linked lists.
//Post: Returns true if the portions of the linked lists
//from node1 back to its list's head and from node2 back
//to its list's head are equal.
bool reverseEquals(DLNode* node1, DLNode* node2)
{
    if (node1 == NULL) {
        if (node2 == NULL) {
            return true;
        }
        else {
            return false;
        }
    }
    else if (node2 == NULL) {
        return false;
    }
    else {
        return node1->data == node2->data
                && reverseEquals(node1->previous, node2->previous);
    }
}

Problems

3. Write a recursive function that takes the last element of a list and tests whether every element is >= 0. Return true if every element is >= 0, false otherwise. If the list is empty, return true. (Why do we define the answer to be true for the empty list?)

4. Write a recursive function that takes the head of one list and the last element of another and tests whether one list is the reverse of the other. For example, if x is head of the list (1 2 3) and y is the last element of the list (3 2 1), your function should return true if given x and y as arguments.

Answers

Building doubly-linked lists iteratively

//Post: Creates the list consisting of aNumber repeated
//count times. Sets the parameter head to the head of the new list
//and last to the last element in the new list.
//If count <= 0, head and last are set to NULL,
//the empty list.
//For example, repeat(5, 3, h, t) creates the list (5 5 5) and leaves
//h equal to the first 5's node and t equal to the last 5's node.
//
//Modifies: head and last
void repeat(int aNumber, int count, Node*& head, Node*& last)
{
    head = NULL;
    last = NULL;
    for (int i = 0; i < count; i++) {
        DLNode* next = new DLNode;
        next->data = aNumber;
        next->previous = last;
        if (head == NULL) {
            head = next;
        }
        else {
            last->next = next;
        }
        last = next;
        last->next = NULL;
    }
}

Note that we return a pointer to the last element. We do this because with doubly-linked lists, because with doubly-linked lists, a pointer to the last element is often useful.

The general pattern for building a doubly-linked list iteratively (given head and last is to

1. Set head and last to NULL.
2. If you are finished building the list, stop.
3. Create a new Node.
4. Set the new node's data.
5. Set the new node's previous link to last. (This works even if the new node is the first node in the list because we initialized last to NULL.)
6. If head is NULL, the new node is the first node in the list. Set head equal to the new node.
7. Otherwise, hook up last to the new node.
8. The new node is now the last node in the list, so set last equal to it.
9. Since there is nothing after the last node yet, set last's link next equal to NULL.
10. Go to step 2.

Problems

5. Implement the function with the following prototype:

//Post: Creates the list of the integers from
//low up to high inclusive and stores the list's head
//in the parameter head and its last element in
//the parameter last.
//If low > high, sets head and last to NULL,
//the empty list.
//For example, createRange(1, 5, h, t) creates the list
//(1 2 3 4 5) and sets h to the node for 1 and t to
//the node for 5.
//For example, createRange(3, 2, h, t) sets
//h and t to NULL.
//
//Modifies: head and last
void createRange(int low, int high, DLNode*& head, DLNode*& last)

Answers