Total size of a linked list in C

Question

Alright... my Introduction to Data Structures from CS is so rusty I need to ask this here.

I have a linked list whose structure is:

struct Data_Struct {
    char *Name;
    char *Task;
    char *Pos;
    struct Data_Struct *Next;
};
typedef struct Data_Struct MyData;

Now, at some point in my application I filled the list with data.

The question is, how do I get the total size of the data stored in there? How many chars are there? Something like

sizeof(MyData);

That will return the size of the info stored in the list.

code is appreciated.

Thanks!

EDIT: Unfortunately this is NOT homework. I finished school more than 20 years ago and frankly i never ever had to use linked lists on anything. I just don't remember. What I am doing is iterate the list and get the strlen() of each element and keep it on a global size but I wanted to know if there was a better way.

and NO, I don't need the size of the linked likes (the count of nodes), i just want to know how many characters are stored in there.

thanks

Answer 1

You usually go through the list until you reach the tail item while counting in the meanwhile, code should be something like that:

int listLength(struct Data_Struct* item)
{
  struct Data_Struct* cur = item;
  int size = 0;

  while (cur != null)
  {
    ++size;
    cur = cur->Next;
  }

  return size;
}

Mind that complexity of this operation is linear with the size of the list, so it's O(n) and it's quite inefficient. You could store size somewhere and update with list insertions and deletes to avoid any overhead and being able to calculate it in a constant time O(1).

EDIT: Didn't notice you wanted size of the whole data included into the list. In your case you can keep the same approach used for calculating the length but instead that adding 1 for every element you should add the total length of strings:

size += strlen(Name)+strlen(Task)+strlen(Pos);

Mind that since data inside your list element if of type char* the effective size of the Data_Struct is just 4 pointers, that's why you need to use a support function like strlen, otherwise you can't get real dimension of the strings.

Which is the difference?

sizeof(Data_Struct) == 16

because the Data_Struct type contains 4 pointers, three for pointers to char and one for the next element in the list

sizeof(Name) == sizeof(Task) == sizeof(Pos) == 4

because these variables are of type pointer to char, so they are pointer, no concrete value, and it's usually 4 bytes (I'm assuming a 32 bit architecture)

strlen(Name) == length in chars of the string

because the function works exactly to calculate the length of a string.

Answer 2

Once you allocate memory for a node (using malloc) you should be able to do sizeof(yourDataType). So to get the total size of the linked list you traverse the list and get the count of nodes:

Total Size Of Linked List = SizeOf(One Node) * Count Of Nodes

For instance:

int getCountOfList()
{
 Node* temp = head; //assign a temp node to the head of the list
 int count=0;

 while(temp) {
  count++;
  temp = temp->next; //move to next node
 }
 return count;
}

Then you take that count and multiply by size:

size = getCountOfList * sizeof(mydatatype);

This will give you the size of the actual linked list but becareful as the linked list node has pointer elements which in and of themselves can allocate memory as well. This will need to be accounted for...

For instance, one of those char* elements within the node could malloc some more space and use up some memory.

If you actually need the entire size of the list including allocated elements for all other char* pointers for example, you simply:

1)Traverse the list and look into each node

2)For each node you check if the elements of each node point to any other allocation (for instance char* data may allocate 50 characters to store). If it isn't null you get the length of the string + 1 (for terminating char) and you multiply that by sizeof(char) (for this example)

3)You do that for each node and store that size, then move to next node

4)You take the SUM of all of these char* (in this case) for each node and accumulate for the entire list.

5)Once you have that simply add this sum that will give you the size of all nodes.

Then total size becomes:

SizeOfAllNode + (SizeOf(dataType) * CountOfNodes)