Build OnetwoThree linked list with minimum assignment operators

Question

I came across this problem while preparing for an interview and curious to know the diffrent ways it can be written. I found this at http://cslibrary.stanford.edu/103/ and have given the problem as it is.

here is a code to build the list {1,2,3}

struct node* BuildOneTwoThree() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    head = malloc(sizeof(struct node)); // allocate 3 nodes in the heap
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));
    head->data = 1; // setup first node
    head->next = second; // note: pointer assignment rule
    second->data = 2; // setup second node
    second->next = third;
    third->data = 3; // setup third link
    third->next = NULL;
    // At this point, the linked list referenced by "head"
    // matches the list in the drawing.
    return head;
}

Q: Write the code with the smallest number of assignments (=) which will build the above memory structure. A: It requires 3 calls to malloc(). 3 int assignments (=) to setup the ints. 4 pointer assignments to setup head and the 3 next fields. With a little cleverness and knowledge of the C language, this can all be done with 7 assignment operations (=).

Answer 1

node= malloc
node->data= 1
node->next= malloc
node->next->data= 2
node->next->next= malloc
node->next->next->data= 3
node->next->next->next= NULL

And here's one that does it with two:

node *make_node(node *new_node, int data, node *next) 
{ new_node->data= data; new_node->next= next; return new_node; }

node *create_node(int data, node *next) 
{ return make_node((node *)malloc(sizeof(node)), data, next); }

node *BuildOneTwoThree(void) 
{ return create_node(1, create_node(2, create_node(3, NULL))); }

Answer 2

I did it with six assignments. What do I get?

struct node
{
    int data;
    struct node * next;
};

struct node * build_123()
{
    struct node * first = malloc(sizeof(*first));
    struct node * second = malloc(sizeof(*second));
    struct node * third = malloc(sizeof(*third));

    assert(first && second && third);

    *first = (struct node){ 1, second };
    *second = (struct node){ 2, third };
    *third = (struct node){ 3, NULL };

    return first;
}

---

Also, the exercise isn't very useful. If I wanted to build a linked list from a known set of integers, I'd do something like this:

struct node
{
    int data;
    struct node * next;
};

#define build_list(...) \
    _build_list((sizeof((int []){ __VA_ARGS__ }))/(sizeof(int)), \
    (int []){ __VA_ARGS__ })

struct node * _build_list(size_t count, int values[count])
{
    struct node * next = NULL;

    for(size_t i = count; i--; )
    {
        struct node * current = malloc(sizeof *current);
        assert(current);
        *current = (struct node){ values[i], next };
        next = current;
    }

    return next;
}

Then, you can build an arbitrary list with

struct node * list = build_list(1, 2, 3);

---

Here's another version using a single assignment, inspired by codelogic's answer:

struct node * build_123(void)
{
    struct node * list = malloc(sizeof(struct node [3]));
    return memcpy(
        list,
        (struct node []){ { 1, list + 1 }, { 2, list + 2 }, { 3, NULL } },
        sizeof(struct node [3])
    );
}

---

Finally, I slightly modified MSN's solution - now, there's no assignment at all:

struct node
{
    int data;
    struct node * next;
};

struct node * make_node(struct node * new_node, int data, struct node * next)
{
    return memcpy(new_node, &(struct node){ data, next }, sizeof(*new_node));
}

struct node * create_node(int data, struct node * next)
{
    return make_node(malloc(sizeof(struct node)), data, next);
}

struct node * build_123(void)
{
    return create_node(1, create_node(2, create_node(3, NULL)));
}

Answer 3

Slight modification of Christoph's code with 4 assignments using the fact that it's always building 3 nodes:

struct node
{
    int data;
    struct node * next;
};

struct node * build_123()
{
    struct node* head = malloc( sizeof(struct node) * 3);
    *head     = (struct node){ 1, head+1 };
    *(head+1) = (struct node){ 2, head+2 };
    *(head+2) = (struct node){ 3, NULL };
    return head;
}

EDIT: Technically (in terms of assembly), using a struct initializer would probably result in at least 2 assignments, one for each member. So it only appears like it's 4 assignments in C code, when it fact it is 7 or more. Similarly, MSN's recursive solution will also result in more than 2 assignments, which is abstracted in the recursion (not counting the additional assignments that will likely occur due to function overhead, assuming it's not inlined).

---

EDIT:

Ok, allocated on the stack globally, hence no assignments, even in assembly. Terrible code as far linked lists (or anything else) goes, but whatever :-)

struct node
{
  int data;
  struct node * next;
};

struct node g_nodes[3] = { {1, g_nodes+1}, {2, g_nodes+2}, {3, NULL} };    
struct node * build_123()
{
  return g_nodes;
}

Answer 4

You can allocate all three nodes with a single malloc() call. I suspect this is the answer they're looking for. While reducing the number of assignments isn't a practical issue, bundling multiple allocations into a single malloc() may simplify memory management. I expect that most senior C developers would be familiar with this technique.

struct node* BuildOneTwoThree() {
    struct node *list = malloc(3 * sizeof(struct node));

    list[0].data = 1;
    list[0].next = list+1;
    list[1].data = 2;
    list[1].next = list+2;
    list[2].data = 3;
    list[2].next = NULL;

    return list;
}

Answer 5

As no-one said anything about this not being C++, here's a C++ version with no assignments except in the test code:

#include <iostream>
using namespace std;

struct Node {

    int mVal;
    Node * mNext;

    Node( int v, Node * n ) 
        : mVal( v ), mNext( n ) {}

    ~Node() {
        delete mNext;
    }
};

int main() {

    // build the list
    Node n( 1, new Node( 2, new Node( 3, 0 ) ) );

    // test it
    Node * p = & n;
    while( p ) {
        cout << p->mVal << endl;
        p = p->mNext;
    }

    return 0;
}