Singly Linked-Lists Top Stacks Contents

Doubly Linked-Lists

Synopsis

A double linked-list is a more versatile version of a singly linked-list. A doubly linked-list node has two node pointers, conventionally named next and prev. As the names imply, it is possible to move from the head node to the tail (via the next pointer) as well as from the tail node to the head (via the prev pointer). The major import of this ability is that the tail pointer can be reset in constant time for both adding to the back and removing from the back.

By making the doubly-linked list circular, the tail pointer can be dispensed with. Here is an illustration of circular doubly-linked list with six nodes:

The double-ended arrows indicate both next and prev pointers are present. The next pointers proceed counter-clockwise in the illustration, while the prev pointers proceed clockwise. To find the last node, one follows the prev pointers from the head node one step.

A doubly linked-list also benefits from a dummy head node as well as a dummy tail node.

Structure

The structure is the same as that of singly linked-lists:

    class doubly-linked-list
        {
        var head = null;        //pointer to the first/leftmost node
        var tail = null;        //optional: pointer to last/rightmost node
        var size = 0;           //optional: holds net number of nodes added
        // operations
        ...
        }

The difference is in the type of nodes comprising the lists. A doubly linked-list uses nodes with two node pointers.

Vocabulary

The terms used in describing an doubly linked-list are identical to those of a singly linked-list and a node.

Supports

Doubly linked-lists are used as a basis for advanced data structures such as binomial and fibonacci heaps.

Dependencies

Doubly linked-lists are implemented using nodes. with a two node pointers, typically named next and prev.

Operations

The operations of a doubly linked-list are very similar to that of singly-linked lists. An additional complication is that the prev pointers need to updated consistently.

As stated early, a node previous to the last node can be found in constant time by following the prev pointer of the last node. This is useful for resetting the tail pointer when deleting from the back of the list.

Traversals

A doubly linked-list can easily be traversed from the tail to the head by following prev pointers from the tail node.

Traversing the list in this direction takes Θ(n) time.

Concept Inventory

     
  1. This is a question.
    1. This is one possible answer
    2. This is another possible answer

lusth@cs.ua.edu


Singly Linked-Lists Top Stacks Contents