Which is a more efficient implementation of a linked list?

Question

There are at least two ways to represent a linked list:

1.)Using an array based representations of the linked list, where we keep an std::vector of structs of the type

struct {
    <whatever-type-you-want> item ;
     int   nextitem; 
   }

Here inserting into the list, is doing a push_back() on the vector and giving an appropriate value to next-item.

2) In which you have a collection of structs all over RAM. Here insert is done with the C++ operators new .

Is it correct to say, that the first method is more efficient since all the items are in consecutive locations in memory, because of which one might be able to grow the linked list to a much larger size than the second method

In the second method, there might be memory fragmentation with huge linked lists because of which one might get a segmentation fault much earlier.

Answer 1

I'll go against everyone else here and say that, yes, the first approach might end up being more efficient. In the second approach, you're allocating memory on the heap O(N) times - N being the number of nodes in the list. If you're using a vector, you're only making O(log N) number of heap allocations.

Also, if you're on a 64 bit machine, the overhead of saving a pointer in each node may be a bit too much if you're dealing with lots of small items. Using a vector, you can use a smaller nextItem - e.g. 32 bit instead of 64, which, if you're making a list to hold 32 bit ints, would be a 1.5 improvement in memory usage.

Another possible optimization is that if you know up-front that you'll be dealing with a lot of elements, you can reserve a big vector and have a single heap allocation for a pretty long time.

I recently took a course on applications of automata and the lecturer is implementing some of the algorithms for pretty large data sets. One of the techniques he told us was exactly your first approach of representing a linked list. I had a course work that I tried implementing both ways (with pointers and with a vector and nextItem kind of thing) and the vector one was acting much better (it did have other optimizations too, but the vector definitely had an effect).

NOTE TO OTHERS

I think what @smilingbuddha is asking about is more like a collection of linked lists - or at least that's what I've used it for. For example, when you save a graph using a list of neighbors. You need a linked list (or array, or whatever) of all the neighbors for each node. So instead of keeping an array of linked lists or a vector of vectors, you just keep of array of indexes pointing to the last inserted neighbor for every node.

Answer 2

Implementing a list with a vector is misguided.

---

I'll explain. Containers are typically designed to achieve a certain set of goals, and the underlying implementation is selected based on those goals.

A vector is very good because it has contiguous memory and you can reach any cell by pointer arithmetic. Unfortunately, a vector has terrible performance when inserting or deleting an element in the center of the vector.

A list has the exact opposite intention. Navigating to a point in a list is time consuming because you have to follow links because its not contiguous. BUT the primary purpose of a list is to allow fast insertions, deletions, reordering, splicing, reversals, etc.

---

So, thinking of a vector as an implementation base for a list (while can be done) really isn't the way to look at this. Implementing a list with a vector would basically mean you didn't have any of the advantages that made you choose a list in the first place.

---

EDIT

As other people have pointed out in the comments below, if you're thinking of more complex implementations, you could definitely get performance benefits out of this.

For example, if you maintain a vector with references to all of the pointers, and you work to keep that reference vector in order, you can have the benefits of pointer-arithmetic access while still having relatively fast removal/insertion, etc. Also, since the reference vector just holds pointers to dynamically allocated objects, manipulating the reference vector isn't costly and you still don't have to have a massive region of contiguous memory being used (the vector would just be NumElements * sizeof(pointer) on your architecture).

You should look at a std::deque implementation for some fun. They have some interesting interplay between contiguous memory regions linked by pointers to speed up insert/delete/other operations.

Answer 3

On the contrary; using your first method, it is inefficient to remove items from the linked list as you "lose" the slot in the vector where that item was stored and would have to walk the whole list in a garbage-collection style to discover which slots are not being used.

With regard to memory fragmentation, having lots of small allocations is not an issue generally; indeed as a vector is required to be contiguous allocating the memory for it will cause fragmentation as you require larger and larger blocks of contiguous memory. In addition, each time the vector is resized you are causing the copying of large blocks of memory.

In fact, your first answer is arrogating to yourself the job of the memory allocator and memory management unit. The job of the memory allocator is to hand out small chunks of memory; the job of the MMU (among others) is to ensure that pointers between blocks of memory continue to point to the same logical memory even when moved around in physical memory. Your nextitem int members are essentially functioning as pointers. Unless you have very specialised requirements, the hardware, kernel and malloc can do this job far better than you can.

Answer 4

Your logic is completely backwards. The first approach requires that memory be contiguous and will fail as soon as insufficient contiguous memory is available. Your second approach can use memory whether contiguous or not and will continue to work until no memory at all remains.

Answer 5

Your first approach seems to blend two algorithms and, therefore, I would say is less efficient.

One of the advantages of a linked list is that items can easily be inserted and deleted. Yet using your approach, they require shifting data around. You may as well use a simply resizable array.

In addition, an array requires memory to be contiguous. In some circumstances, you will run out of memory sooner than with a true linked list when working with large amounts of data because there may be times when a certain amount of memory is available, but not contiguously.

Answer 6

If you remove an element from the list in the case #1, a good part of the remaining elements may get their nextitem indexes messed up. So #2 is the usual way to go and won't cause any memory problems if properly implemented, unless you try to insert an insane number of elements into the list, or any other container for that matter.