Linked lists

**fnoyan** · 10-05-2016

Hi there,

I have a simple linked list composed of an int a pointer.

The code below compiles and runs fine, but I wonder whether I am wasting memory (or implementing the list in an inappropriate way) by keeping one nullified structure at the end of the list.

Thanks in advance...

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

struct my_node{
	int num;
	float sqr;
	struct my_node *next;
};

void list_print(struct my_node *l){
	struct my_node *head = l;

	while (head->next != NULL){
		printf("%d\t->\t%.0f\n",head->num , head->sqr);
		head = head->next;
	}
}

int list_count(struct my_node *l){
    int c=0;
    struct my_node *head = l;

    while (head->next != NULL){
        head = head->next;
        c++;
    }

    return c;
}

int main(){
	int r, i;
	float p;
	time_t t;
	struct my_node *head, *new_node;

	srand((unsigned) time(&t));

	head = (struct my_node*)malloc(sizeof(struct my_node));
	new_node = head;

	i = 0;
	while (i<3) {
		r = rand() % 50;
		p = pow(r,2);
		printf("%d\t->\t%.0f\n",r , p);

		new_node->num = r;
		new_node->sqr = p;
		new_node->next = (struct my_node*)malloc(sizeof(struct my_node));
		memset(new_node->next, 0, sizeof(struct my_node));
		new_node = new_node->next;

		i++;
	}

	printf("\n----------------------------\n\n");

	list_print(head);

	printf("list count = %d\n", list_count(head));

	return 0;
}

**laserlight** · 10-05-2016

Originally Posted by fnoyan

The code below compiles and runs fine, but I wonder whether I am wasting memory (or implementing the list in an inappropriate way) by keeping one nullified structure at the end of the list.

It looks like a logic error: if you have a node memset to zeroes at the end, it might help you to append to the list more easily since you have a ready-made new node at the end to populate, but it also means the typical head->next != NULL check no longer works as on the conceptual last node, its next pointer would not be a null pointer, but rather will point to this nullified node.

A better method would be to keep track of both head and tail, so when you want to append, you just append to the tail, e.g.,

Code:

struct my_node *head = NULL;
struct my_node *tail = NULL;
struct my_node *new_node = NULL;

for (i = 0; i < 3; i++) {
    new_node = malloc(sizeof(*new_node));
    if (new_node) {
        r = rand() % 50;
        p = pow(r, 2);
        printf("%d\t->\t%.0f\n", r, p);

        new_node->num = r;
        new_node->sqr = p;
        new_node->next = NULL;

        if (head) {
            tail->next = new_node;
        } else {
            head = new_node;
        }
        tail = new_node;
    } else {
        /* report an allocation error and end the loop/program? */
    }
}

Incidentally, you probably should just write r * r instead of calling pow.

Thread: Linked lists

Thread Tools

Search Thread

Display

Linked lists

Similar Threads

Double Linked Dynamic Lists Vs Unrolled Linked Lists

Suggestions on how to traverse a linked list of linked lists as if it is a 2D-Vector?

Question about Linked lists of lists

question on linked lists(stack with linked lists)

Linked List of Linked lists Revisited.

Tags for this Thread