- Data Structure Runtime Cheat Sheet
- Java Data Structures And Algorithms Cheat Sheet
- Java Data Structures Complexity Cheat Sheet
- Java Data Structures Cheat Sheet
- Java Data Structures Cheat Sheet
Common Data Structure Operations
| Data Structure | Time Complexity | Space Complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(n) | O(n) | O(n) | O(n) |
| B-Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | N/A | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | N/A | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| KD Tree | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | Θ(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
Array Sorting Algorithms
Algorithms and Data Structures Cheatsheet We summarize the performance characteristics of classic algorithms and data structures for sorting, priority queues, symbol tables, and graph processing. The end of the textbook, you will find 2 practice midterm 1’s (on java), 2 practice midterm 2’s (on data structures), and 2 practice finals. These summarize the contents of the book and will be challenging, probably more challenging than the course you are currently taking. These exams are meant to be difficult, especially in the time.
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
- Java Tutorial
- Java Object Oriented
- Java Advanced
- Java Useful Resources
- Selected Reading
The data structures provided by the Java utility package are very powerful and perform a wide range of functions. These data structures consist of the following interface and classes −
- Enumeration
- BitSet
- Vector
- Stack
- Dictionary
- Hashtable
- Properties
All these classes are now legacy and Java-2 has introduced a new framework called Collections Framework, which is discussed in the next chapter. −
The Enumeration
The Enumeration interface isn't itself a data structure, but it is very important within the context of other data structures. The Enumeration interface defines a means to retrieve successive elements from a data structure.
For example, Enumeration defines a method called nextElement that is used to get the next element in a data structure that contains multiple elements.
To have more detail about this interface, check The Enumeration.
The BitSet
The BitSet class implements a group of bits or flags that can be set and cleared individually.
This class is very useful in cases where you need to keep up with a set of Boolean values; you just assign a bit to each value and set or clear it as appropriate.
For more details about this class, check The BitSet.
The Vector
Data Structure Runtime Cheat Sheet
The Vector class is similar to a traditional Java array, except that it can grow as necessary to accommodate new elements.
Like an array, elements of a Vector object can be accessed via an index into the vector.
The nice thing about using the Vector class is that you don't have to worry about setting it to a specific size upon creation; it shrinks and grows automatically when necessary. Croc 2 download full game pc.
For more details about this class, check The Vector.
The Stack
The Stack class implements a last-in-first-out (LIFO) stack of elements.
You can think of a stack literally as a vertical stack of objects; when you add a new element, it gets stacked on top of the others.
When you pull an element off the stack, it comes off the top. In other words, the last element you added to the stack is the first one to come back off.
For more details about this class, check The Stack.
Java Data Structures And Algorithms Cheat Sheet
The Dictionary
The Dictionary class is an abstract class that defines a data structure for mapping keys to values.
This is useful in cases where you want to be able to access data via a particular key rather than an integer index.
Since the Dictionary class is abstract, it provides only the framework for a key-mapped data structure rather than a specific implementation.
For more details about this class, check The Dictionary.
The Hashtable
The Hashtable class provides a means of organizing data based on some user-defined key structure.
For example, in an address list hash table you could store and sort data based on a key such as ZIP code rather than on a person's name.
Java Data Structures Complexity Cheat Sheet
The specific meaning of keys with regard to hash tables is totally dependent on the usage of the hash table and the data it contains.
For more detail about this class, check The Hashtable.
The Properties
Java Data Structures Cheat Sheet
Properties is a subclass of Hashtable. It is used to maintain lists of values in which the key is a String and the value is also a String.
Java Data Structures Cheat Sheet
The Properties class is used by many other Java classes. For example, it is the type of object returned by System.getProperties( ) when obtaining environmental values.
For more detail about this class, check The Properties.