Why do we need pointers in C implementation of a linked list?

Question

Why is it important to use pointers in an implementation of linked lists in C?

For example:

typedef struct item                                     
{
    type data;
    struct item *next;
} Item;

typedef struct list                                          
    Item *head;
} List;

What would happen if Ill use the same implementation just without the pointers?

Answer 1

Well you'll end up with something like this

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

and now the C compiler will go to try to figure out how large Item is. But since next is embedded right in Item, it'll end up with an equation like this

size-of-Item = size-of-type + size-of-Item

which is infinite. Hence we have a problem. Because of this, C requires pointers so you have

size-of-Item = size-of-type + size-of-pointer

which is closed. More interestingly, even when you do this in languages like Java, Python, or Haskell, you're really implicitly storing a pointer (they say reference) to break the cycle. They just hide the fact from you.

Answer 2

You do not actually need to use pointers to implement a data structure that exposes the interface of a linked list, but you do need them in order to provide the performance characteristics of a linked list.

What would the alternatives to pointers be? Well, item needs to have some way to refer to the next item. It cannot aggregate the next item for various reasons, one of them being that this would make the struct "recursive" and therefore not realizable:

// does not compile -- an item has an item has an item has an item has...
typedef struct item                                     
{
    type data;
    struct item next;
} Item;

What you could do is have an array of items and implement the linked list on top of that:

Item *storage[100];

typedef struct item                                     
{
    type data;
    int next; // points to the index inside storage of the next item
} Item;

This looks like it would work; you can have a function that adds items to the list and another that removes them:

void add_after(Item *new, Item *existing);
void remove(Item *existing);

These functions would either remove existing from the array (taking care to update the next "pointer" of the previous item) creating an empty slot, or find the existing item and insert new in an empty slot in storage (updating next to point there).

The problem with this is that this makes the add_after and remove operations not realizable in constant time because you now need to search into the array and reallocate it whenever you are out of space.

Since constant time add/remove is the reason people use a linked list for, this makes the non-pointer approach only useful as an intellectual exercise. For a real list, using pointers means you can perform these operations in constant time.

Answer 3

Without a pointer, each list item contains another list item (next) which contains another list item. Which in turn contains another list item. And so on.

You end up with an infinitely large data structure that would use an infinite amount of memory, and that of course can't work.

Answer 4

Pointers are used for dynamic allocation of memory.

You can implement a list as a simple array but that means that you allocate a continuous memory area, which for a large list is not efficient. Also, arrays are more difficult cu extend (you have to reallocate it if you reach its maximum size).

Therefore, dynamic allocation is preferred for large lists, and for each element it can allocate it into memory in any place, continuously or not, and you can extend it easily.

Also, you cannot store in an struct item another struct item because the structure is not defined yet and it cannot establish the size of the structure:

This cannot be done:

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

Therefore pointers are used because the size of a pointer can be determined (the size of an integer on that platform) when the structure is compiled.

Answer 5

You don't need a pointer to create a list in C. If a pointer list is preferable depends on your application. People used linked lists before they had a concept of pointers implemented in languages. It's only sometimes simpler to comprehend for some people (with pointers). You don't need a structure with data either.

A simple array will do fine. You need:

• one integer array to hold indices (this resembles the pointer). Array content is either -1 (means nil or NULL in pointer terminology), or 0 .. N-1, means: the array index of the next element linked. The index-array's index represents the item 's index in the data array.
• one array for any data to be 'connected' within the 'list' above.

That's all you need.

An array instead of a pointer list may have

• advantages, if the amount of your data doesn't change (doesn't grow). In this case, the advantages can be huge. If you know the maximum number of data you'll encounter and can allocate data beforehand, an array implementation will be much faster than any pointer-linked list. Especially, if you only insert, but don't need to remove.
• disadvantages otherwise. In this case, the disadvantages can be huge.

Please read up here.

Your example would, therefore, look like:

type data[N];  // or: type *data = new type [N];
int links[N];  // or:  int *links = new int [N];

That should be all you need to start with a simple test case.

Answer 6

Important of pointer in c

advantages:-

1. Execution speed will be high.

2. pointers allow us to access the variable which is outside of a function.

3. reduce the size of our code.

without pointers:-

1. Code size will get increase.

2. We cannot maintain the data efficiently.

3. In list the pointer is used to point the next item from the list.If you are not declared the pointers means you cannot access more than one item from the list.

4. If you allocate some memory dynamically at run time that time really the pointers are much needed.

Answer 7

There's more than one kind of "list". The implementation you show is a "Linked List". Without pointers there would be no "links", so we'd need to look at other kinds of lists.

So, first up, what happens if you just remove the * from the struct definition: it won't compile. You can include a struct inside of another struct, but if there's recursion then the structure will have infinite size that isn't going to happen!

How about an array as a list:

struct item list[100];

Yep, that'll work, but now your list is a fixed size.

Ok, so let's dynamically allocate the list:

struct item *list = malloc(sizeof(struct item));

Then, everytime you add to the list you'd have to do this:

list = realloc(list, newcount * sizeof(struct item));
list[newitem] = blah;

OK, that works, but now we're reallocating memory frequently, and that leads to lots of memory copies, and inefficiency.

On the other hand, if the list is updated very infrequently, this is more space-efficient, and that might be a good thing.

Another disadvantage of using an array is that operations such as push, pop, sort, reverse, etc. become much more expensive; they all mean multiple memory copies.

There are other kinds of "list", but they all involve pointers, so I think we can disregard them here.