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!
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.
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
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!!