Linked list without pointers... Old school style. Or at least my father tells me that they used to do linked lists like this with arrays. But unfortunately it uses arrays which will disqualify it for this challenge:
int next; // Contains the index of the next Node. 0 means end of list.
// Node 0 is also used to store the head index.
arr.next = 0;
// Set up the free list
for(int i = 1; i < MAX_SIZE - 1; i++)
arr[i].next = i + 1;
arr[MAX_SIZE - 1].next = 0;
freeList = 1;
bool Append(char ch)
if (freeList == 0)
return false; // no more room
int current = 0;
while (arr[current].next != 0)
current = arr[current].next;
arr[current].next = freeList;
current = freeList;
freeList = arr[freeList].next;
arr[current].data = ch;
arr[current].next = 0;
This post has been edited by jimblumberg: 25 August 2012 - 01:54 AM
Reason for edit:: Added spoiler tags
so basically it uses its own allocator with a fixed amount of memory. wouldn't pointers still be slightly more efficient because you wouldn't have to waste the cycles adding the index and the base pointer? just a conjecture, maybe it wouldn't work.
I think it really depends on the machine and how the compiler generates the code, but in general, I think the pointer will win out by having one less operation.
Anyway, thanks to jimblumberg for moving the code into spoiler tags. When I originally posted the code, I deliberately did not put the code in spoiler tags because I was thinking that by implementing Append(), rather than an InsertAtFront(), I was avoiding any hint of trying to solve the challenge listed here. An insert at front would then let you get the reversed string by traversing the list from head to tail and get the string in reverse order. With append, I now realize that you can recursively traverse the list and display the contents in reverse order. But still, this is a no-go since it uses an array.
This post has been edited by Skydiver: 25 August 2012 - 03:28 PM
I guess I'll try a linked list solution. The rules say you can't use "pointers", I'm not sure if that includes references or not, but here's my linked list solution using temporary references and polymorphism