Free C / C++ / C# Newsletter!
Discuss in my Forum

Programming Challenge 6 - Now Completed

By David Bolton, About.com Guide

See More About:

The challenge this month is simple. Implement a function (or class member) in C, C++ or C# that takes as input a simple linked list and returns element n in the list where n is the number of nodes from the end of the list. in C or C++ a node looks like this:

typedef struct node * pnode;
struct node {
int value;
node * next;
};

pnode list;

in C#

  public sealed class node
    {
     private static Random Rnd = new Random() ;
     public int value=Rnd.Next(32000) ;
     public node next=null;
    }

You should implement a function GetElementFromEnd(pnode list,int index) (there's no pnode parameter in the C# version) which returns the value from the specified node, as fast as possible. The C++ version can use this C version or feel free to write it to use a class. On a 3 year old PC, the C version runs in under two seconds. The GetElementFromEndNode() as implemented only fetches the value at the last node.

The list is be populated with 10,000 random values (in the range 1 to 32,000) and your function will be called to fetch 10,000 of them in random order. To make it more challenging, you must NOT use any kind of index array or make any changes to the node struct or class or use a derived class.

To simplify this problem, I've provided source code examples for both C/C++ and C# which includes timing code. Just download the source code examples, flesh out the GetElementFromEnd(pnode list, int index ) function and submit your entire source code file. That's it!

Download fastlist.zip C/C++ Version
Download fastlistcs.zip C# Version

Results

There were seven entries, one of which didn't run - it hit an exception and two of which used index tables. Strangely enough those two got the fastest times and one used a construction I have never ever seen used- it's worth repeating below! Don't mock, though it was the fastest. However the challenge specifically excluded index tables.

#define P ptr=ptr->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next->next->next->next->next->next->next->next->next->next-> next->next

The fastest non-indexed are listed below: