Summary of Elementary Data Structures -

top of Musings page

By: Nicholas Duchon.

This seems like a good place to present a summary of the elementary data structures:

• Protocols:
• stack (LIFO)
• reverse Polish notation evaluation
• walking trees and graphs
  
• queue (FIFO)
• binary search tree (BST)
• priority queue
• Structures:
• graph
• trees
• binary tree
• binary search tree
• heap tree
• linked list
• array
• circular queue
• key-value
• map
• dictionary
• hash table
• Searching
• linear
• binary
• Sorting - slow
  
• bubble
• insertion
• selection
• Sorting - fast
  
• merge
• quick
• heap
• radix

Most commons classes:

• ArrayList
  
• HashMap
  
• Collections (for sorting)
  
• Interface: Comparable
• one method:
  compareTo (T)
  
• Arrays.sort (Object []) - natural ordering, static method
  
• Interface: Comparator
  
• two required methods (lots of defaults):
  equals (Object) - actually already provided in Object class
  compare (T, T)
  
• ???? API says "can be used with lamda expressions, implement compare method", but I think this is backwards, Comparable is the lambda expression class.
  
• Arrays.sort (Object [], Comparator)
  
• ArrayList.sort (Comparator) - sort is an instance method here
  
• Collections.sort (List, Comparator) - static method