Algorithms Summary Points – Part 7: Data Structures Basics

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

Data Structures Basics

ArrayList 

  • All operations are O (n) except for get(index) and addLast(object) (unless resize needed) which are O (1) 

LinkedList 

  • All operations are O (n) except for addFirst(object) and addLast(object) which are O (1) 

Stacks and Queues 

  • All operations are in O (1) time. 

Hash Tables 

  • O (1) if collisions are handled well. 
  • Rehashing 
  •  Separate chaining provides a way to handle collisions by placing in a list all key/value pairs for which the hash values associated with the key are equal: All key/value pairs belonging to the same slot are lined up in a list that lives in that slot. 
  • O(α) on average where α = m/n – where n is the number of slots available and m is the number of elements.

Binary Search Trees 

  • Sorts by building a BST with the input, then reading by in-order traversal. 
  • The average depth of a node in a randomly built BST having n nodes is O(log n). Therefore, the operations of insert, delete and search perform in O(log n) on average. 
  • The cost of using a BST to sort an array is O(nlog n) 
  • The worst case of reading from BST is O(n^2) 
  • worst-case running time of Ω(n). 

Leave a Reply

Your email address will not be published. Required fields are marked *