Saturday, March 4, 2017

Data structures

Hi folks!  (I aten't dead)
I was thinking recently that I haven't made nearly enough things to do with computer science, the same way I did for maths, and it's time to fix that!
So this project is to knit a family of data structures.  The idea will be to take a bunch of plastic toy balls to represent data items, and knit wrapper cups, connected together in different ways, to represent the data structure itself.
I've got ideas for a few of these:

  • Linked list - each node has a link to the next node.
  • Doubly linked list - each node has forward and backward links.
  • Binary tree - each node has two children.  I'd like this to be unbalanced, so some of the branches will be longer than others.
  • Red-black tree - another binary tree, but with coloured nodes (and this one will be balanced).
  • Hash table - a single parent has a bunch of child nodes, each with a coloured rim to represent the hash value of the objects to place in it.  Some of the child nodes will also form (small) linked lists, of the same colour.
  • Array - a string of references, only some of which have a node attached.  (It might be more accurate if he nodes are all there, but only some of them are filled, but I think this would make it harder to distinguish from the linked list.
I'm planning to write up a pattern for this one - it should be pretty simple since the only components are the cups and the references.  But I'd love to see people knitting some other structures too, and maybe they'll be useful as teaching aids at some point?  The one drawback is this means I need to knit a *lot* of identical cups, I think the whole project will need about 40 of them.

Happy knitting,
Hugh.

No comments: