What are some unique benefits of Trees, Linked Lists, Stacks and Hashtables?

[khlee]

and what are some practical applications that each data structure is best for?

 

[mundane]

Just digging back into memory a few years since we learned (and had to use this information) ....

Sorted Binary trees give the best performance for searching, I think. Linked Lists give good performance for serialized type information that would require addition/deletion, etc. We used stacks when we needed to parse mathematical functions ( ex 3 * ( 8+5-2)^ 3 ), where we could apply it to the stack in the corret order of operations, the data structure is good for activities like that (and others). Hashes were recommended to give the best overall performance, and now I usually use them for all my major datastructures.

I'm sure there are other members who can give more indepth answers/insight .... anyone? (Sounds like a hw problem =) )

 

[joeSmack]

Ha. It does sound like a HW problem. With Tree's, Linked Lists, and Hashtables there are several variations of them each has their own use. Anyhow, here some general ideas. I'll also add a data structure, an array:

Some general concepts:
- locality: the way a computer works, things are much faster if they are close to each other in memory. The more you jump around in memory the worse the performance.
- things to consider: element access, insertion/deletion, search, scalability/load balancing. Your choice of data structure should be based on which of the three things are most important and will have the greatest effect on performance.

- array: arrays are typically fixed size and implemented as contiguous blocks of memory. If you know the fixed size of the data coming in, and don't do insertions or deletions in the middle of the array, and know the index of the element you want arrays can't be beat. Arrarys are bad with everything except element access.

- linked list: linked lists are usually implemented with pointers. linked lists are great for a lot of insertions and deletions. Inserting in the middle is not so bad. A linked list is great for making sorted lists. Element access is slow since it has to loop thru the list.

- tree: Trees are the best at load balancing. Element access is faster than linked lists. The only draw back is that insertions and deletions might be slow, since the tree might have to rebalance itself.

- hashtable: data goes in with a pair (key, value). hashtables are usually great everything but it can be awful at everything depending on your hash algorithm.

- stack: a stack is a data structure where stuff that goes in first, comes out last. ie. a stack of dishes in your sink.

The above data structures also have different ways of accessing data.

Example uses:
- array: a matrix
- linked list: alphabetical sorted ordered list
- tree: b+ trees are used in databases
- hashtable: something like a DNS lookup where a string maps to an ip address
- stack: to remember function calls in programming languages. in C if you call a function, which calls a function, etc. these function calls are put on a stack. the function called last finishes first and gets popped off the stack. this continues until the originating function eventually gets popped off the stack and the program ends.

Hope this helps.

 

[DaveSimmons]

I hate to tell you this, but if you want to be any good at software development you'll need to really learn this material and understand it well enough to write your own descriptions instead of memorizing someone else's.

You're also more likely to bomb the real tests if you try to get by with memorizing, unless you're just trying to pass instead of get a good grade.

 

[joeSmack]

Originally posted by: DaveSimmons
I hate to tell you this, but if you want to be any good at software development you'll need to really learn this material and understand it well enough to write your own descriptions instead of memorizing someone else's.

You're also more likely to bomb the real tests if you try to get by with memorizing, unless you're just trying to pass instead of get a good grade.

I know a ton of people who got good grades off pure memorization. That said those people are the worst programmers, people who think that they're good programmers because they know how to do the class projects, but that lack creativity and depth.

 

[khlee]

Originally posted by: DaveSimmons
I hate to tell you this, but if you want to be any good at software development you'll need to really learn this material and understand it well enough to write your own descriptions instead of memorizing someone else's.

You're also more likely to bomb the real tests if you try to get by with memorizing, unless you're just trying to pass instead of get a good grade.

i agree with you, but I analyzed this question myself and formed my own conclusions. I asked because I wanted to make sure that I didnt miss any points.

btw: its not a hw problem.

 

[khlee]

Originally posted by: joeSmack
Ha. It does sound like a HW problem. With Tree's, Linked Lists, and Hashtables there are several variations of them each has their own use. Anyhow, here some general ideas. I'll also add a data structure, an array:

Some general concepts:
- locality: the way a computer works, things are much faster if they are close to each other in memory. The more you jump around in memory the worse the performance.
- things to consider: element access, insertion/deletion, search, scalability/load balancing. Your choice of data structure should be based on which of the three things are most important and will have the greatest effect on performance.

- array: arrays are typically fixed size and implemented as contiguous blocks of memory. If you know the fixed size of the data coming in, and don't do insertions or deletions in the middle of the array, and know the index of the element you want arrays can't be beat. Arrarys are bad with everything except element access.

- linked list: linked lists are usually implemented with pointers. linked lists are great for a lot of insertions and deletions. Inserting in the middle is not so bad. A linked list is great for making sorted lists. Element access is slow since it has to loop thru the list.

- tree: Trees are the best at load balancing. Element access is faster than linked lists. The only draw back is that insertions and deletions might be slow, since the tree might have to rebalance itself.

- hashtable: data goes in with a pair (key, value). hashtables are usually great everything but it can be awful at everything depending on your hash algorithm.

- stack: a stack is a data structure where stuff that goes in first, comes out last. ie. a stack of dishes in your sink.

The above data structures also have different ways of accessing data.

Example uses:
- array: a matrix
- linked list: alphabetical sorted ordered list
- tree: b+ trees are used in databases
- hashtable: something like a DNS lookup where a string maps to an ip address
- stack: to remember function calls in programming languages. in C if you call a function, which calls a function, etc. these function calls are put on a stack. the function called last finishes first and gets popped off the stack. this continues until the originating function eventually gets popped off the stack and the program ends.

Hope this helps.

whao, thanks!! 🙂

 

[khlee]

you forgot one:

hashtables are bad if the number of containers is determined during run time and also if it changes.
also its inefficient when table becomes full

 

[khlee]

linked list: alphabetical sorted ordered list

wouldnt a binary tree be better for alphabetically sorted lists? things are always in alphabetical order left to right, and it is sorted as elements are inserted. it would also be more efficient b/c for every iteration the range is restricted to up to half

 

[khlee]

also, can you elaborate on the scalability/ load balancing facet of data structures and how trees are used for databases.