3

I've got a question if it's possible to do that?

One man said to me that i can do something like this:

struct Node
{
  int data;
  int NextIndex;
}

But I am not sure if I should not use pointers at all.

James Cornod
  • 39
  • 1
  • 4
  • Why do you want to avoid pointers? – Maya Jun 30 '17 at 13:04
  • Yes, it's possible. Keep searching, and think about what a pointer really models ;) – Quentin Jun 30 '17 at 13:04
  • From Wikipedia: In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. So I would say no, it's not. But then again I could be wrong. – Rivasa Jun 30 '17 at 13:05
  • 1
    I guess you could, but what is `NextIndex`? How does this know where the next element of the linked list lives? Is it the integer value of a memory address? Because that's just a pointer, but one that will cause you huge headaches because you will have to separately manage the memory outside both this struct and c++'s standard memory management operators... – PaSTE Jun 30 '17 at 13:05
  • 1
    Well, if you keep an array/vector of all nodes and `NextIndex` points to an index in that array, then yeah, why not? But that sounds like a real overengineering. – freakish Jun 30 '17 at 13:07
  • 1
    Such a model would be useful if **array of struct** is used as to implement a linked list and adjacent elements in the array are not adjacent elements in the linked list. – GAURANG VYAS Jun 30 '17 at 13:08
  • @NieDzejkob I dont really want to avoid it, that's kind of my home work – James Cornod Jun 30 '17 at 13:09
  • Advantage of storing indices: Requires less memory, assuming that an index requires less storage than the 64bit of a pointer in a 64bit system. Disadvantage: When deleting entries, you get holes that you have to deal with in some way. If deleting occurs rarely or not at all, this is not an issue at all, obviously. If deleting occurs frequently, you might end up with a lot of wasted space, especially if you have no way to fill it again. In any case, such a structure should be encapsulated. There must not be any way to change the index directly. Btw, why is NextIndex in upper case? – Aziuth Jun 30 '17 at 13:14

1 Answers1

3

I've done that many times (I work in embedded systems, so I use tricks like this). The advantage of using indexes is that an index uses less memory than a pointer (usually a uint8_t or uint16_t), so if memory is a concern, you can do that.

You are limited to using a single array in that case (because the index has to be relative to that). Because you are not doing dynamic allocation, in this case, insertion and deletion is very quick. Notice though that you can use pointers in an array as well, and if you're optimizing for time, then this is even faster than indexes (on most architectures I've worked on anyways).

As far as using the next pointers, you allocate a large array, and create a free head which points to the first element, and then make all elements point to the next one, so essentially you have a free-linked-list. If you want to use an element, you pop it from the free list, and push it onto the new list you wish to use. When you free an element, you simply push it back onto the free list.

blackghost
  • 1,730
  • 11
  • 24
  • Access is also faster in array implementation due to locality of reference. Am I right ? – GAURANG VYAS Jun 30 '17 at 13:21
  • @John can you provide a simple implementation. – ytobi Jun 30 '17 at 13:31
  • That depends on a lot of things. If you have multiple entries on the same cache line, then it definitely would improve average access time. Which brings up an interesting point -- I wonder how hard it would be to implement a list that would favor allocating entries adjacent to entries you're planning to link to... – blackghost Jun 30 '17 at 13:33