Linked List – Detect a Cycle

I spent a considerable amount of time over the weekend experimenting with this easy challenge from HackerRank. If interested you can get to the challenge using the following URL: https://www.hackerrank.com/challenges/ctci-linked-list-cycle

For starters, the first element in the list is also the head. This is not a good idea. The reason is that if the head changes references to the list are lost. This might be OK for trivial examples, but in real life a list may be referenced by different threads.

It seems to me that the challenge addresses a possible issue when a person implements their own liked list. It is hard to create a cycle with a list that has methods to add and remove elements. IN that case the links are managed by the class. A cycle condition would be due to a poor implementation that was not tested.

If you are using Java and a list class from the library, I do not see how a cycle could be created. If you have an example I would like to hear from you.

The first reason I spent a lot of time on this challenge was to make sure the requirements are meant not to practice on a condition that would never be encountered; at least not in an OOP language (e.g., Java), but to verify the mental thinking process of an individual.

The second reason, and perhaps the most important to me, is that some time ago I designed and implemented a queue library with an API that has been used in several commercial of the shelf (COTS) products. I am not at liberty to show the code, but the API is public domain. A partial edited listing of the API description (sncrque.h) follows:

typedef       struct SENCOR_QUEUE  {

struct SENCOR_QUEUE  *next;

struct SENCOR_QUEUE  *prev;

unsigned long        count;

unsigned long        priority;

unsigned long        mutex;

__int32                    time;

unsigned long        signature;

void                 *privateData;

unsigned long        elementSize;

unsigned long        maxCount;

unsigned char        filler[SENCOR_QUEUE_LEN – 40];

} SENCOR_QUEUE;

SENCOR_EXPORT INT_CALL      QueAlloc      (                                                                                  SENCOR_QUEUE  **queue

);

SENCOR_EXPORT INT_CALL      QueAppend     (

SENCOR_QUEUE  *baseQueue,                                                          SENCOR_QUEUE  *queueToAppend

);

