[Tutor] data structures general query

[Alan Gauld]

On 26/06/2019 11:40, mhysnm1964 at gmail.com wrote:

> 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.

> Link lists

Link lists are very flexible and ideal for when you have a varying
amount of data and don;t want to reserve space for a maximum amount when
you only use a fraction of it. Examples are process lists in an OS.
Jobs in a queue (although technically queues are data structures in
their own right!) Think of situations where you use a list in everyday
life - a shopping list. You add items in an ad-hoc way and don't know in
advance how any items you will eventually have.

The advantages are that they have a low memory footprint, easy to move
things around (including deletion), insertion is quick if adding to the
top. Searching not so much.

> Double link-lists
Same as single linked lists except you can access both ends so a sorted
list becomes much faster to search but at the cost of making inserts and
moves etc slightly more complex(but only slightly). Real world uses?
Hmmm, for me not so many. I'll let somebody else suggest something!


> Binary trees
Good for searching. Not so good for insertions/moves.
Always a danger of the tree becoming unbalanced in which case it
tends towards becoming a linked list. Real world use - heirarchical
or ordered data arriving at random. Trees are inherently ordered so
inserting the data puts it "in order" Code tends to be more complex than
for lists though and is often recursive in nature which can be an issue
for big trees.

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

Thee are whole families of trees including multi child trees such as
yours. AVL trees (if memory serves) try to force the tree to be
balanced. Non binary trees need selector functions etc (often hash
based). Real world use - database caches, network management heirarchies
parsing structures.



-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos