class Node
{
    char element;
    int next;
}

class SinglyLinkedList
{
    Node []space = new Node[100];
    int head = -1;
    int tail = -1;
    int size = 0;

    InsertBeginning(char val)
    {
        index = mymalloc(space);
        space[index].element = val;
        space[index].next = -1; // in general

        space[index].next = head;
        head = index;
    }
    etc., etc.
}

how do we allocate this memory from the array?

i gave an example, using a linked list, where each node had a start position and a length property.

but however you do it, malloc


summary of data structure: using xor, we can use a single link field to navigate a linked list in either direction. we need a history of the previous element, xor it with link field, that yields address of 'next' / 'prev' element.

Related to a midterm question. *Print* a singly linked list in reverse order.

main()
{
    print_reverse(head);
}
void print_reverse(Node *current)
{
    if (current == NULL)
        return;
    else
        print_reverse(current->next);
    cout << current->value << " ";
}

note to self: still need to see recursive reverse


"unrolled linked list"
http://en.wikipedia.org/wiki/Unrolled_linked_list