There are two basic data structures and four linear abstract data types we've discussed so far:

Data structures:

• List
  • See, e.g.,

    • Wikipedia on linked lists

    • John Morris's notes on Lists

  • Scheme lists are a special case we've studied extensively

    • SICP section 2.2

    • Dybvig also http://www.scheme.com/tspl2d/objects.html#g2027

  • This type is sometimes called a linked list

  • We didn't look at a doubly linked list, but you might find it interesting

• Array
  • See, e.g.,

    • Wikipedia on arrays

    • John Morris's notes on arrays

Abstract data types:

• Wikipedia on ADTs

• Collection

  • Wikipedia calls this a List ADT

  • John Morris's notes on ADT/Collection

• Stack

  • Wikipedia on Stacks

  • John Morris's notes on Stacks

• (FIFO) Queue

  • Wikipedia on Queues NB the scheme code there is very cool, but quite non-intuitive.

• Tree

  • Wikipedia on binary trees (not the only kind, but Wikipedia on trees isn't what you want....