[Tutor] data structures general query

[Mats Wichmann]

On 6/26/19 4:40 AM, mhysnm1964 at gmail.com wrote:
> All,
> 
>  
> 
> General computer science question for data structures.
> 
> When would you use the below structures and why? If you can provide a real
> life example on when they would be used in a program  This would be great. I
> am not after code, just explanation.
> 
>  
> 
> Link lists
> 
> Double link-lists

This becomes a question of what kind of data you have and what you need
to do with it.

Python has "lists", which are what most people think of as arrays - you
reference them by index. Lists have fast access: if you know you want
the 7th element, you just ask for that.  Then if you want to insert a
new element following that, the whole array past that point has to move
to make room - the grunt work is normally abstracted away by languages
that have array datatypes, but it is still happening, same for deleting,
so lots of random inserts/deletes (except at the end) are "expensive".
In linked lists, insert is cheap. You just take the existing element's
"next" field and stick that into the new element's "next" field, and
then stick the new element into the existing element's "next" field.
However, deleting an still isn't cheap: unless your traversal mechansm
saves it on the way to finding a certain element, you have to start from
the beginning and walk through to find the previous element, because
it's this one which has to have its "next" field changed.  A doubly
linked list however makes removal trivial - you already have a reference
to that element via the "previous" field.  For both kinds of linked
lists, searching is expensive as you have to walk the chain.  The
fastest data structure for searching is when the lookup is hashed - this
is what the Python dict type allows for, as the keys are hashed as
they're stored (leading to the sometimes surprising rule for Python
dicts that "key must be hashable"). Other popular data structures are
queues and stacks.  Note there are also circular lists, which only means
the tail hooks back into the head.

So your choices depend on what the usage pattern of your data is. The
fact that Python doesn't have link lists, neither natively or in the
standard library, suggests the designers didn't think they represented a
common enough usage pattern for users of the language.


> Binary trees
> 
> What other trees are their other than hierarchical tree (file systems)

Can let this go without mentioning the Merkle tree, darling of anyone
who's ever dabbled in blockchain :)

> Link lists I would guess be useful in an index for a database? 

I believe the "classic" use case is memory management - keeping track of
chunks of memory.

> Binary trees useful for searches?

it's useful for searches if the "is A less than B" comparison is a
useful property of the data you are representing. If not, it isn't
useful at all as you have no way to construct the tree :)