Node definition

struct Node {
    int data;
    struct Node *next;
};

Why a pointer is used

The structure cannot contain a complete instance of itself directly: that would require another instance inside it, without a finite completed layout. A pointer has a usable pointer type while the node definition is being completed, so next can identify another node.

Linking example

Two separate Node objects can hold 10 and 20. Set the first node’s next to the address of the second and set the second node’s next to NULL. Starting with the first node, following next reaches the second, then detects the null link at the end.

Lifetime and ownership

A node pointer does not create its target. Nodes may have automatic, static or allocated storage with different lifetimes. In a dynamic list, allocate each needed node, check the result and free it when removed. Never retain a link to an object whose lifetime has ended.

Complexity

Reading the current node’s data or next member is O(1). Following links to visit n nodes takes O(n) time. A single next link does not provide constant-time indexed access to an arbitrary position. This type is the foundation for the singly linked-list operations in Unit III.

Diagram or flowchart