[Tutor] When am I ever going to use this?
Alan Gauld
alan.gauld at freenet.co.uk
Wed Aug 2 22:01:46 CEST 2006
> Lately, I have been learning about abstract data types
> (linked lists, stacks, queues, trees, etc.). While I
> do enjoy the challenge of creating these objects, I am
> not sure what they are used for.
To be honest, with the possible exception of trees, not very often!
Most of these data types are taught for historic reasons. Older
programminng
languages like assembler, C, BASIC, Fortran, Pascal typically only had
arrays(and often only single dimensioned arrays) for collecting data,
and arrays were either fixed size or had to be explicitly resized in
blocks
of storage. Thus a whole science grew up in Computing about how to
represent data more abstractly using arrays as the underpinnings.
For example a linked list could be built using 2 identical arrays.
One held the data and the other held the index of the next item,
like this:
index intList next
0 42 1
1 27 2
2 66 -1 <-- where -1 indicates end of list...
which was equivalent to a list: 42,27,66
Now we can insert a member between 42 and 27 by adding an item at
index 3
then modifying the next value for 42 to be 3 and setting the next
value at 3 to
be 1 - like this:
index intList next
0 42 3
1 27 2
2 66 -1 <-- where -1 indicates end of list...
3 99 1
All very convoluted but produced the illusion of a python like list in
a
language without lists.
But if the language has lists built in, which almost all modern
languages do,
there is no real need for most of this. You can add features like
priorities
and auto sorting etc etc, but this is almost trivial in modern
languages
whereas in old languages it was a lot of work.
And if the language suuppors a dictionary type ijn addition to lists,
and if
it can store data of moxed types, then you can implement almost any
abstract data collection easily. But the concepts of abstract data
types
are still taught to an increasingly bewildered audience...
In practice, the average Python programmer can easily simulate or
replace all of the classic data structures with built in types (with
the
possible exception of trees) or by using a relational database - the
use
of which wasn't possible in the 60's, 70's and early 80's because
they hadn't been invented yet! Now implementing an RDBMS as part
of a solution is so trivial that there's rarely need to worry about
bulding
trees etc for fast searches.
That may be a slightly controversial view but it reflects my personal
experience of programming with Python (and Ruby, Tcl, Smalltalk etc)!
Of course if you ever have to use one of the older languages then the
data structure stuff instantly applies again.
HTH,
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld
More information about the Tutor
mailing list