SENCOR_EXPORT INT_CALL      QueClear      (

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT INT_CALL      QueClone      (

SENCOR_QUEUE  *originalQ,

unsigned long elementSize,

SENCOR_QUEUE  *cloneQ

);

SENCOR_EXPORT INT_CALL      QueConsistent (

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT INT_CALL      QueCopy              (

SENCOR_QUEUE  *dstQueue,

SENCOR_QUEUE  *srcQueue

);

SENCOR_EXPORT INT_CALL      QueCopyCount  (

SENCOR_QUEUE  *srcQueue,

SENCOR_QUEUE  *dstQueue,

unsigned long countToCopy

);

SENCOR_EXPORT INT_CALL      QueCopyFromHere (

SENCOR_QUEUE  *srcQueue,

SENCOR_QUEUE  *element,

SENCOR_QUEUE  *dstQueue

);

SENCOR_EXPORT INT_CALL      QueCopyThis   (

SENCOR_QUEUE  *srcQueue,

SENCOR_QUEUE  *dstQueue,

int           n

);

SENCOR_EXPORT INT_CALL      QueDeQueue    (

SENCOR_QUEUE  *queue,

SENCOR_QUEUE  *element

);

SENCOR_EXPORT INT_CALL      QueDestroy    (

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT INT_CALL      QueDump              (

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT INT_CALL      QueFree              (

SENCOR_QUEUE  **queue

);

SENCOR_EXPORT INT_CALL      QueGetCount   (

SENCOR_QUEUE  *queue,

unsigned long *count

);

SENCOR_EXPORT INT_CALL      QueGetElementSize (

SENCOR_QUEUE  *queue,

unsigned long *elementSize

);

SENCOR_EXPORT INT_CALL      QueGetMaxCount (

SENCOR_QUEUE  *queue,

unsigned long *maxCount

);

SENCOR_EXPORT INT_CALL      QueGetPrivateData (

SENCOR_QUEUE  *queue,

void          **privateData

);

SENCOR_EXPORT INT_CALL      QueGetTime    (

SENCOR_QUEUE  *queue,

time_t        *time

);

SENCOR_EXPORT INT_CALL      QueHasCycle   (

       SENCOR_QUEUE  *queue,

       BOOL          *hasCycle

       );

SENCOR_EXPORT INT_CALL      QueInit              (

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT INT_CALL      QueInsert     (

SENCOR_QUEUE  *queue,

SENCOR_QUEUE  *element

);

SENCOR_EXPORT INT_CALL      QueInsertHead (

SENCOR_QUEUE  *queue,

SENCOR_QUEUE  *element

);

SENCOR_EXPORT INT_CALL      QueInsertHere (

SENCOR_QUEUE  *queue,

SENCOR_QUEUE  *here,

unsigned short       position,

SENCOR_QUEUE  *element

);

SENCOR_EXPORT INT_CALL      QueIsEmpty    (

SENCOR_QUEUE  *queue,

BOOL          *isEmpty

);

SENCOR_EXPORT INT_CALL      QueIsFull     (

SENCOR_QUEUE  *queue,

BOOL          *isFull

);

SENCOR_EXPORT INT_CALL      QueMoveElement       (

SENCOR_QUEUE  *srcQueue,

SENCOR_QUEUE  *element,

SENCOR_QUEUE  *dstQueue

);

SENCOR_EXPORT INT_CALL      QuePack              (

SENCOR_QUEUE  *queue,

unsigned long elementSize,

void          **buffer,

unsigned long *bufferSize

);

SENCOR_EXPORT INT_CALL      QuePointToElement (

SENCOR_QUEUE  *queue,

unsigned long n,

SENCOR_QUEUE  **element

);

SENCOR_EXPORT INT_CALL      QueRemove     (

SENCOR_QUEUE  *queue,

SENCOR_QUEUE  **element

);

SENCOR_EXPORT INT_CALL      QueSetElementSize (

SENCOR_QUEUE  *queue,

unsigned long elementSize

);

SENCOR_EXPORT INT_CALL      QueSetMaxCount       (

SENCOR_QUEUE  *queue,

unsigned long maxCount

);

SENCOR_EXPORT INT_CALL      QueSetPrivateData (

SENCOR_QUEUE  *queue,

void          *privateData

);

SENCOR_EXPORT INT_CALL      QueSetTime    (

SENCOR_QUEUE  *queue,

time_t        time

);

SENCOR_EXPORT INT_CALL      QueTimeDiff   (

SENCOR_QUEUE  *element,

time_t        *seconds

);

SENCOR_EXPORT INT_CALL      QueUnPack     (

void          *buffer,

unsigned long bufferSize,

unsigned long elementSize,

SENCOR_QUEUE  *queue

);

SENCOR_EXPORT int __cdecl   SencorQueueCompare (

       const void           *a,

       const void           *b

       );

As I mentioned earlier, if the functions / methods are working properly then it is quite difficult to end up with a circular queue. Keep in mind that the methods manage all pointers. In addition an empty queue is instantiated with its own set of pointers. The head and tail are set to point to the queue element when the queue is created and is empty. There are simple consistencies checks perform when each method is invoked.

After solving this challenge I decided to add the QueHasCycle() method. In a nutshell the method performs the following set of steps:

// **** initialization ****

// **** perform some sanity checks ****

// **** check if the queue has been initialized ****

// **** check if queue is empty ****

// **** check if count is too big ****

// **** allocate array of links ****

// **** traverse the queue using the next link ****

// **** sort the links ****

// **** check for duplicates ****

// **** traverse the queue using the prev link ****

// **** sort the links ****

// **** check for duplicates ****

// **** clean up ****

// **** free array of links (if needed) ****

// **** inform the user what is going on ****

// **** inform the caller what went on ****

Given that this new method will be part of the standard API from now on, I decided not to include its code.

I always start a method with initialization steps and always terminate with a clean up. An array of pointers is allocated. The array is populated by traversing the queue from the head to the tail using the next pointer. Each time an element is visited the value of the pointer is stored in the array. The array of pointers is sorted. The array is traversed looking for duplicates. A dup0licate would indicate a circular list.

The traversal operation is then repeated using the prev pointer.

The actual code was implemented using the Visual Studio 2013 Professional edition.

I will now show a simple example using a test utility. I always develop test code (which fails) and then implement the actual methods. In the way additional tests or code modifications may occur. Such process is quite common in software development. Some edited (for duplication) console screen captures follow:

Edited main menu for queue testing:

* * * * Test Queue Methods * * * *

1      QueAlloc()      heap (used in most cases)

2      QueInit()       stack

3      QueClear()

4      QueFree()       heap

5      QueDestroy()    stack

6      QueInsert()

7      QuePush()

8      QuePop()

9      QueDump()

10      QueConsistent()

11      QueCopy()

12      QueDeQueue()

13      QueGetCount()

14      QueInsertHead()

15      QueInsertHere()

16      QueIsEmpty()

17      QueRemove()

18      QueTimeDiff()

19      QueMutexLock()

20      QueMutexIsLocked()

21      QuePointToElement()

22      QuePack()       <—+

23      QueUnPack()     <—+

24      QueAppend()

25      DupOrSeq

26      QueIsFull()

27      QueSetMaxCount()

28      QueGetMaxCount()

29      QueHasCycle()

-1      QUIT

>>> selection [1]:

After allocating a queue:

>>> selection [1]: 16

TestQueCalls <<< QueIsEmpty isEmpty: 1 (bool) line: 1518

>>> selection [16]: 9

QueDump <<< sizeof(SENCOR_QUEUE): 64

QueDump <<< queue: 0x011c1920 line: 1695

+———————-+

+–>|       queue: 011c1920|<——-+

|   |       count:        0|        |

|   |    priority:        0|        |

|   |        time: 58a1c5c7|        |

|   |   signature: abcddcba|        |

|   | elementSize:        0|        |

|   | privateData: 00000000+–>     |

+—+        prev: 011c1920|        |

|        next: 011c1920+——–+

+———————-+

After setting the maximum queue size to 3 and attempting to enter 4 elements:

>>> selection [6]: 6

>>> element priority [0]:

>>> element value [34]: 44

QueInsert <<< queue->count: 3 >= queue->maxCount: 3 line: 694 file ==>c:\sencorsource\source\que.c<==

Message <<< Buffer is FULL – WAR_BUFFER_FULL

TestQueInsert <<< QueInsert status: -1359 line: 1733 file ==>c:\sencorsource\source\testlib.c<==

TestQueCalls <<< TestQueInsert status: -1359

>>> selection [6]: 9

TestQueDump <<< element: 0x011c17d0 priority: 0 value: 11

TestQueDump <<< element: 0x011c1990 priority: 0 value: 22

TestQueDump <<< element: 0x011c1a00 priority: 0 value: 33

QueDump <<< sizeof(SENCOR_QUEUE): 64

QueDump <<< queue: 0x011c1920 line: 1695

+———————-+

|       queue: 011c1920|<——-+

|       count:        3|        |

|    priority:        0|        |

|        time: 58a1c5c7|        |

|   signature: abcddcba|        |

| elementSize:        0|        |

| privateData: 00000000+–>     |

+——+        prev: 011c1a00|        |

|  +–>|        next: 011c17d0+—–+  |

|  |   +———————-+     |  |

|  |                                |  |

|  |   +——————+         |  |

|  |   | element: 011c17d0|<——–+  |

|  +—+    prev: 011c1920|            |

|  +–>|    next: 011c1990+———+  |

|  |   +——————+         |  |

|  |                                |  |

|  |   +——————+         |  |

|  |   | element: 011c1990|<——–+  |

|  +—+    prev: 011c17d0|            |

|  +–>|    next: 011c1a00+———+  |

|  |   +——————+         |  |

|  |                                |  |

|  |   +——————+         |  |

|  |   | element: 011c1a00|<——–+  |

|  +—+    prev: 011c1990|            |

+—–>|    next: 011c1920+————+

+——————+

Three elements with values 11, 22 and 33 have been inserted. When I tried inserting element 44 the operation failed indicating the queue was full. A simplified graphical representation was then invoked.

I then invoked the new QueHasCycle() method:

>>> selection [9]: 29

TestQueCalls <<< QueHasCycle hasCycle: 0 (bool) line: 1603

As expected, the queue has no cycles.

Note that the API includes a QueConsistent() method which perform a set of consistency checks. The QueHasCycle() method is not included at this time.

>>> selection [29]: 10

Getting back to the challenge, following is the Java code implemented using the Eclipse IDE:

import java.util.Random;

import java.util.Scanner;

class Node {

// **** constants ****

public final int MAX_SIZE  = 100;

public final int CYCLE_MOD = 7;

// **** members ****

int data;

Node next;

/*

* constructor

*/

public Node(int data) {

this.data = data;

this.next = null;

}

/*

* append node to list

*/

Node append(Node head, int data) {

// **** instantiate new node ****

Node node = new Node(data);

// **** empty list (new head) ****

if (head == null) {

return node;

}

// **** get to the last node ****

Node p = head;

for ( ; p.next != null; p = p.next) {}

// **** append new node to list ****

p.next = node;

// **** return head of list ****

return head;

}

void makeItCycle(Node head) {

System.out.println(“makeItCycle <<< entering …”);

// **** check for null head ****

if (head == null) {

return;

}

// **** generate random place to put cycle ****

Random rand = new Random(System.currentTimeMillis());

int c = 1 + rand.nextInt(CYCLE_MOD – 1);

System.out.println(“makeItCycle <<< c: ” + c);

// **** get to the tail ****

Node cycle    = null;

Node p               = head;

for (int i = 1; p.next != null; p = p.next, i++) {

if (c == i) {

System.out.println(“makeItCycle <<< cycling …”);

cycle = p;

}

}

// **** ****

p.next = cycle;

}

void show(Node head) {

// **** special case ****

if (head == null) {

System.out.println(“show <<< list: null”);

return;

}

// **** traverse list ****

System.out.print(“show <<< list: “);

int i = 0;

for (Node node = head; (node != null) && (i <= MAX_SIZE); node = node.next, i++) {

System.out.print(node.data + ” “);

}

System.out.println();

}

}

public class Solution {

    static boolean hasCycle(Node head) {

       // **** check for null head condition ****

       if (head == null) {

              return false;

       }

       // **** count nodes in the list ****

       int count = 0;

       for (Node p = head; (p != null) && (count < 100); p = p.next, count++) {}

       // **** ****

       return (count >= 100);

    }

public static void main(String[] args) {

// **** instantiate an empty list ****

Node head = null;

// **** get number of elements ****

Scanner sc = new Scanner(System.in);

System.out.print(“main <<< N: “);

int N = sc.nextInt();

// **** close scanner ****

sc.close();

// **** start with a head node (if needed) ****

if (N > 0) {

// **** ****

head = new Node(1);

// **** check (update if needed)  ****

if (N > head.MAX_SIZE) {

N = head.MAX_SIZE;

}

}

// **** loop building list ****

for (int i = 2; i <= N; i++) {

head = head.append(head, i);

}

// **** make list cycle (if needed) ****

if ((N != 0) && (N % head.CYCLE_MOD) == 0) {

head.makeItCycle(head);

}

// **** show the contents of the list ****

if (head != null) {

head.show(head);

}

// **** check if list has cycle ****

boolean cycle = hasCycle(head);

System.out.println(“main <<< cycle: ” + cycle);

// *** check if we do not have a cycle ****

if ((N != 0) && ((N % head.CYCLE_MOD) == 0)) {

if (!cycle) {

System.out.println(“main <<< should HAVE cycle !!!”);

}

}

}

}

Please note that the actual code for the solution is in the hasCycle() method. The rest of the code was used to experiment and test.

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *