Data Structures

This is one of the most frequently asked data structures coding questions and answers for freshers in recent times.

An ArrayList is a collection of homogenous data types stored in contiguous memory locations while a LinkedList is a collection of data elements linked to each other using pointers. Since pointers are used the elements are not required to occupy contiguous memory locations. Let’s see how this arrangement affects searching, insertion and deletion of data.

• Insertion and Deletion of elements is much easier in a LinkedList. This is because when a new node is added or existing node removed, only the pointers need to be rearranged. No shifting of data is required. However, when an element is added in the mid of anArrayList or removed from the middle, all the remaining elements need to be rearranged resulting in higher cost of operation.
• Searching, however, is faster is anArrayList as the elements are stored in contiguous memory locations and can be looked up without having to traverse the entire list. In the case of a LinkedList, the entire list needs to be traversed until the element being searched for is found.

Hence if the application involves a number of reads than writes an ArrayList is suitable otherwise a LinkedList.

A singly LinkedList is one in which the node contains two fields – data – the actual content and – address – link to the next node. Though this type of list occupies less memory, it can be traversed in one direction only. A doubly LinkedList is one in which the node contains data and address of previous as well as the next node. This type of list can be traversed in both directions.

Expect to come across this, one of the most important data structures interview questions for experienced professionals in web development, in your next interviews.

Consumer Producer problem is one in which we have two independent entities – a producer and a consumer sharing a common buffer/queue. Producer writes data to the queue while Consumer consumes from it. The problem is that if queue is full then the producer should wait for space to become available before writing to it while if the queue is empty, the consumer should wait for data to become available before starting to read again.

In a traditional queue, if the queue is full and the producer tries to add more elements to it, it will throw an exception. On the other hand, if the queue is empty and the consumer tries to read from it, it will throw an exception again. This is where Blocking Queue is of help.

Blocking Queue is a part of the java.util.concurrent package. It is a type of Queue with the additional feature of blocking if the queue is full or empty. A thread trying to add/enqueue an element to an already full queue is blocked until another thread makes space for it by removing/dequeuing an element from the queue. Similarly, a thread trying to dequeue an element from an empty queue is blocked until another thread adds an element to the queue. Hence in this way, it helps solve the Consumer Producer problem.

The various implementations of BlockingQueue are:

• LinkedBlockingQueue
• PriorityBlockingQueue
• SynchronousBlockingQueue