Data Structure in Java

Types of Data Structures:

1. A data structure is way of collecting and organizing data
2. Choosing the right data structure impacts efficiency
3. Data comes from many sources e.g. Database, Files etc.
4. Many data structures are implemented using as Linked list (Stack, queue etc.)

Array List: Stores objects and can grow or shrink

Linked List: Uses pointers to keep track of elements

Vector: Can grow or shrink, It provides synchronization

Stack: Operates on Last In , First Out (LIFO)

Queue: Operates on First In, First Out (FIFO)

Array List and Vectors:

Advantages:

• Provide fast access using indexing 
• Memory Coherence
• Provide an initial size (optional)
• User internal array for storage, which makes random access fast

Disadvantages:

• Can be time consuming to add elements in the middle
• Waste space if array is not full
• Need to be resized when they reach capacity
• Slower when deleting elements from the middle

Linked List:

Advantages:

• Insertion and deletion operations are easily implemented
• Elements are efficiently added or deleted from the middle of the list

Disadvantages:

• Elements in a linked list must be read sequentially
• Elements are not stores sequentially in memory
• Random access to element can be inefficient
• slower iteration and extra memory overhead are required

Collection Frameworks:

• It provides implementation of data structures
• There is a Collections class that has static methods
• The static methods can be used to Sort, Search, Copy and Fill
• Each methods throws a NullPointerException, if objects are null

Collection Interface:

• it defines common operation for data structure
• List stores an ordered collection of elements
• A set stores a group of non-duplicate elements
• Queues stores objects that are processed in a FIFO order
• Collection are sometimes referred to as containers.
• They are used to store, retrieve, manipulate and aggregate
• Some containers store a collections of elements
• Other containers stores Key/Value pairs, called as MAP
• The interface provides basic operations for add and remove
• it also provides important query operations
• A commonly used method is toArray() , which return an array
• To convert from array to a list, use Arrays.toList()

Iterable Interface:

• Each collection has an Iterator object to traverse the elements
• It provides a tools for walking through a data structure
• It hides the details of how data is stored
• The Collection interface extends the Iterable interface
• Methods in Iterable interface are iterator() , foreach()
• The iterator() method return an iterator object
• The Iterator includes hasNext(), next(), remove
• The Iterable interface is used to traverse the elements
• In addition to yhr Iterable interface, there is ListIterator
• The ListIterator is use for list data structure
• This adds functionality to traverse the list backward
• Method include previous(), hasPrevious(), previoudIndex()

ArrayList:

• Implements the List interface
• Is the most frequently used data structure
• create an object array that grow as needed
• can contain duplicate elements
• It hold null value
• Its not thread safe
• Quick access is provided to elements based on its position
• Developer can add or remove elements by index value
• Easily find the index of the first occurrence of an elements
• The initial size capacity can be set when created
• The trimTo() method can used to reduce the size

LinkedList:

• Prior to Java-7, linked list were created manually
• Now, There is LinkedList class included in the API
• Access to the elements is linear
• It uses a doubly linked list to manage the collection of object

Vectors:

• Includes with First release of Java 1.0
• Similar to the behavior of Array List
• Automatically provides synchronization, which cause its performance to suffer

Stack:

• Its used as Last In, Firs Out order (LIFO)
• its a vertical stack of objects
• The last elements added is the first to come off
• Items are added and deleted from the same end
• To add an item, you use the push() method
• To remove an item, you pop()
• The peek() method makes a copy of the first item
• A stack is an easy way to reverse a collection of value

Queue:

• A linear list is where items are added to one end & deleted from the other end
• Example include waiting a line in stadium line
• People join the queue at the end and exit from other end
• Another example is Print Queue Job
• add() - Used to add elements to the end
• peek() - returns a copy of the first element
• remove() - removes the top element; error if empty
• poll() - removes from the top; returns null if the queue is empty