CODEWITHSUNDEEP
cpointerslinked-list
Huzo
Huzo

Reputation: 1692

Do we need a head node in a circular linked list

I need to create a circular linked list. However, I am not sure if I should be having a head node. If I include a head node I will be able to empty everything easily. But the last element would have to point to the node the head is pointing? I am not sure if that would ease things or make it harder.

Upvotes: 1

Views: 3973

Answers (2)

Mark Benningfield
Mark Benningfield

Reputation: 2902

For a circular linked-list, a head node (usually termed a sentinel node in this case) is only useful if you need to keep track of the insertion order of the elements, because to maintain an order, you need to know the starting point.

For singly-linked lists, this is usually not a consideration, because if insertion order is important, there is not really any point in making the list circular in the first place. For doubly-linked lists, however, it becomes useful because then you have a list that you can traverse in either direction: LIFO or FIFO.

For example, an empty, doubly-linked circular list with a sentinel node would look like this:

enter image description here

The sentinel node is persistent, and usually doesn't carry any payload. As nodes are added, the list begins to look like this:

enter image description here

As you can see, this allows traversal of the list either in the order the nodes were inserted (using the next pointers), or the reverse (using the prev pointers).

Again, for a singly-linked list, if the insertion order is needed, then making the list circular defeats the purpose right from the start. If the insertion order is not needed, then there's no point in having a sentinel node you have to carry around, because you never use it. Any old node will do.

Upvotes: 4

paxdiablo
paxdiablo

Reputation: 882146

A circular linked list doesn't need a head node since there's really no head. It does however need a pointer into some node within the list so you can get to all the elements.

In terms of freeing the list, a normal list scan would stop after processing the node that points to null. A circular list is very similar except that you remember the node you started at so you can stop after freeing the one that points to it. Pseudo-code for such a beast would look like:

def deleteAll(someNode by reference):
    # Do nothing for empty list.

    if someNode == null:
        return

    # Process each node, stopping after one that points to start node.

    nodeToDelete = someNode
    do:
        nextNode = nodeToDelete.next
        free nodeToDelete
        nodeToDelete = nextNode
    until nodeToDelete == someNode

    # Mark list as empty.

    someNode = null

Upvotes: 4

Related Questions