Editing Linked list (section)

===Circularly linked list===

In a circularly linked list, all nodes are linked in a continuous circle, without using ''null.'' For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The ''next'' node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time.

Circularly linked lists can be either singly or doubly linked.

Both types of circularly linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing ''firstNode'' and ''lastNode'', although if the list may be empty, there needs to be a special representation for the empty list, such as a ''lastNode'' variable which points to some node in the list or is ''null'' if it is empty; it uses such a ''lastNode'' here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.

====Algorithms====
Assuming that ''someNode'' is some node in a non-empty circular singly linked list, this code iterates through that list starting with ''someNode'':

 '''function''' iterate(someNode)
     '''if''' someNode ≠ '''null'''
         node := someNode
     '''do'''
         do something with node.value
         node := node.next
     '''while''' node ≠ someNode

Notice that the test "'''while''' node ≠ someNode" must be at the end of the loop. If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node.

This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.

 '''function''' insertAfter(''Node'' node, ''Node'' newNode)
     '''if''' node = '''null'''    // assume list is empty
         newNode.next := newNode
     '''else'''
         newNode.next := node.next
         node.next := newNode
     update ''lastNode'' variable if necessary

Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the ''end'' of the list, one may do

 insertAfter(L, newNode)
 L := newNode

To insert "newNode" at the ''beginning'' of the list, one may do

 insertAfter(L, newNode)
 '''if''' L = '''null'''
     L := newNode
This function inserts a value "newVal" before a given node "node" in O(1) time. A new node has been created between "node" and the next node, then puts the value of "node" into that new node, and puts "newVal" in "node". Thus, a singly linked circularly linked list with only a ''firstNode'' variable can both insert to the front and back in O(1) time.
 '''function''' insertBefore(''Node'' node, newVal)
     '''if''' node = '''null'''    // assume list is empty
         newNode := '''new''' Node(data:=newVal, next:=newNode)
     '''else'''
         newNode := '''new''' Node(data:=node.data, next:=node.next)
         node.data := newVal
         node.next := newNode
     update ''firstNode'' variable if necessary
This function removes a non-null node from a list of size greater than 1 in O(1) time. It copies data from the next node into the node, and then sets the node's ''next'' pointer to skip over the next node.
 '''function''' remove(''Node'' node)
     '''if''' node ≠ '''null''' and size of list > 1
         removedData := node.data
         node.data := node.next.data
         node.next = node.next.next
         '''return''' removedData
<!--PLEASE FIX THIS
As in doubly linked lists, "removeAfter" and "removeBefore" can be implemented with "remove(list, node.prev)" and "remove(list, node.next)".

example:
node 'tom' next pointing to node 'jerry'...till the last point at node 'fix'..
data in node 'fix' previous to node 'tom'...looping instruction..
-->