What is a circular singly linked lists?

A circular singly linked list is a memory structure in programming that supports walking around the list in a circle. Such a list is almost always written in the following form:

class ListNode {

public ListNode nextNode;

public Object nodeData;

public void addNode(Object newData);

public void removeNode();

}

Note that I've just generalized the data structure, as each language will have a specific syntax that has to be followed.

The data is organized such that if you follow nextNode indefinitely, you will eventually circle all the way back to the original node you started at. This is the "circular" part of this list. Going in a circle is done like this:

while(ListNode node = CurrentNode.nextNode) {

/* Do some processing here */

}

Depending on the actual use case, care must be taken to ensure that you are not truly going around infinitely.

The "singly linked" part is identified by the single pointer (or reference, if you will) to the next available node, called nextNode. A "doubly linked" structure would also contain a "previousNode" pointer/reference.

void addNode(Object Data) {

ListNode temp = new ListNode();

temp.nextNode = CurrentNode.nextNode;

temp.Data = Data;

CurrentNode.nextNode = temp;

}

Inserting a new node can be done by inserting after the current entry. Inserting in place of the current entry would be slightly more complex, because you'd have to move the data pointers in the current node to the new node, then place the new data into the current node.

void removeNode() {

CurrentNode.nextNode = CurrentNode.nextNode.nextNode;

}

This code removes the node after the current entry. Again, to remove the current node instead of the one following, you would move the data from nextNode into the current node, then delete nextNode.

In a modern programming language, the old node will be garbage collected after a period of time, thus reclaiming the memory used. In other languages, you would need to "free" or "delete" the ListNode that was contained in CurrentNode.nextNode.