Linear Lists

A linear list is one of the most fundamental and the most frequently used logical structures in data structures; structures such as stacks, queues and strings can all be seen as special cases or extensions of it. This chapter revolves around the central comparison of sequential storage versus linked storage: it introduces the definition of a linear list, the implementation and the basic operations of the sequential list and of the linked list, and it trains you to choose the right storage structure for a given scenario. After reading this chapter you will be able to understand the definition and the basic characteristics of a linear list, master the storage structure of the sequential list together with its insertion and deletion operations and the complexity analysis, master the storage structure of the singly linked list together with its insertion and deletion operations and the complexity analysis, learn the characteristics and the applicable scenarios of doubly linked lists, circular linked lists and static linked lists, and understand how to choose the right storage structure for the requirement at hand.

Questions This Chapter Answers

When a set of elements with a linear relationship has to be stored, do you choose a sequential list whose addresses are contiguous, or a linked list whose nodes are joined by pointers? The two have their own advantages and disadvantages in random access, in insertion and deletion, and in the use of the space. This chapter revolves around this central question of choosing a storage structure, and it introduces the implementation details of the two storage schemes, the differences in complexity and the scenarios in which each of them applies.

Basic Concepts

Basic Concepts

Comparison of the Storage Structures

• Sequential list: the elements of the linear list are stored one after another in a set of storage units with contiguous addresses, so logically adjacent elements are physically adjacent.
• Linked list: every node contains a data field and a pointer field and the nodes are joined by pointers, so logically adjacent elements are not necessarily physically adjacent.

Exercises

Exercise 1

The characteristic of a linear list is ( )

A. The number of the elements is fixed and never changes B. Every element except the first and the last has exactly one predecessor and exactly one successor C. The storage addresses have to be contiguous D. All the elements may have different types

Exercise 2

Briefly describe the definition and the main characteristics of a linear list.

Exercise 3

What are the advantages and the disadvantages of the sequential list and of the linked list?

Sequential Storage

A sequential list is implemented with an array; it is the simplest and the most commonly used storage scheme. Its core operations are insertion, deletion and searching.

Insertion into a Sequential List

To insert the element x at position i, the elements from the i-th to the last one have to be shifted one place to the right, one after another.

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int length;  // current length
} SqList;

// insert the element x at position i (i starts from 1)
bool ListInsert(SqList &L, int i, int x) {
    if (i < 1 || i > L.length + 1) return false;  // illegal position
    if (L.length >= MaxSize) return false;        // the list is full
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];  // shift the elements to the right
    L.data[i - 1] = x;
    L.length++;
    return true;
}

Deletion from a Sequential List

To delete the element at position i, the elements from the (i+1)-th to the last one have to be shifted one place to the left, one after another.

// delete the element at position i and return it in e
bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
        L.data[j - 1] = L.data[j];  // shift the elements to the left
    L.length--;
    return true;
}

Complexity Derivation

Insertion: in the best case, inserting at the tail of the list, 0 elements are moved; in the worst case, inserting at the head of the list, n elements are moved; on average $\frac{n}{2}$ elements are moved. Therefore:

$T_{insert}(n) = O(n)$

Deletion: similarly, $\frac{n-1}{2}$ elements are moved on average, so $T_{delete}(n) = O(n)$.

Access by position: the element is reached directly through its index, so $T_{get}(n) = O(1)$.

Exercises

Exercise 1

In a sequential list of length n, inserting one element at position i (where $1 \le i \le n+1$) requires moving how many elements ( )

A. n-i+1 B. n-i C. i D. i-1

Exercise 2

How is the traversal of a linear list implemented?

Linked Storage

A singly linked list joins its nodes with pointers: an insertion and a deletion do not have to move any element, but a search has to start from the head of the list and traverse it.

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

Insertion into a Singly Linked List

To insert a new node s after the i-th node, first let s point to the successor and then let the predecessor point to s. The order must not be reversed.

// insert the node s at position i (the insertion is made before the node at position i)
bool ListInsert(LinkList &L, int i, int x) {
    LNode *p = L;  // head node
    int j = 0;
    while (p != NULL && j < i - 1) {  // find the (i-1)-th node
        p = p->next;
        j++;
    }
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;  // (1) the new node points to the successor
    p->next = s;        // (2) the predecessor points to the new node
    return true;
}

Deletion from a Singly Linked List

To delete the i-th node, it is enough to let the predecessor node point to the successor of the deleted node.

bool ListDelete(LinkList &L, int i, int &e) {
    LNode *p = L;
    int j = 0;
    while (p->next != NULL && j < i - 1) {  // find the (i-1)-th node
        p = p->next;
        j++;
    }
    if (p->next == NULL) return false;  // the i-th node does not exist
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;  // skip the deleted node
    free(q);
    return true;
}

Complexity Derivation

• Insertion and deletion: locating the position takes $O(n)$, but modifying the pointers after the position has been located takes only $O(1)$. If the predecessor of the insertion position is already known, the insertion and the deletion are $O(1)$.
• Search by value: the elements have to be compared one by one starting from the head of the list, so the worst case is $O(n)$.
• Access by position: the list has to be traversed, so the worst case is $O(n)$.

Exercises

Exercise 1

The advantage of a singly linked list over a sequential list is ( )

A. It supports random access B. Its insertion and deletion operations are efficient C. Its storage density is higher D. Its search is more efficient

Exercise 2

What is the basic idea of the insertion and of the deletion in a singly linked list?

Other Linked Lists

Doubly Linked List

Every node has two pointer fields, one pointing to the predecessor and one to the successor, so a bidirectional traversal is supported. The price is one extra pointer per node and a larger space cost.

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

The insertion operation (inserting s after the node p):

s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

Circular Linked List

• Circular singly linked list: the pointer of the last node points to the head node or to the first node, so that the whole list is connected end to end and every node can be reached starting from any node.
• Circular doubly linked list: the prior of the head node points to the tail node, and the next of the tail node points to the head node.

A circular linked list is often used in the scenarios that operate frequently on the two ends, the Josephus ring and the process scheduling of an operating system for instance.

Static Linked List

A static linked list simulates a linked list with an array, and the “pointer” of a node is replaced by an array index, that is, a cursor; it suits the high-level languages that do not support pointers and the scenarios where the memory is limited.

Exercises

Exercise 1

Briefly describe the difference between a singly linked list and a doubly linked list and the scenario in which each of them applies.

Typical Applications and Summary

The two preceding sections have made clear the difference in the storage between the sequential list and the linked list; this section puts them back into real decisions: task queues, browsing history, shopping carts and the undo and the redo of an editor are all built on a linear list underneath, and it is only the question of whether a random access is frequent that decides between the sequential list and the linked list. The common pitfalls at the end remind you that in a singly linked list the order of connecting first and breaking later must not be reversed during an insertion, and that is the line of code which is the easiest to get wrong.

Typical Applications

• As the foundation of the other data structures: the linked storage of stacks, queues, strings and sparse matrices is in essence a linked list node with a different linking rule.
• Task queues, browsing history and shopping carts: in these scenarios the elements are frequently added and removed at the two ends and are seldom accessed by their serial number in the middle, so a linked list, or a queue and a stack built on a linked list, avoids the cost of moving the elements that a sequential list would incur.
• The undo and the redo of a text editor: every edit produces one record, and organizing the records with a stack naturally supports undoing the most recent operation and restoring the operation that has been undone.

Terminology Summary

Common Pitfalls

Two other frequent mistakes come next. The first is mixing a list with a head node and a list without one: with a head node p points at the head node, and the first element that is inserted has to be inserted after the head node; without a head node the special case of the empty list has to be taken into account. The second is the condition for testing whether the list is empty: with a head node the empty list is head->next == NULL, and without a head node it is head == NULL.