Collections Framework

Collections in Java

Collections in java is a framework that provides an architecture to store and manipulate the group of objects.

All the operations that you perform on a data such as searching, sorting, insertion, manipulation, deletion etc. can be performed by Java Collections.

Java Collection simply means a single unit of objects. Java Collection framework provides many interfaces (Set, List, Queue, Deque etc.) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet etc).


What is Collection in java

Collection represents a single unit of objects i.e. a group.


What is framework in java

•  provides readymade architecture.
•  represents set of classes and interface.
•  is optional.

What is Collection framework

Collection framework represents a unified architecture for storing and manipulating group of objects. It has:

•     Interfaces and its implementations i.e. classes
•     Algorithm

Hierarchy of Collection Framework 

Let us see the hierarchy of collection framework.The java.util package contains all the classes and interfaces for Collection framework.

Methods of Collection interface

No.	Method	Description
1	public boolean add(Object element)	is used to insert an element in this collection.
2	public boolean addAll(Collection c)	is used to insert the specified collection elements in the invoking collection.
3	public boolean remove(Object element)	is used to delete an element from this collection.
4	public boolean removeAll(Collection c)	is used to delete all the elements of specified collection from the invoking collection.
5	public boolean retainAll(Collection c)	is used to delete all the elements of invoking collection except the specified collection.
6	public int size()	return the total number of elements in the collection.
7	public void clear()	removes the total no of element from the collection.
8	public boolean contains(Object element)	is used to search an element.
9	public boolean containsAll(Collection c)	is used to search the specified collection in this collection.
10	public Iterator iterator()	returns an iterator.
11	public Object[] toArray()	converts collection into array.
12	public boolean isEmpty()	checks if collection is empty.
13	public boolean equals(Object element)	matches two collection.
14	public int hashCode()	returns the hashcode number for collection.

Iterator interface

Iterator interface provides the facility of iterating the elements in forward direction only.

There are only three methods in the Iterator interface. They are:

• public boolean hasNext() it returns true if iterator has more elements.
• public object next() it returns the element and moves the cursor pointer to the next element.
• public void remove() it removes the last elements returned by the iterator. It is rarely used.

Java ArrayList class

• Java ArrayList class uses a dynamic array for storing the elements.It extends AbstractList class and implements List interface.
• Java ArrayList class can contain duplicate elements.
• Java ArrayList class maintains insertion order.
• Java ArrayList class is non synchronized.
• Java ArrayList allows random access because array works at the index basis.
• In Java ArrayList class, manipulation is slow because a lot of shifting needs to be occurred if any element is removed from the array list.

Data Structures

Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elements in terms of some relationship, for better organization and storage.

In simple language, Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily.

Basic types of Data Structures

As we discussed above, anything that can store data can be called as a data strucure, hence Integer, Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures.

Then we also have some complex Data Structures, which are used to store large and connected data. Some example of Abstract Data Structure are :

• Linked List
• Tree
• Graph
• Stack, Queue etc.

All these data structures allow us to perform different operations on data. We select these data structures based on which type of operation is required.

What is Algorithm ?

An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain predefined task. Algorithm is not the complete code or program, it is just the core logic(solution) of a problem, which can be expressed either as an informal high level description as pseudocode or using a flowchart.

An algorithm is said to be efficient and fast, if it takes less time to execute and consumes less memory space. The performance of an algorithm is measured on the basis of following properties :

•  Time Complexity - Time Complexity is a way to represent the amount of time needed by the program to run to completion. We will study this in details in our section.
•  Space Complexity - Its the amount of memory space required by the algorithm, during the course of its execution. Space complexity must be taken seriously for multi-user systems and in situations where limited memory is available.

Time Complexity of Algorithms

Time complexity of an algorithm signifies the total time required by the program to run to completion. The time complexity of algorithms is most commonly expressed using the big O notation.

Now the most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N, as N approaches infinity. In general you can think of it like this :

 statement;

Above we have a single statement. Its Time Complexity will be Constant. The running time of the statement will not change in relation to N.

for(i=0; i < N; i++)
{
  statement;
}

The time complexity for the above algorithm will be Linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

for(i=0; i < N; i++)
{
  for(j=0; j < N;j++)
  {
    statement;
  }
}

This time, the time complexity for the above code will be Quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

Types of Sorting Techniques

•   Bubble Sort
•   Insertion Sort
•   Selection Sort
•   Quick Sort
•   Merge Sort
•   Heap Sort

 

Stacks

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

 

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.

Class Stack
{
  int top;
  public:
  int a[10];    //Maximum size of Stack
  Stack()
  {
    top = -1;
  }
};

void Stack::push(int x)
{
  if( top >= 10)
  {
    cout << "Stack Overflow";
  }
  else
  {
    a[++top] = x;
    cout << "Element Inserted";
  }
}

int Stack::pop()
{
  if(top < 0)
  {
    cout << "Stack Underflow";
    return 0;
  }
  else
  {
    int d = a[top--];
    return d;
  }
}

void Stack::isEmpty()
{
  if(top < 0)
  {
    cout << "Stack is empty";
  }
  else

Queue

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.

Linked Lists

Linked List is a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.


Advantages of Linked Lists:

•     They are a dynamic in nature which allocates the memory when required.
•     Insertion and deletion operations can be easily implemented.
•     Stacks and queues can be easily executed.
•     Linked List reduces the access time.

Singly Linked List : Singly linked lists contain nodes which have a data part as well as an address part i.e. next, which points to the next node in sequence of nodes. The operations we can perform on singly linked lists are insertion, deletion and traversals




Doubly Linked List : In a doubly linked list, each node contains two links the first link points to the previous node and the next link points to the next node in the sequence.



Circular Linked List : In the circular linked list the last node of the list contains the address of the first node and forms a circular chain.

Database Normalization

There are three common forms of normalization: 1st, 2nd, and 3rd normal form.  There are several additional forms, such as BCNF, but I consider those advanced, and not too necessary to learn in the beginning.


1NF – First Normal Form

• Should be contained only atomic values
• There should not be repeating groups

How do we bring an unnormalized table into first normal form? Consider the following example:


This table is not in first normal form because the [Color] column can contain multiple values. For example, the first row includes values "red" and "green."

To bring this table to first normal form, we split the table into two tables and now we have the resulting tables:



Now first normal form is satisfied, as the columns on each table all hold just one value.


2NF - Second Normal Form

A database is in second normal form if it satisfies the following conditions:

•     It is in first normal form
•     All non-key attributes are fully functional dependent on the primary key

Consider the following example:



This table has a composite primary key [Customer ID, Store ID]. The non-key attribute is [Purchase Location]. In this case, [Purchase Location] only depends on [Store ID], which is only part of the primary key. Therefore, this table does not satisfy second normal form.

To bring this table to second normal form, we break the table into two tables, and now we have the following tables:




3NF - Third Normal Form

A table is in third normal form if:

•     It is in second normal form.
•     There is no transitive functional dependency. (A transitive dependency is a functional dependency in which X → Z (X determines Z) indirectly, by virtue of X → Y and Y → Z (where it is not the case that Y → X))

Consider the following example:




In the table, [Book ID] determines [Genre ID], and [Genre ID] determines [Genre Type]. Therefore, [Book ID] determines [Genre Type] via [Genre ID] and we have transitive functional dependency, and this structure does not satisfy third normal form.

To bring this table to third normal form, we split the table into two as follows:

JUnit and Wrapper class in Java

Features of JUnit

• JUnit is an open source framework, which is used for writing and running tests.
• Provides annotations to identify test methods.
• Provides assertions for testing expected results.
• Provides test runners for running tests.
• JUnit tests allow you to write codes faster, which increases quality.
• JUnit is elegantly simple. It is less complex and takes less time.
• JUnit tests can be run automatically and they check their own results and provide immediate feedback. There's no need to manually comb through a report of test results.
• JUnit tests can be organized into test suites containing test cases and even other test suites.
• JUnit shows test progress in a bar that is green if the test is running smoothly, and it turns red when a test fails.

Features of JUnit Test Framework

• Fixtures-Fixtures is a fixed state of a set of objects used as a baseline for running tests
• Test suites-A test suite bundles a few unit test cases and runs them together.
• Test runners-Test runner is used for executing the test cases.
• JUnit classes
• Assert − Contains a set of assert methods.
• TestCase − Contains a test case that defines the fixture to run multiple tests.
• TestResult − Contains methods to collect the results of executing a test case.

 

Assert Class

Following is the declaration for org.junit.Assert class −

public class Assert extends java.lang.Object

This class provides a set of assertion methods useful for writing tests. Only failed assertions are recorded. Some of the important methods of Assert class are as follows −

Methods & Description   

• void assertEquals(boolean expected, boolean actual)-Checks that two primitives/objects are equal.   
• void assertFalse(boolean condition)-Checks that a condition is false   
• void assertNotNull(Object object)-Checks that an object isn't null.  
• void assertNull(Object object)-Checks that an object is null   
• void assertTrue(boolean condition)-Checks that a condition is true.   
• void fail()-Fails a test with no message.

 

Annotation

Annotations are like meta-tags that you can add to your code, and apply them to methods or in class. These annotations in JUnit provide the following information about test methods (mainly it can be used to set execution procedures)−

1. @Test-The Test annotation tells JUnit that the public void method to which it is attached can be run as a test case.
2. @Before-Several tests need similar objects created before they can run. Annotating a public void method with @Before causes that method to be run before each Test method.
3. @After-If you allocate external resources in a Before method, you need to release them after the test runs. Annotating a public void method with @After causes that method to be run after the Test method.
4. @BeforeClass-Annotating a public static void method with @BeforeClass causes it to be run once before any of the test methods in the class.
5. @AfterClass-This will perform the method after all tests have finished. This can be used to perform clean-up activities.
6. @Ignore-The Ignore annotation is used to ignore the test and that test will not be executed.

Ignore Test

A test method annotated with @Ignore will not be executed. 

If a test class is annotated with @Ignore, then none of its test methods will be executed. 

 @Test(timeout = 1000)
   public void testPrintMessage() {  
      System.out.println("Inside testPrintMessage()");   
      messageUtil.printMessage();   
   }

 

Exceptions Test 

JUnit provides an option of tracing the exception handling of code. You can test whether the code throws a desired exception or not.

@Test(expected = ArithmeticException.class)
   public void testPrintMessage() {   
      System.out.println("Inside testPrintMessage()");    
      messageUtil.printMessage();    
   }

Time Test 

JUnit provides a handy option of Timeout. If a test case takes more time than the specified number of milliseconds, then JUnit will automatically mark it as failed. 

Parameterized Test

JUnit 4 has introduced a new feature called parameterized tests. Parameterized tests allow a developer to run the same test over and over again using different values. There are five steps that you need to follow to create a parameterized test.

Wrapper class in Java

• Wrapper class in java provides the mechanism to convert primitive into object and object into primitive.
• Since J2SE 5.0, autoboxing and unboxing feature converts primitive into object and object into primitive automatically. The automatic conversion of primitive into object is known and autoboxing and vice-versa unboxing.
• One of the eight classes of java.lang package are known as wrapper class in java. The list of eight wrapper classes are given below:

Primitive Type     Wrapper class

boolean              Boolean

char                   Character

byte                   Byte

short                  Short

int                     Integer

long                  Long

float                  Float

double              Double

• public class WrapperExample1{  
• public static void main(String args[]){  
• //Converting int into Integer  
• int a=20;  
• Integer i=Integer.valueOf(a);//converting int into Integer  
• Integer j=a;//autoboxing, now compiler will write Integer.valueOf(a) internally  
•   
• System.out.println(a+" "+i+" "+j);  
• }}  

• public class WrapperExample2{    
• public static void main(String args[]){    
• //Converting Integer to int    
• Integer a=new Integer(3);    
• int i=a.intValue();//converting Integer to int  
• int j=a;//unboxing, now compiler will write a.intValue() internally    
•     
• System.out.println(a+" "+i+" "+j);    
• }}    

Test Driven Development (TDD)

• Test-driven development (TDD) is a software development process that relies on the repetition of a very short development cycle: first the developer writes an (initially failing) automated test case that defines a desired improvement or new function, then produces the minimum amount of code to pass that test, and finally refactors the new code to acceptable standards.
• sequence of steps
• Add a test 
• Run all tests and see if the new one fails
• Write some code
• Run tests
• Refactor code
• Repeat
• TDD Best practices
• Naming Conventions
• Processes
• Development practices
• Tools 

1. Naming conventions 
• Naming conventions help organize tests better so that it is easier for developers to find what they’re looking for
• Most important is that everyone on the team knows what conventions are used and is comfortable with them. Choosing “more popular” conventions has the advantage that newcomers to the team can get up to speed fast since they can leverage existing knowledge to find their way around. 
2. Separate the implementation from the test code
• Common practice is to have at least two source directories. Implementation code should be located in src/main/java and test code in src/test/java. In bigger projects number of source directories can increase but the separation between implementation and tests should remain.
3. Place test classes in the same package as implementation 
• Knowing that tests are in the same package as the code they test helps finding them faster
4. Name test classes in a similar fashion as classes they test 
• One commonly used practice is to name tests the same as implementation classes with suffix Test. If, for example, implementation class is StringCalculator, test class should be StringCalculatorTest.
5. Use descriptive names for test methods
• Using method names that describe tests is beneficial when trying to figure out why some test failed or when the coverage should be increased with more tests. It should be clear what conditions are set before the test, what actions are performed and what is the expected outcome.
• public final void whenSemicolonDelimiterIsSpecifiedThenItIsUsedToSeparateNumbers()  
6. Write the simplest code to pass the test
• The idea is that the simpler the implementation the better and easier to maintain is the product. 
7. Write assertions first, act later
• Once assertion is written, purpose of the test is clear and developer can concentrate on the code that will accomplish that assertion and, later on, on the actual implementation.
8. Minimize assertions in each test
• If multiple assertions are used within one test method, it might be hard to tell which of them caused a test failure 
9. Use mocks
• Mocks are prerequisites for fast execution of tests and ability to concentrate on a single unit of functionality. By mocking dependencies external to the method that is being tested developer is able to focus on the task at hand without spending time to set them up 

• Pros 
• It can lead to simple, elegant, modular code.
• It can help developers find defects and bugs earlier than they otherwise would and it’s a commonly held belief that a bug is cheaper to fix the earlier you find it.
• The tests can serve as a kind of live documentation and make the code much easier to understand.
• It can speed up development in the long term.
• It can encourage developers to think from an end user point of view.
• Cons
• It necessitates a lot of time and effort up front which can make development feel slow to begin with.
• It’s difficult to write good tests that cover the essentials and avoid the superfluous.
• If the design is changing rapidly then you’ll need to keep changing your tests

Git

• First go to the relevant folder and initialize a Git repository , type the following command:     git init
• To see what the current state of our project is: git status
•  To add files to the staging area : git add .
• Let's run git status again to see where we stand 
• To store our staged changes we run the commit command with a message describing what we've changed : git commit -m "Message"
• there's git log. Think of Git's log as a journal that remembers all the changes we've committed so far, in the order we committed them : git log
•  To push our local repo to the GitHub server we'll need to add a remote repository : git remote add origin https://github.com/try-git/
• So let's push our local changes to our origin repo (on GitHub) :  git push origin master
•  We can check for changes on our GitHub repository and pull down any new changes by running :git pull origin master
• In this case we want the diff of our most recent commit, which we can refer to using the HEAD pointer : git diff HEAD
• run git diff with the --staged option to see the changes you just staged : git diff --staged
• You can unstage files by using the git reset command : git reset octofamily/octodog.txt
• Files can be changed back to how they were at the last commit by using the command: git checkout -- <target>. Go ahead and get rid of all the changes since the last commit for octocat.txt : git checkout -- octocat.txt
• create a branch called clean_up : git branch clean_up
• You can switch branches : git checkout branch_name
• We're already on the master branch, so we just need to tell Git to merge the clean_up branch into it : git merge clean_up
• You can use git branch -d <branch name> to delete a branch : git branch -d clean_up
• All that's left for you to do now is to push everything you've been working on to your remote repository : git push