Data structures

[MarkusBaumeister]

I added an article on data structures so that "Linked List" article is no longer an orphan (and it seems we also had a hast_table entry although not listed in the computers workgroup).

Alas the article has few problems among them:

• I'm not an expert on data structures. Anyone doing type theory want to have a look? Preferably without making it to theoretic.
• As all books I have on this topic are in German, I have nothing to cite.
• I vaguely remember that someone once said that once all the data structures for a problem are defined, the actual programming work is easy. Would IMHO fit nicely as a quote to the article. Does anyone know, a) who said that and b) what exactly he said?

Have fun editing around in it.

[Bohdan Leonid Shmorhay]

Instead of that quote, consider using the title of Niklaus Wirth's 1976 book "Algorithms + Data Structures = Programs" (ISBN 0130224189) as a heuristic aphorism for the Data Structure article -- they work better as complementary concepts, like soup-and-sandwich or thunder-and-lightning.  (Often while troubleshooting, it helps to examine the figure-ground relationship -- if the algorithm is unwieldy, maybe using a different data structure will work.)  Of course all this assumes the existence of an Algorithm article, so I guess I just volunteered to write a stub.   

[Greg Woodhouse]

I added an article on data structures so that "Linked List" article is no longer an orphan (and it seems we also had a hast_table entry although not listed in the computers workgroup).

Alas the article has few problems among them:

• I'm not an expert on data structures. Anyone doing type theory want to have a look? Preferably without making it to theoretic.
• As all books I have on this topic are in German, I have nothing to cite.
• I vaguely remember that someone once said that once all the data structures for a problem are defined, the actual programming work is easy. Would IMHO fit nicely as a quote to the article. Does anyone know, a) who said that and b) what exactly he said?

Have fun editing around in it.

I'm a Computers editor, and I'll have a look.

Data structures are (is?) a basic topic in computer science. One of the best references I know is Thomas H. Cormen, et. al., Introduction to Algorithms, 2nd ed., MIT Press, 2001, ISBN 0-262--03293-7.

I should warn you that the idea that data structures and algorithms are the basis of good computing practice is going to sound rather dated today, given that object orientation is all the rage. However, that does not mean data structures are any less fundamental! Rather, they are the a (big) part of the foundation upon which higher level constructs (lists, sets, maps, etc.) are built. Today, programmers try to achieve what is called "loose coupling" where one part of a program does not depend unnecessarily on the structure of other parts of the program. This wasn't really so back in the 1970's when Donald Knuth (one of the pioneers of the field) was writing.

Having said all that, I should throw in a plug for functional programming. Recently, there has been a lot of interesting work on data structures in functional languages like Scheme, ML and Haskell. This is perhaps a bit more surprising than it appears because one of the cardinal rules of functional languages is that the value of a function is completely determined by its input (i.e., it is independent of any mutable state, such as what might be stored in a list or tree at a given time).

[Bohdan Leonid Shmorhay]

Structured programming (Fortran, 1950s), object-oriented programming (Smalltalk, 1970s), and functional programming (Lisp, 1950s) have all been around a long time, with algorithms and data structures central to all three of these programming paradigms.

As a recent functional programming book noted: "Using OCaml will also make you a better programmer.  This may sound like a snake-oil sales pitch, but remember that programming is about algorithms and data structures.  Learning a new programming language expands your understanding of these concepts, resulting in a better programming you."  (From "Practical OCaml" by J.B. Smith, Oct. 2006 ISBN 159059620X.) 

Nerd note:  OCaml means Objective Categorical Abstract Machine meta-Language, and is the basis for Microsoft's newly launched F# (f-sharp) functional programming language.

Good recipes (algorithms) plus well-stored ingredients (data structures) remain relevant and important concepts, whichever data crunching philosophy is being used to solve the particular problem. 

It would likely be useful to distinguish between articles in Citizendium written for a "computer science" (theoretical "specialist") audience and articles in Citizendium written for a "computer technology" (college-educated "generalist") audience. 

This would let us do justice both to Rigor and to Readability in those cases where there is a design trade-off.  Users can always successively "drill down" for more detail and ever-finer distinctions, depending on their backgrounds and needs.

-- Bo Shmorhay

[Argyriou]

Markus - by all means, if you understand the subject and both languages well enough to write in English about subjects you have German citations for, do so, and cite the German texts. Eventually, someone will come through and re-point those citations from translations to the English originals, or find better English sources, unless the best citations *are* your German books.