Types of Linked Lists

Singly Linked List

To avoid moving elements, a linear list can use another storage method: linked storage. A linked list is a data structure that is physically noncontiguous and unordered, and it consists of nodes.

Every singly linked-list node contains two parts: a data field named data and a pointer field named next that points to the next node. Nodes can be created dynamically at runtime.

typedef struct node_t {
    T data;
    struct node_t *next;
} node_t;

The first node is called the head node, and the last node is called the tail node. The tail node's next pointer points to NULL.

Unlike an array, which locates elements randomly by index, a linked list can only use node A's next pointer to find the next node B, then use node B's next pointer to find node C, and so on.

Arrays use sequential storage in memory, whereas linked lists use scattered storage. Each node can occupy a different memory location and is connected through next pointers. This makes flexible and effective use of fragmented free space.

Doubly Linked List

How can the previous node be found quickly from a node in a linked list? A doubly linked list allows every node to trace back to its predecessor.

It is slightly more complex than a singly linked list. In addition to data and next, every node has a prev pointer to its preceding node.

typedef struct node_t {
    T data;
    struct node_t *prev;
    struct node_t *next;
} node_t;

Singly linked lists can only be traversed from head to tail. They can find successors but not predecessors, so traversal does not loop forever. A doubly linked list requires storage for one additional pointer; each node has two pointers to its immediate predecessor and successor.

Circular Linked List

Besides singly and doubly linked lists, there are circular linked lists. In a singly circular linked list, the tail node's next pointer points to the head. In a doubly circular linked list, the tail node's next points to the head and the head node's prev points to the tail.