LinkedList<> over ArrayList<>?

LinkedList and ArrayList are two different implementations of the List interface of Java Collections Framework. LinkedList is implemented based on doubly-linked list where as ArrayList implements it with a dynamically resizing array.

These implementations differ in algorithmic runtime as shown below

For ArrayList

• Accessing Data : get(int index) - Constant time O(1) - Reading is faster which is main advantage of using ArrayList
• Adding new elements : 
• • End of list - add(E element) - If it fits into existing size of the list O(1). If the array is full and needs resize O(n) which is worst case
  • Add at a particular index (in between) - add(int index, E element) - This requires re indexing of all the elements after insertion position and hence in general O(n-index) and worst case will be O(n)
  • ListIterator.add(Element e) - Since we will adding at a position, it is same as adding an element at a index
• Remove an element:
• • remove(int index) - As with adding elements at a particular index, removing (if not last element) requires re indexing all the elements after the element which is removed. So, in general it is O(n-index) and worst case is O(n).
  • remove(Element e) - It is same as removing at an index.
  • Iterator.remove() - Same as removing at an index.

For LinkedList

• Accessing Data : get(int index) - O(n) - Reading is slower compared to ArrayList since we need to sequentially move towards the specified index to get the data.
• Adding new elements : 
• • add(E element) - constant time O(1) only if you happen to have a pointer to the location where you are inserting (index). Else O(n-index)
  • add(int index, E element) - O(n-index) and worst case is O(n)
  • ListIterator.add(E element) is O(1)  - mainly because you are already at the index of the element after which element will be added. This is the main advantage of Linked Liked over ArrayList.
• Remove an element:
• • remove(int index) - O(n) as we need to traverse to index and remove it. But we need not re index since only the pointers will be adjusted.
  • Iterator.remove() - O(1) same as ListIterator.add(E element). Again this is one of the main advantage over ArrayList.

As a conclusion,

LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.

ArrayList, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

And one more important point to note here that memory requirements for LinkedList is more than ArrayList since it has to store the information about next and previous pointers. So, when we are looking at memory angle, we need to take this into consideration.

Choice of Data structure depends on specific use case and how we need to handle the add/remove and read operations on the data structure. During design, need to list all the possible uses of the data structure and finalize on optimized data structure to be used.

Is Java “pass-by-reference” or “pass-by-value”?

Java is always pass-by-value. !!!!

However there is a difficulty in understanding this or more over a confusion when we are dealing with method calls involving Java Objects.

Java Specification says that everything in Java is pass-by-value and there is nothing called "pass-by-reference" in Java. To understand more about this, we can start with Java Object and reference understanding. Say we have a class called Employee

public class Employee

{

     private int id;

     private int age;

     private String name;

    // Getters-Setters ...

}

Now we will create an object instance of Employee as below

    Employee myEmp = new Employee();

Here myEmp is not "Employee" but a handle to point to an instance of "Employee" object somewhere sitting in memory.

We have a method call handleEmployee as below which needs Employee object

public void handleEmployee(Employee emp)

{

     // Do Something with employee

    

}

When we call the above method as below

  

      Employee myEmp = new Employee();

      handleEmployee(myEmp);

What essentially happens here is that, we are passing a copy of the handle (myEmp) which was used to access Employee object to the calling method.

Why java pass-by-value ?

Because, we as passing a copy of a reference variable - myEmp, to handleEmployee method ( as emp).

This gives the method handle to get to Employee object but it cannot change myEmp reference itself.

public void handleEmployee(Employee emp)

{

     // Do Something with employee

     emp = null;

}

When we make emp = null, then it just nullifies the copy so that it will no longer refer Employee object. But the original myEmp is still unaffected.

So, as a conclusion, Java is always "pass by value" whether we are passing primitives ( int, char, long, etc) or an object.

Unit Testing - Test Private methods using JUnit

Unit testing is a very critical and crucial part of any development activity. Simple but sound unit test cases can save many hours of debugging time for a developer which indeed improves the code quality. For a Java developer, Junit is one of the old and preferred way of fortifying his code. 

During unit testing, we often need to test a class completely which includes testing individual private methods for proper bug free execution which covers all corner case. Below is description on how we can test a private method using JUnit.

Class targetClass = MyClassWithPrivateMethod.class;
Object[] myMethodArgsClasses = new Object[]
              {MethodArgType1.class,MethodArgType2.class,...}
Method method = targetClass.getDeclaredMethod(methodName,
                 myMethodArgsClasses);
method.setAccessible(true);
method.invoke(targetObject, argObjects);
// More testing goes here