Data Structures Implementation in Java : Ultimate Notes

Share this post!

Vote this!

These notes provide an introduction to some of the most commonly occurring data structures. The language used is Java. The aim is not the greatest generality. The DataStructures package developed here is not as extensive as the Collections framework, first released with Java 1.2. For portable applications, you should use the Collections framework where possible. The DataStructures package, however, includes graphs which are not currently in the Collections framework; and the greater simplicity of the DataStructures package makes it more suitable as a basis for learning about fundamental principles of data structures and algorithms.

THIS NOTES COVERS THE FOLLOWING

• Arrays
  • Array Variables
  • Length
  • Assignment
  • Arrays as Parameters
  • Arrays of Objects
  • Array Access and Memory Allocation
• Stacks
  • Simple Implementation
  • Interfaces
  • Implementation
  • Demonstration
  • Note on Exceptions
  • Code and Demonstration
• Queues
  • Simple Implementation
  • Interface
  • Implementation
  • Demonstration
  • Code and Demonstration
• Linked Implementations
  • The Stack as a List
  • A List Node Class
  • List Implementation of Stack
  • List Implementation of Queue
  • Comparison
  • Code and Demonstration
• Enumerations and Iterators
  • Enumerations
  • Iterators
• Linked Lists
  • Instance variables and the constructor
  • Insertion
  • Deletion
  • Testing for the presence of an item
  • Reversing a list
  • Enumerating elements
  • Equality
  • The toString method
  • Code and demonstration
• Order
  • Binary search
  • Generic methods
• Binary Search Trees
  • Java implementation
  • The abstract SearchTree class
  • EmptyTree and NodeTree implementations
  • Enumerations
  • elementsLevelOrder for the NodeTree class
  • elementsInOrder for the NodeTree class
  • The toString method
  • Discussion
  • Code and demonstration
• Binary Heaps and Priority Queues
  • Complete Binary Trees
  • Array Representation
  • Priority Queues
  • Removal Algorithm
  • Implementation of Priority Queues
  • Strict Priority Queues
  • Code and Demonstration
• Heap Sort
  • Preliminaries
  • Building the heap
  • Sorting by removal
  • Code and demonstration
• Hash Tables
  • Hashing
  • Collision resolution
  • Removal
  • Choice of hash function
  • Lookup tables
  • The findIndex method
  • Separate chaining
  • Code and demonstration
• Weighted Graphs
  • Graph representations
  • Java implementation
  • Iterators
  • Other methods
  • Code
• Shortest Paths in Weighted Graphs
  • Paths and lengths
  • Dijkstra's algorithm
  • Justification
  • Java implementation
  • Shortest path methods
  • The nature of weights
  • The code
• Generics in Java 5
  • Generic types
  • Other enhancements
  • Typing an order relation
  • Generic arrays     more...