## Insert Into A Cyclic Sorted List

### August 16, 2011

Today’s task comes to us from i has 1337 code:

Given a cyclic list with elements in sorted order, write a function to insert a new element into the cyclic list that maintains the sorted order of the cyclic list. Do not assume that the cyclic list is referenced by its minimal element.

Your task is to write the function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Here’s my clojure solution. I’ve got more detail at my blog

In Lisp, the nodes are predefined (they’re called CONS cells).

We can use the standard operators PUSH and POP to insert an element in a circular list and advance into the circular list.

Here are my solutions in both Racket and C: https://github.com/adolfopa/programmingpraxis/tree/master/2011/20110816. The racket one is virtually the same you provide here, but using mutable conses instead of regular ones.

My java solution (class Elem has only the fields value and next):

public static void addToList(Elem start, int x) {

Elem i, newElem;

for(i=start;;i=i.next){

if(

(x

i.value) ||(x<i.next.value && i.next.value

i.value && i.value>i.next.value)){

newElem=new Elem();

newElem.value=x;

newElem.next=i.next;

i.next=newElem;

return;

}

}

}Here is my solution in C#:

///

/// This method adds an int element to a cyclic sorted list of int elements.

///

/// Integer element to be inserted

/// Pointer to a node in the cyclic sorted list

///

/// List of all elements in the list starting from nodePtr.

/// The return value is really a test hook.

///

public List AddElementAndGetFullListOfElements(int element, Node nodePtr)

{

Node newNode = new Node(element);

// if list has no node, make newNode the first node and return

if (null == nodePtr)

{

_listPtr = newNode;

newNode.NextPtr = newNode;

return GetListOfElements(nodePtr);

}

// if list has only one node, insert newNode as the next element

if (nodePtr.NextPtr.Equals(nodePtr))

{

InsertNodeAfterCurrentNode(newNode, nodePtr);

return GetListOfElements(nodePtr);

}

Node currentNode = nodePtr;

Node nextNode = nodePtr.NextPtr;

do

{

// if currentNode <= newNode <= nextNode : Insert the number

// ahead of the currentNode

if (currentNode.Element <= newNode.Element &&

newNode.Element <= nextNode.Element)

{

InsertNodeAfterCurrentNode(newNode, currentNode);

return GetListOfElements(nodePtr);

}

// if currentNode = nextNode.

// currentNode points to list’s end.

// Insert the number ahead of the currentNode.

if (currentNode.Element >= nextNode.Element &&

newNode.Element >= currentNode.Element)

{

InsertNodeAfterCurrentNode(newNode, currentNode);

return GetListOfElements(nodePtr);

}

// currentNode >= nextNode. newNode = nextNode.Element &&

newNode.Element <= nextNode.Element)

{

InsertNodeAfterCurrentNode(newNode, currentNode);

return GetListOfElements(nodePtr);

}

currentNode = nextNode;

nextNode = currentNode.NextPtr;

} while (!currentNode.Equals(nodePtr));

throw new Exception("Error : Unable to find a place to insert the new element in the list.");

}

private void InsertNodeAfterCurrentNode(Node newNode, Node currentNode)

{

Node nextNode = currentNode.NextPtr;

newNode.NextPtr = nextNode;

currentNode.NextPtr = newNode;

return;

}

******************* TEST CODE ****************************************************************************

private static List givenList = new List() { 2, 3, 4, 5, 7 };

///

/// Insert minimum element to the list

///

[TestMethod()]

public void AddMinimumElement()

{

CyclicSortedList target = new CyclicSortedList(givenList);

int elementToInsert = 1;

Node nodePtr = target.GetXthNode(0);

List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);

List expectedList = new List(givenList);

expectedList.Add(elementToInsert);

if (!CheckArrayEquality(expectedList, actualList))

{

Assert.Fail(“Error : Method returned an unexpected list.”);

}

}

///

/// Insert maximum element to the list

///

[TestMethod]

public void AddMaximumElement()

{

CyclicSortedList target = new CyclicSortedList(givenList);

int elementToInsert = 10;

Node nodePtr = target.GetXthNode(0);

List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);

List expectedList = new List(givenList);

expectedList.Add(elementToInsert);

if (!CheckArrayEquality(expectedList, actualList))

{

Assert.Fail(“Error : Method returned an unexpected list.”);

}

}

///

/// Insert greater element to the list. Greater element is bigger than the list pointer

/// but smaller than maximum number in the list.

///

[TestMethod]

public void AddGreaterElement()

{

CyclicSortedList target = new CyclicSortedList(givenList);

int elementToInsert = 6;

Node nodePtr = target.GetXthNode(1);

List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);

List expectedList = new List() { 3, 4, 5, 6, 7, 2 };

if (!CheckArrayEquality(expectedList, actualList))

{

Assert.Fail(“Error : Method returned an unexpected list.”);

}

}

///

/// Insert smaller element to the list. Smaller element is smaller than the list pointer

/// but greater than the smallest number in the list.

///

[TestMethod]

public void AddSmallerElement()

{

CyclicSortedList target = new CyclicSortedList(givenList);

int elementToInsert = 6;

Node nodePtr = target.GetXthNode(4);

List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);

List expectedList = new List() { 7, 2, 3, 4, 5, 6 };

if (!CheckArrayEquality(expectedList, actualList))

{

Assert.Fail(“Error : Method returned an unexpected list.”);

}

}

///

/// Insert identical element to the list where all elements are identical.

///

[TestMethod]

public void AddIdenticalElement()

{

CyclicSortedList target = new CyclicSortedList(new List() { 1, 1, 1, 1, 1 } );

int elementToInsert = 1;

Node nodePtr = target.GetXthNode(0);

List actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);

List expectedList = new List() { 1, 1, 1, 1, 1, 1 };

if (!CheckArrayEquality(expectedList, actualList))

{

Assert.Fail(“Error : Method returned an unexpected list.”);

}

}

Complete Visual Studio Project is at my website.

My website is here: http://tech-nuggets.blogspot.com/2011/08/insert-into-cyclic-sorted-list.html