bluesky129 / data-structure

another java collection library

java collection implementations for the data structures talked about in the book DATA STRUCTURES AND ALGORITHM ANALYSIS IN JAVA, THIRD EDITION

Yep, this can be seen as another collection library like java collection framework, but it provides other data structure implementations like Splay Tree, AVL Tree, Red-black Tree etc. it includes:

• List:

  LinkedList
  ArrayList
  Stack
  Queue

• Tree:

  Basic Tree
  Binary Search Tree
  AVL tree
  Splay Tree
  Red-black tree
  TreeMap
  TreeSet
  HashMap based on Red-black Tree
  BTree
  SkipList
  Treap
  Tries

• Heap:

  Basic Min-Heap
  Leftist Heap
  Skew Heap
  Binomial Heap
  DoubleEndedHeap

• Hash:

  Basic Hash Table by seperate chain
  Hash Table by linear probing, quadratic probing
  Perfect Hash Table
  Cuckoo Hash Table
  Hopscotch Hash Table
  Extensible Hash Table

• BitMap:

  BitMap

• External memory data structure(they can hold long key and long value):

  HashTable
  BPlusTree

Features

Most of class provides few but really necessary functions, the benefit about this is that it can make code clean, more readable and more extensible. I also make data structures separate, For example, hashmap could be built on red-black tree array and this is what java hashmap does, but it turns out java hash map implementation is very very complicated, if you go into java hash map source code since jdk 1.8, then you can get 2390 line codes, and my hash map implementation only has 160 line. This is another reason I built this.

Documentations

For a detailed api documentation, please go to api docs.

Examples

• List

• Tree

• Heap

• Hash

• BitMap

• External