# 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)

• 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).