Difference between linked list and array data structure in Java Programming

Array and linked list are two fundamental data structure in programming world. Almost all programs use Array in some form or other, which makes it increasingly important to learn array and linked list. Difference between linked list and array data structure is also a popular data structure question, frequently asked in various programming job interview. This makes it even more important to learn and understand difference between an array and a linked list. Well there are lot of difference between these two starting from how they store data, to how you retrieve data from them. Main difference comes from the fact that array elements are stored in contiguous memory location, which makes it easy to retrieve them in quick time, while linked list elements are scattered through out memory, where one element knows address of other, it makes it hard to retrieve element from linked list in quick time. Some of the differences which we saw in ArrayList vs LinkedList also applicable at data structure level, because ArrayList is backed by array and LinkedList is internally backed by double linked list in Java. In this tutorial, we will learn differences between these two fundamental data structure in more details. Once you know the difference, you can make a concise choice of which data structure suits your need better. Since both of them offers distinctive advantage over others, in terms of speed and flexibility, You can make an informed choice based upon your need.

Read more »

Read More..

Find subarray of an array coding

Q. Can you write code to find starting position of a sub array in an array? if not found, return -1 as the position.

For example, find

• [-3, 7] in [5, 9, -3, 7, 8] --> 2
• [7, 8, 9] in   [5, 9, -3, 7, 8] --> -1
• [5] in   [5, 9, -3, 7, 8] --> 0

A. This can be approached a number of different ways. I will discuss 3 approaches.

Define the interface first

 
package findarray;

public interface FindArray {
    abstract int findArray(int[] array, int[] subArray) ;
}

Approach 1: Make use of the Collections.indexOfSubList method as per dont reinvent the wheel principle.

 
package findarray;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FindArrayImpl1 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        //convert primitive int to Integer and then use the Collections API 
        return Collections.indexOfSubList(convertArrayToList(array), convertArrayToList(subArray));
    }
    
    /**
     * convert int[] to List<Integer>
     */
    public List<Integer> convertArrayToList(int[] input)
    {
        if (input == null)
        {
            return null;
        }
        List<Integer> output = new ArrayList<Integer>(input.length);
        for (int i = 0; i < input.length; i++)
        {
            output.add(Integer.valueOf(input[i]));
        }
        
        return output;
        
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl1().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl1().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl1().findArray(array, subArray3));
        
    }
}

Approach 2: Write your own logic. The interviewer might be wanting to test your logic processing ability.

 
package findarray;

public class FindArrayImpl2 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        int index = -1; // assume not found
        
        for (int i = 0; i < array.length; i++)
        {
            // Check if the next element of array is same as the first element of subarray
            if (array[i] == subArray[0])
            {
                //check subsequent elements of subarray against the subsequent elements of array
                for (int j = 0; j < subArray.length; j++)
                {
                    //if found, set the index
                    if (i + j < array.length && subArray[j] == array[i + j])
                    {
                        index = i;
                    }
                    else
                    {
                        index = -1;
                        break;
                    }
                }
            }
        }
        
        return index;
        
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl2().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl2().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl2().findArray(array, subArray3));
        
    }  
}

Approach 3: Using the StringBuilder class.

 
package findarray;

public class FindArrayImpl3 implements FindArray
{
    
    @Override
    public int findArray(int[] array, int[] subArray)
    {
        if (array == null || subArray == null || subArray.length > array.length)
        {
            return -1;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++)
        {
            sb.append(array[i]);
        }
        
        StringBuilder sbSub = new StringBuilder();
        for (int i = 0; i < subArray.length; i++)
        {
            sbSub.append(subArray[i]);
        }
        
        int index = sb.toString().indexOf(sbSub.toString());
        if (index >= 0)
        {
            return index;
        }
        else
        {
            return -1;
        }
    }
    
    public static void main(String[] args)
    {
        int[] array =
        {
            5, 9, -3, 7, 8
        };
        
        int[] subArray1 =
        {
            -3, 7
        };
        
        //should return 2
        System.out.println(new FindArrayImpl3().findArray(array, subArray1));
        
        int[] subArray2 =
        {
            7, 8, 9
        };
        
        //should return -1
        System.out.println(new FindArrayImpl3().findArray(array, subArray2));
        
        int[] subArray3 =
        {
            5
        };
        
        //should return 0
        System.out.println(new FindArrayImpl3().findArray(array, subArray3));
        
    }
}

The output for all 3 approaches:

 
2
-1
0

Feel free to show us other creative and better approaches.

Read More..