CLL vs SLL, Use of Tail Pointer

A singly linked list (SLL) is usually drawn as an open chain: the last node’s next is NULL. A singly circular linked list (CLL) closes the chain so the last node points back (typically to head). This page compares the two and explains why many CLL implementations keep a tail pointer—not just head—to reach both ends in O(1).

1) SLL vs CLL — structure

Both use the same node shape (data + next). The difference is what the last node points to:

• SLL (linear): last node’s next is NULL. You detect the end by NULL.
• CLL (circular): in a non-empty list, last node’s next points into the list—almost always head. There is no NULL “end marker” on the last node.

Diagrams (same values 10 → 20 → 30)

SLL — open chain                         CLL — ring (last → head)

  head                                       tail often stored here
    │                                                    │
    ▼                                                    ▼
┌──────┐   ┌──────┐   ┌──────┐              ┌──────┐   ┌──────┐   ┌──────┐
│  10  │──→│  20  │──→│  30  │──→ NULL      │  10  │←──│  30  │←──│  20  │…
└──────┘   └──────┘   └──────┘              └──┬───┘   └──────┘   └──────┘
     ▲ head                          head ───┘         ▲_______________│
                                                         └── tail→next = head

2) SLL vs CLL — traversal and operations

Choose SLL when you want a simple NULL-terminated walk and a clear end. Choose CLL when the problem is cyclic or you want uniform “always a next node” inside a non-empty list.

3) Tail pointer in SLL

If you only store struct Node *head, inserting or deleting at the end requires walking to the last node — O(n). Maintaining an extra struct Node *tail lets you append in O(1) by linking the old last node to the new node and moving tail.

Limits: after some deletes you must keep tail correct. Insert/delete at the end still needs the predecessor of the last node if you only have singly links—so “delete last” is still awkward without a full walk or a doubly linked list.

4) Tail pointer in CLL — why it shines

A very common CLL convention is:

• tail points to the last node in the ring.
• tail->next is always head (first node).

Then in O(1) time you have:

• Last node: tail
• First node: tail->next (i.e. head)

That makes insert at end straightforward: create a new node, link old tail->next through the new node, update tail, and keep tail->next == head. Insert at beginning can also be done in O(1) with the same invariant: new node’s next becomes the old first node; tail->next points to the new first; advance nothing on tail if the new node is before the old head (implementation details vary—some APIs expose only tail).

Without tail, only head: finding the last node still costs O(n) in a CLL because you must walk until you are about to return to head.

Conceptual variables in C

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

/* Common CLL pattern: one pointer to last node */
struct Node *tail;   /* tail->next is the first node (head) */
/* "head" is then: tail->next (when list non-empty) */

Empty list: usually tail == NULL (and no nodes). Single node: that node’s next points to itself; tail points at that node.

5) Summary

• SLL — open chain, NULL terminator, simple loops; tail helps append only.
• CLL — closed ring; traversal needs explicit stopping; tail + tail→next == head gives O(1) access to both first and last.