How to create a linked list of OneTwoThree with a minimum number of assignment operators?

Question

I ran into this problem in preparation for an interview, and I am curious to know how this can be written. I found this at http://cslibrary.stanford.edu/103/ and asked the problem as is.

here is the code to create 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 least number of assignments (=) that will create over the memory structure. A: To call malloc (), 3 calls are required. 3 assignments int (=) to configure ints. 4 pointers for head installation and 3 following fields. With little mind and knowledge of the C language, all this can be done using 7 assignment operations (=).

Answer 1

I did this with six tasks. What can 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; } 

---

In addition, exercise is not very useful. If I wanted to create a linked list from a known set of integers, I would 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 create an arbitrary list with

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

---

Here's another version using one task, inspired by the codological 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 changed the MSN solution - now there is no purpose:

 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 2

 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 is the one that does this 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 3

A small modification of Christophe’s code with 4 assignments using the fact that he always creates 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 structure initializer is likely to result in at least two assignments, one for each element. Thus, it appears only as 4 destinations in C code, when it is a fact of 7 or more. Similarly, the MSN recursive solution will also result in more than two assignments that abstract in the recursion (not counting the additional assignments that are likely to arise from the overhead of the functions, assuming they are not included).

---

EDIT:

Well, it is globally allocated, so there are no assignments even in the assembly. Awful code how far related lists (or something 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 select all three nodes with a single call to malloc() . I suspect this is the answer they are looking for. Although reducing the number of assignments is not a practical problem, combining multiple allocations into a single malloc() can simplify memory management. I expect most senior C developers to 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

Since no one said anything about this other than C ++, here is a version of C ++ without assignments other than 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; }