Nodes Top Doubly Linked-Lists Contents

Singly Linked-Lists

Synopsis

A linked-list is one of the more important data structures in computer science, having a wide application in a number of situations. Linked-listes are usually constructed from nodes, each node having a single node pointer. The nodes are chained together with this node pointer. For example, if the node pointer is named next and the variable a points to the first node in the chain, the subsequent nodes in the chain could be accessed with the expressions:

    a.next;             //the second node
    a.next.next;        //the third node
    a.next.next.next;   //the fourth node

Pictorially, a linked-list is often represented with a box-and-pointer diagram, where each box represents a node and where a downward arrow represents a value pointer and a rightward arrow represents the next node pointer:

To improve performance when adding a new element to the rear of the list, a tail pointer can be used. The tail pointer is set to always point to the last node in the list:

Structure

    class singly-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
        ...
        }

Vocabulary

The terms used in describing an singly linked-list are:

chain
A series of nodes linked using a single node pointer
head of the list
The first/leftmost value stored in the list.
tail of the list
The list minus the first/leftmost node.
head pointer
A component of the list that points to the first/leftmost node in the list. When the list is empty, the head pointer has a value of null. The head pointer serves as the data structure's store.
tail pointer
An additional component of the list that points to the last/rightmost node in the list. When using a tail pointer, it is imperative to remember to set the tail pointer to null whenever and however a list becomes empty.
index
An index is an integer value used to indicate a particular node in the list. The first node has index 0, the second has index 1, and so on.
size
The number of nodes in the list. Also called length.
dummy head node
A device to simplify the add-to-front operation. A dummy node is a node with no value. When using a dummy head node, the head pointer always points to this node, even if the list is empty. The first/leftmost node follows the dummy head node. The size of the list does not include the dummy head node.
walking a list
Traversing the list, usually from the head node to the tail node.
link
A node in the list is often called a link.

Supports

Singly linked-lists are used as a basis for:

If a tail pointer is implemented, then a singly linked-list can be used as a basis for a queue.

Dependencies

Singly linked-lists are implemented using nodes. with a single node pointer, typically named next.

Operations

add-to-front

The add-to-front operation is quite simple. It simply points the head to a new node whose next pointer points to the old head:

    function add-to-front(value)
         {
         head = new node(value,head);
         }

However, if the list incorporates a dummy head node, the add-to-front function becomes:

    function add-to-front(value)
         {
         head.next = new-node(value,head.next);
         }

If a tail pointer is used, the tail pointer must be set the newly created node if the list was empty prior to the addition.

This operation takes Θ(1) time.

add-to-back

Without a tail pointer, adding to the back involves traversing the list, stopping at the last node. Then a new node is added:

    function add-to-back(value)
        {
        if (is-empty())
            add-to-front(value);
        else
            {
            var last = get-last-node();
            last.next = new-node(value,null);
            }
        }

If the list is empty, then an add-to-front is performed to make sure the head pointer is updated properly. Otherwise, the get-last-node function is tasked with the job of walking the list, starting at the head, and returning the last node in the list. As written, add-to-back takes Θ(n) time, due to the cost of the get-last-node function.

However, if a tail pointer is used, this operation can be reduced to Θ(1) time since the last node in the list is cached. When adding to the back, care must be taken to update the tail pointer to the new node.

remove-from-front

Removing from the front updates the head pointer to point to the head's next pointer. In the case of a dummy head node, the dummy's next pointer is updated.

If a tail pointer is used, a check must be made if the list becomes empty. If so, the tail pointer should be set to null.

This operation takes Θ(1) time.

remove-from-back

If the size of the list is one, then this operation should call remove-from-front to ensure a newly empty list is dealt with properly. Otherwise, one must walk to list to find the next to the last node and set its next pointer to null. If a tail pointer is kept, it is set to the new "last" node.

This operation takes Θ(n) time, regardless of whether a tail pointer is kept or not.

insert-at-index

Inserting at a given index entails walking the list. With each step, the index is reduced by one. When the index reaches one (using zero-based counting), a new node containing the given value is inserted between the current node, and the node after the current node. Care must be taken so that all pointers are updated correctly. A special case occurs when the given index is zero. If so, add-to-front is called instead of performing the walk and subsequent node insertion.

If a dummy head node is used, the walk stops when the index reaches zero. There are no special cases when using a dummy head node.

This operation takes Θ(n) time.

remove-from-index

Similar to add-at-index, but after walking to the proper node, the next node is unlinked from the current node:

    current.next = current.next.next;

Usually, the deleted node or the value of the deleted node is returned after unlinking. Special cases exist if a dummy head node is not used or if a tail pointer is used and the list becomes empty.

This operation takes Θ(n) time.

is-empty

If the size of the list is cached, then this operation returns whether or not the size is zero. Otherwise, the list is walked and the whether or not the number of steps taken is zero is returned.

size

If the size of the list is cached, then the size must be updated when add or remove operations are performed.

find

Finding a value in the list involves traversing the list, similar to that of finding a value in an array.

Traversals

Traversing (or walking) a list involves following next pointers until a null is found:

    current = head;
    while (current != null)
        {
        current = current.next;
        }

If a dummy head node is used, the walk is started using the dummy head node's next pointer.

Traversing the list 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


Nodes Top Doubly Linked-Lists Contents