[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 
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 
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 
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 
and auto sorting etc etc, but this is almost trivial in modern 
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 
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 
possible exception of trees) or by using a relational database - the 
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 
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.


Alan Gauld
Author of the Learn to Program web site

More information about the Tutor mailing list