Data Structures

data structures.md

Update

This gist has been superseded by https://github.com/Integralist/Data-Structures and also https://www.integralist.co.uk/data-types-and-data-structures/

---

Note:
sequential == collection keeps order of population
ordered == collection is re-ordered (implements a Sequence interface)

Tuple

• ordered
• duplicates allowed

Set

• sequential
• no duplicates

Note: Clojure's Set data structure appears to be ordered #{3 1 2}, (first #{3 1 2}) returns 1

Linked list

• list contains nodes
• each node holds:
  • data
  • pointer to the next node
• the last node's pointer points to null
  • this is a singly linked list
  • a doubly linked list will also have a pointer to the previous node
• no direct access to individual elements
  • you must access the head and navigate until element is found

Array/Vector

• index access
• duplicates allowed
• Vectors are synchronised (i.e. thread-safe)
• Arrays allow operations across multiple threads (i.e. not thread-safe)
• Array size is determined up front
  • you cannot remove an element from an Array
    • but you can put a null pointer or no value to it
• Vector is dynamic (i.e. it can resize dynamically based on new elements added)
• Arrays can't add elements to a specific index, only to the end.
• Vectors are like super Arrays.

List/Sequence

• ordered
• duplicates allowed (but finite size)

Stack

• ordered
• LIFO (last in, first out)
• only actions available are push and pop (push directs "in", pop directs "out")

Queue

• ordered
• FIFO (first in, first out)
• only actions available are enqueue and dequeue (enqueue directs "in", dequeue directs "out")

Tree
See http://en.wikibooks.org/wiki/Data_Structures/Trees

• tree contains nodes
• each node holds:
  • data
  • pointer to the zero or more nodes
• no direct access to individual elements
  • you must access the head and navigate until element is found

Graph
See http://en.wikibooks.org/wiki/Data_Structures/Graphs

• contains:
  • nodes
  • edges
• edges contain references to 2 nodes
  • in a directed graph the references are from 1 node to another

I have some questions about Arrays and Vectors as described here, and I wondered why you did not mention Hash/Map/Dictionary data structures?

So, first of all, it feels as though your definition of Arrays and Vectors is very C/C++/Java Centric - is that fair? I mean in that paradigm it's absolutely accurate, as far as I can tell, but here's the thing...

In Clojure there is no such thing as an Array, and like all data structures, Vectors are immutable.

In PHP (not a good start I admit), there is no such thing as a Vector and Arrays are mutable (This is because Arrays in PHP are not actually Arrays, but specialised Hashes, but still...)

On to Hash(Table)/Map/Dictionaries...

• Depending on your programming environment, this structure could be named any of the above things or even an "Associative Array"
• Is a normally but not exclusively mutable length data structure that allows data to be stored using numeric, text or symbol identifiers.
• Data can (usually) be of any scalar or data structure type, i.e. Int / Float / String or Array, Nested Hash(Table)/Map/Dictionary etc.
• Data and / or Keys can be added or accessed programmatically:

  • Ruby

    my_hash = {:name => "Oli"}
    puts my_hash[:name]
    Oli
    my_hash[:surname] = "Godby"
    puts my_hash.inspect
    {:name => "Oli", :surname => "Godby"}
    puts my_hash.keys
    name
    surname

• Does not (usually) preserve order
• Can be ordered by Key(s), Data, arbitrary functions run on the Data - Highly Flexible.
• "Under the Hood" Hash(Table)/Map/Dictionary structures are quite interesting... Wondrous Learning
• Does not exist as a data structure in JavaScript, but can be 'faked' by using an Object
• Examples:
  • Ruby -> {"1" => "January", "2" => "February"}
  • Python -> { 'abc': 123, 98.6: 37 }
  • PHP -> ["foo" => "bar", "bam" => "baz", 12 => "noodle"]
  • JavaScript -> {"my" : "name", "is" : "Slim Shady", "age" : 29, "cars" : ["Ferrari Enzo", "Hummer", "Lincoln Town Car"]}
  • Clojure* -> {:name "Odin" :alternatename "Wotan" :pantheon "Norse" :son "Thor"}

*In Clojure, Maps are immutable like all other data structures and values.

@maleghast no reason for not mentioning the hash(table)/map/dictionary data structure, I started the gist more for covering data structures that I wasn't necessarily familiar with (e.g. Linked Lists) and although I've used Arrays my entire career I was always confused by what the hierarchy was of its other variants.

For example, I assumed that Linked Lists were the fundamental iterator and because of its implementation (i.e. size not needed to be specified up front, almost lazy sequence in style like Clojure) that it would be much more performant than a standard Array. I then assumed that Vectors were the next level up from Linked Lists as they allow indexed access, but I knew nothing more about Vectors other than they were supposed to be like Arrays (I realise they're a more mathematical term for Arrays and so I assumed there must be an implementation detail other than index access that makes them an extension from Linked Lists but not quite a feature capable as an Array). Finally, I believed Array to be the highest level data structure out of the three and hence why that was implemented in JS rather than the lower level Vector or Linked List structures.

It wasn't until I started learning Clojure and realised that they don't provide Arrays but Vectors and yet the functionality of both Vectors and Arrays (from Clojure's perspective) seemed almost identical (with the exception of immutability). Please do correct me though if I'm mistaken about that.

Then when I started reading up on Arrays vs Vectors it almost seemed like the opposite. That Arrays were an enhancement from the base level Linked List concept and then Vectors were an enhanced version of Arrays. But I wasn't sure who to believe on that topic. That's ideally of great interest to me.

I appreciate that Computer Science data structures are typically built around the C/C++/Java environments and so things like Linked Lists aren't really exposed in languages such as Ruby/PHP or JavaScript (although maybe Enumerators and Iterators could be seen as enhanced Linked Lists?)

Any way, I'd appreciate your feedback on my above comments. Thanks for taking the time so far to write out your detailed explanation for hashes. I enjoyed reading through it :-)