README

The module contains functions used in singly linked lists.

These functions do not make assertions, can lead to infinite loops in code and cycles in nodes or lists.

As a general rule, cycles should be broken before any other changes. Almost all functions are candidates for applying this rule. Keep this in mind when infinite loops occur in code and their causes are not very obvious.

Some important facts about cycles:

• a cycle always starts from the last node of node
• where the last node points in node really matter:
  • to last node, n4 -> n4
  • to an inner node, n4 -> n2
  • to first node, n4 -> n0
• where we break the cycle really matter, see the demos
• any function that involves the last node in some way, for a cycle node or list, leads to infinite loops in code

The code is based on following sources:

• Zig Standard Library
  • GitHub

📌 Implementation

A singly linked list is a linear data structure that includes a series of connected nodes.

The Node represents the type of nodes in a list

    pub const Node = struct {
        data: T,
        next: ?*Node = null,

        // some implementation code
    };

where field:

• data is a value for the node itself
• next is a pointer to the next node

The SinglyLinkedList type has a single field

    pub fn SinglyLinkedList(comptime T: type) type {
        return struct {
            head: ?*Node = null,

            // some implementation code
        };
    }

where field head is a pointer to the first node in list.

Above structures use an optional pointer ?*Node, with default value null.

The meaning of null depends on context:

• for a list .head == null
  • the list is empty, there are no nodes in list
  • in many cases this check is done separately, it is a special case for a list
• for a node .next == null
  • the node is not linked or is the last node in a list, end of list
  • general case for this check is when the operations are on a single node, even if a function accepts only one node as parameter, the node itself can be linked to another, and another, and so on
  • the check becomes more important in needs to avoid node cycles, either by pointing back to the node itself or to another node already existing in list

📌 Final note

More information about cycles in nodes and singly linked list can be found in IMPORTANT file. Also, more detailed examples are in the demo files.