LinkBack URL
About LinkBackshi,
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!
This is a discussion on linked list - when to use? within the C++ Programming forums, part of the General Programming Boards category; hi, can anyone tell me when i "should" be using linked lists? i know this is a very broad question, ...
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:int main(void){srand(time(0));for(double l=rand(),l0=0,l00=0;;l0+=0.1){for(double l000=0;l000 <1;l000+=.001,l+=((double)rand()/RAND_MAX)/0x64,l00+=((sin(l*0x8*atan(l0)*l000-(l0*0x8*atan (l)))*0.5)+0.5)){l00-=floor(l00);for(size_t l0000=0,l00000=(size_t)(0x50*(l00));l0000<l00000;++l0000 )putchar(0x20);putchar(0x61+(int)((double)rand()/RAND_MAX*0x1a));putchar('\n');}}return 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!!
