linked list - when to use?

hi,

can anyone tell me when i "should" be using linked lists? i know this is a very broad question, but i'm just trying to figure out when they would work better than just using an array.

thanks!

Essentially, arrays and linked-lists can be used interchangeably. It really depends on the situation though. You have to think of the pro's and con's of each:

Arrays
Pros

• Easy pointer manipulation (i.e. You can just used indexes)
• Easier to read and understand by the programmer
• A fixed size (this can be a good thing if you don't want something getting too big)

Cons

• A fixed size (this can be a bad thing considering that it limits your space)
• You have to think of a size for the array that will accomodate any situation while not being too astronomical.

Linked-Lists
Pros

• Not fixed size. Can accomodate any amount of data (given the hardware)
• You can create nested lists within the list (very useful for trees)

Cons

• Not fixed size. Things can go out of hand sometimes.
• Tougher pointer manipulation. (You have to keep track of where everything is pointing).
• To access any node, you must travel through all of the previous nodes

I think some great uses for Arrays would be stacks, FIFO's, and other simple data constructs.

Some great uses for Linked-Lists would be Binary trees, 2-3 Trees, and basically things you aren't sure how large they are to be.

I hope that helped clear things up.

Some more pros/cons:

arrays::

pro:

- compiler generates very fast iteration code since the cells are guaranteed to be side-by-side in memory.

con:

- to remove an item you must effectively shift an entire chunk of cells over, which can be quite inefficient.

lists::

pro:

- to remove an item, simply "detach" it from the list and place it somewhere else/destroy it quite easily and efficiently.

con:

- when sorting a list, it is difficult to implement the more efficient techniques, such as quicksort. This is mainly because these algorithms rely on indexes to navigate.

You should be using linked lists when you don't need random access or sortedness, searching is not done often, but you will be doing a lot of insertions and deletions, especially if those insertions/deletions are in the middle of the sequence.

Basically, insertions and deletions are really fast in a linked list, but it suffers from not being able to access arbitrary elements quickly.

that's exactly what i thought. thanks very much to all of you!!