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

Well, you can traverse the list to calculate the count pretty easily. Obviously the total memory will be equal to the number of items multiplied by size of each item (sizeof(Data_Struct)).

Of course, this will be the size of the linked list itself and doesn't include the memory allocated for the strings. A pointer doesn't have any information about the amount of allocated memory it refers to, so strictly speaking, you can't calculate the amount of total memory allocated directly by just looking at a linked list like that. Additionally, there may be duplicate pointers in the linked list you will need to keep track of. That said, assuming all pointer are unique, you can calculate the number of chars in each item by summing up return values of strlen calls on each pointer as you are traversing the list (which should be pretty straightforward).

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)

Answer 3

Keep a running count as you add or remove nodes. That way, you don't have to walk the list, summing up each node each time you want the count. Simply reference your up-to-date value.

Answer 4

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 5

To calculate the size of the list itself, just take sizeof(MyData) and multiply by the number of nodes.

If you want to include the size of the string data in the list, you can calculate the memory used by a string as (strlen(str) + 1) * sizeof(char) - that is assuming of course that the string was allocated to exactly the right size.

Answer 6

If you need to get the size of the data more than once, then it would be wiser to keep track of it as you added elements to the list, but the code to figure it out brute force is pretty easy.

 size_t cb = 0;
 int    cItems = 0;
 struct Data_Struct * pnext = &MyData;
 while (pnext)
    {
    if (pnext->Name)
       cb += (strlen(pnext->Name)+1) * sizeof(char);
    if (pnext->Task)
       cb += (strlen(pnext->Task)+1) * sizeof(char);
    if (pnext->Pos)
       cb += (strlen(pnext->Pos)+1) * sizeof(char);
    ++cItems;
    pnext = pnext->Next;
    }

 // cb has the total size of the strings, now add the size of the data structs
 cb += sizeof(struct Data_Struct) * cItems;

Answer 7

You can iterate through all the members of your list and accumulating the number of characters on Name, Task, and Pos.

However, if you are going to do this several times, I would store the number of characters of every field when populating the node instead of counting them once and once again.

So, your structure would be defined as follows:

struct Data_Struct {
    char *Name;
    int   NameCount;

    char *Task;
    int   TaskCount;

    char *Pos;
    int   PosCount;
    struct Data_Struct *Next;
};
typedef struct Data_Struct MyData;

and iterating through the list could be something like:

void getCharacterCount(struct Data_Struct* data, int* nameCount, int* taskCount, int* posCount)
{
  struct Data_Struct* auxData = data;
  int nc = tc = pc = 0;

  for (; auxData; auxData = auxData->Next())
  {
    nc += auxData->NameCount; 
    tc += auxData->TaskCount;
    pc += auxData->PosCount;
  }

  *nameCount = nc;
  *taskCount = tc;
  *posCount  = pc;
}