Pages

Thursday, May 24, 2012

Java - Data Structures

Data Structure       Advantages                Disadvantages



Array
Quick insertion
(very fast access if index known.)
Slow search, 
Slow deletion, 
fixed size.
Ordered Array
Quicker search
Slow insertion,
Slow deletion,
fixed size. 
Stack
Provides last-in, first-out access
Slow access to other items
Queue
Provides first-in, first-out access
Slow access to other items
Linked list
Quick insertion, quick deletion
Slow search
       ArrayList           
(is same as a Vector. Vectors are
synchronized, can be thread safe, but
slower)
Binary Search, Sort
Slow insertion, deletion
Binary tree
Quick insertion, deletion (if tree remains balanced), and search.
Deletion algorithm is complex
Red-black tree
Quick insertion, deletion (this tree is always balanced), and search.
Complex
2-3-4 tree
Quick insertion, deletion (this tree is always balanced, is good for disk storage progr.), and search.
Complex
Hash table (~arrays)
Very fast access if key known. Fast insertion
Slow deletion, access slow if key not known, inefficient memory usage.
Heap (~LinkedList)
Fast insertion, deletion, access to largest item.
Slow access to other items
Graph
Models real-world situations.
Slow and complex.
                       

No comments:

Post a Comment