Circular Linked Lists

Please visit my earlier post linked lists for basics of linked lists. Visit this post for circular double linked lists

What is circular linked list?

Circular Linked lists are chain of records/nodes, one record/node points to the next, and last node/record pointing to the first node instead of pointing to a sentinel. Record/node holds the data.

Why circular linked lists?

Circular linked lists can be traversed from anywhere (given any node) in the list, which gives flexibility and it also enahnces efficiencies of some operations however it complicates operations by inducing special cases to deal with circularity of list

How circular linked lists look like?

Operations On Circular Linked Lists:

 

Please refer http://www.refcode.net/2013/02/circular-linked-lists.html

 

Printing linked List in Reverse without Reversing The List Actually

Printing a linked list in reverse order without actually reversing the linked list can be done by a recursive routine or using a stack.

Lets us see a recursive routine first…

In recursive routine go to the end then print the nodes, i.e. recursive call comes before printing the node… Here is the function…

void printreverse(Node *node)
{
  if (node)
  {
    printreverse(node->next);
    printf("%d -> ",node->info);
  }
}

Reversing the list using stack:
Push all the nodes, pop one by one and print them… Here is the program for this..

void printreverse(Node* node)
{
  Node *tmpnode;

  Stack *stack = CreateStack();

  while(node)
  {
    Push(stack, node);
    node = node->next;
  }

  tmpnode = Pop(stack);

  while(tmpnode)
  {
    tmpnode = Pop(stack);
    printf("%d -> ", tmpnode->info);
  }

  DestroyStack(stack);
}

Josephus Problem in C

Q:Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 40 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive.

Requirements:

1. Circular linked list must be used.
2. The sequence starts from 1, therefore you won’t see a 0 appear in the sequence.The number of people and number of skips must be larger than 0
   (>0).

Please refer http://www.refcode.net/2013/03/josephus-problem-in-c.html

Sorting a Linked List with QuickSort – Simple Algorithm

Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(nlogn). It is based on devide and conquer idea:
partition into two lists and put them back together again. It does more work on the divide side, less on the combine side.

The basic algorithm is
1)pick any element (called as Pivot) in list
2)Partition the list as two parts, first part contains all the elements which are less than pivot, the other contain all the elements which are greater than pivot
3)do quicksort recursively on sub lists

Regarding step1:
Any element can be selected as pivot, but some choices may cause bad performance. Example. first element everytime: this pivot cause bad performance on presorted or lists in reverse sorted order, because all elements go into one sublist. One safe strategy is choosing pivot randomly.

regarding Step2:
As already pointed out quicksort does most of the work while partitioning the lists, so this is the step which is a bit complex..

both step1 and 2 are represented graphically below…

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-quicksort.html