What is a simple node?

Answer 1

In computer programming, a simple node is a structure that holds two pointers. The first pointer refers to the data that is indirectly associated with the node, while the other refers to the next node in the sequence. Simple nodes are typically used in forward lists (singly-linked lists) where we keep track of the head node only. The last node in the list refers to NULL as there can be no next node after the last node. We can insert new data into the list knowing only the address of the data. A new node is constructed which then refers to the data and to the current head of the list. The new node then becomes the head of the list. Insertions at the head are performed in constant time. Inserting anywhere else in the list requires that we traverse the nodes recursively, following each node's next pointer, starting from the head, stopping at the node that should come after the new node. That node then becomes the new node's next node (if the node reaches the end of the list, the next node is NULL). Since we traversed recursively, we can return the newly inserted node to the caller, which can then be assigned to the caller's next node. All other recursions simply return the node we traversed to, thus leaving the caller's next node unchanged.

The following example shows a simple node implementation for an ordered list of type int:

typedef struct Node_t { // a simple node

int* data;

Node_t* next;

} Node;

Node* insert (int* data, Node* node) { // insert data

if (!node *node->data > *data ) { // insertion point reached (end recursions)

Node* pnode = malloc (sizeof (Node)); // create a new node

pnode->data = data; // attach the data

pnode->next = node; // refer to the next node (may be NULL)

return pnode; // return the new node so the previous node can be updated

}

// if we get this far, the given node comes before the new data

// delegate to the next node, the return value is the new or existing next node

node->next = insert (data, node->next);

return node; // return the node (it remains the previous node's next node)

}

void print_all (Node* node) { // print the given node and all that follow it

while (node) {

printf ("%d ", *node->data);

node = node->next;

}

}

Node* destroy_all (Node* node) // destroy the given node and all that follow it while (node) {

Node* next = node->next; // refer to the next node (may be NULL)

free (node->data); // release the current node's data

free (node); // release the node itself

node = next; // make the next node current (may be NULL)

}

return node; // always NULL

}

int main(void) { // The test program...

srand ((unsigned) time (NULL)); // seed a random number generator

Node* head = NULL; // the head node of the list (initially NULL for an empty list)

for (int i=0; i<10; ++i) { // insert 10 random integers

int* pint = malloc (sizeof (int)); // allocate a new integer on the free store

if (!pint) break; // allocation failed, stop inserting!

*pint = rand () % 10; // assign a random integer value (range 0:9)

head = insert (pint, head); // insert the data (the return value is the new or existing head)

}

print_all (head); // print all the nodes starting from the head node

head = delete_all (head); // destroy all the nodes starting from the head (returns NULL)

return 0;

}