Linked lists alternatives?

I'm a C programmer and I "get" pointers. I like them quite a bit. But I'm really not too fond of is linked lists. Most of the time their complexity isn't needed. Yeah, they're necessary if you have to insert or remove stuff at any point or do lot's of searching or sorting, but if all you want is a linear list of stuff that you'll process in a sequential order, what alternatives are there and what do you prefer?

If you go about allocating each individual object one at a time, then an attractive option is an array of pointer to these objects with the array terminated by a NULL pointer:

typedef struct  _some_stuff SOME_STUFF;

SOME_STUFF **array_of_pointers_to_stuff;

But then you end allocating memory for each piece of data and then memory for pointers to all of the data (and the terminating NULL pointer). But, at the same time, you can much more easily manipulate the data:

SOME_STUFF **struct_pointer = array_of_pointers_to_stuff;

while (*struct_pointer)
{
      SOME_STUFF *stuff = *struct_pointer;
      ...
}

What do you prefer?

The Mountain Man of Park Avenue.
Monday, April 5, 2004

I use std::list when I have to insert and remove stuff a lot, and read/sort sometimes.  I use std::vector when I have to insert/remove stuff almost never, and read/sort frequently.

Kalani
Monday, April 5, 2004

If you know in advance the number of elements, why not just malloc() a simple array? Actually I prefer calloc() as it will clear the space and so you can be sure that it's really been allocated. Even if the number of elements changes you can always realloc() it, although clearly you don't want to do that too often.

fred
Monday, April 5, 2004

If you know that SOME_STUFF is going to be stored on a list, then you can put a pointer inside the struct itself:

typedef struct  _some_stuff
{
  SOME_STUFF* next_item;
  ... other elements ...
} SOME_STUFF;

Christopher Wells
Monday, April 5, 2004

Linked lists don't have any more complexity in day-to-day usage than anything else as long as you have a collection class and iterators to hide the complexity.  Why people refuse to do this is beyond me.

anon
Monday, April 5, 2004

Mountain man said he was a C programmer, not a C++ programmer.

C++ STL containers (std::list, std::vector, std::map, etc.) have changed my life.  But they are not available in straight C.  Nor are objects available in C.

Glade Warner
Monday, April 5, 2004

In plain flat C, I think I'd probably use arrays of structures and let the compiler worry about the addressing offsets if  I didn't care the order in which members of the list were stored.

But there's no reason why you can't implement a flattrunked tree with embedded pointers and then convert that to inorder/postorder if you needed to.

Simon Lucy
Monday, April 5, 2004

There exist numerous libraries to give C some C-style collections. There is really no good reason not no use them. Unless he's a student.

Anon to protect the guilty
Monday, April 5, 2004

Sorry buddy, but if you think linked lists are full of "complexity", then you're going to be SOL when you learn about more advanced data structures (hashtables, trees, etc). Linked lists are about as simple as it gets--they're basic comp101 stuff!

Sexist
Monday, April 5, 2004

> if you think linked lists are full of "complexity"

Compared to a simple array or struct, yes, they are. Linked lists always come with a handful of generic functions you need to learn how to use to manipulate them, and if you don't need to insert items or do any searching or sorting, then you don't need that added functionality.

I'm asking for preference here. E.g., if a function is gonna return a bunch of strings to you and you plan to process them one after the other, would you rather get them returned as a pointer to a linked list full of char *'s or as a pointer to an array full of char *'s with a NULL pointer at the end?

What do you prefer? Which do you use? Are there any simple alternatives you'd recommend?

The Mountain Man of Park Avenue.
Monday, April 5, 2004

IMHO, C is a terrible language for grinding through a list of strings. Why not use a language known for text processing like Perl? Or at least a language with built-in list/iterator capabilities like Python.

Anony Coward
Monday, April 5, 2004

Because sometimes you can't...

Jack of all
Monday, April 5, 2004

Back in my C days, I rarely used linked lists. Arrays are a lot more convenient. If I didn't know the size in advance, I started with some initial size and reallocated it to be twice is large whenever necessary.

Though linked lists are straightforward, arrays require fewer keystrokes and brain cells. CPU usage was also better, since you allocate memory log N times for N records, though you might waste some memory. Adding or removing objects from the middle, which is where linked lists shine, was hardly ever necessary.

Computer classes teach linked lists and similar structures. Though it's helpful background info and provides good pointer practice, there are easier ways to code.

Julian
Tuesday, April 6, 2004

It's pretty easy to write a generic doubly linked list implementation using macros in C.

Hint: create a macro to calculate the address of a containing structure based upon the offset of a data member.

SG
Tuesday, April 6, 2004

Grab list.h from the linux source code tree.  If you look at it there are 2 parts: 1 is a set of macros for dorking with doubly linked lists.  The other optimizes memory caching.  Delete the caching crap and you have some really nifty tools for working with linked lists.

Snotnose
Tuesday, April 6, 2004

OP: 'a linear list of stuff that you'll process in a sequential order'

I'm not a Comp Sci geek, but isn't this a queue?  Would that be easier to use?

Lee
Tuesday, April 6, 2004

Linked lists have their places.

If you find arrays easier to work with, go with it.  If you find you have big arrays and lots of shuffling, go migrate to a proper list.

One interesting type of array is the segmented array.  Combined with allocation bitmaps, it can make a good compromise between array and list.  In Symbian programming, where efficient memory usage is paramount but we want speed too, segmented arrays are extremely popular.

i like i
Wednesday, April 7, 2004

  Recent Topics

  Fog Creek Home