Data Structure is the method of arranging data in such a way that it can be used to perform common and most frequent operations effectively and efficiently. It represents a logical relationship between data and its function.

Data Structures are about creating data elements in terms of some relationship, for organizing and storing them in a better way.

A linked list is a linear data structure, which contains two parts. First is data part, which is used to information of the element in the list. The other one is link, which contains the pointer to next node or previous node or both, that holds the address of the node. Combination of these make a node.

A singly linked list is a linear data structure, in which link only store reference to the next node. It can not point to the previous node. The last node always points to null. It’s size can be changed during the run time, i.e. dynamically. It is also known as one-way list. We cannot traverse in backwards direction.

A doubly linked list is a linear data structure, in which link store reference to the next node as well as to the previous node.

The last node always points to null. We can traverse in both direction. Operations like adding, deleting a node require more changing more links than a singly linked list.

A circular linked list is a linked list, in which all nodes are connected to form a circle, i.e. the last node points to the first node of the list. A circular linked list can be a singly circular linked list or doubly circular linked list. We can traverse the complete linked list by starting from any point in the list.

A stack is a non-primitive data type linear data structure ordered list, in which the addition of new data and deletion of data takes place from one end, known as top.

Elements can’t be deleted or inserted from the middle of the stack. Stacks follows Last in first out (LIFO) principle. The size of the stack can be static as well as of dynamic size depending on the need of the user.

Binary search is an efficient algorithm for finding an element from a sorted list or an array. It works by repeatedly dividing the list in half portion so it that could contain the item or element, until we have narrowed down the possible locations to just one element and at that location we will find our required element in the list.

Binary search is also known as half-interval search, and runs in logarithmic time and in the worst case it takes O (log n) comparisons, where n is the number of element.

There are so many sorting algorithms such as quick sort, bubble sort, balloon sort, radix sort, merge sort, etc.

But none of them can be considered as the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort.

Dynamic data structures are those structures that expand and contract as a program runs, i.e. their size is decided during the run time.

It provides a flexible way of manipulating data because it can adjust according to the size of the data. It enables the programmer to control exactly how much memory is utilized in the heap memory.

The advantages of Linked List over array are as follows:

• Unlike Linked List, it is expensive to insert and delete elements in the array.
• One can’t double or triple the size of the array, as it occupies a block of memory space.
• Successive element’s need not occupy adjacent space in memory.
• It doesn’t require reallocation or reorganization of the entire list because the data elements need not be stored contiguously in memory.

When we want to insert the element/ data into the data structure, but there is no available space available, this situation is called overflow.

When we want to delete element/data from a data structure that is already empty, this situation is called underflow.

When an overflow or underflow condition happens, either the program will crash or the programming language will have its own way of handing things, i.e. by giving the exception in the program.

Stack is used to perform recursion because of its LIFO (Last In First Out) property as it remembers its ‘caller’ so knows whom to return when the function has to return.

Recursion uses system stack for storing the return addresses of every function calls.

Every recursive function can have its equivalent iterative function. Even when such equivalent iterative functions are coded, explicit stack is to be used.

A multidimensional array is very useful in organizing subgroups of elements within an array. A multidimensional array stores memory addresses of data in a pointer array and an array of pointers.

Multidimensional arrays are used to store element in matrix form.

E.g: a railway timetable, we need to use a 3-dimensional array for storing height, width and length of each room on each floor of a building.

A set is a collection of objects, need not be in any particular order. The cardinality of a set is the number of elements present in set. In set no element can appear more than once. An empty set is a set whose cardinality is zero. A singleton set is a set whose cardinality is one.

There are many different ways to implement sets. The simplest one, but in most cases it is the least efficient, is to simply create a linear list containing each of the elements in the set.

Hashing is the technique of transforming a string of characters into a usually shorter, fixed length value or key that represents the original string. The values are stored in a data structure called hash table. Hashing is used to index and retrieve items in a database because it is faster to find the element using the short hashed key than to find it using the original value.

Hashing allows modifying and retrieve any data/element in a constant time O(1). It is mostly used in the encryption and decryption of digital signatures.

A binary search tree is a special kind of binary tree, which is either empty or follows all the given conditions:

• Every node has a different value and no two nodes should have the same value, i.e. all values are distinct.
• The values in any of the left sub-tree is less than the value of its parent node.
• The values in any of the right sub-tree is greater than the value of its parent node.
• The left and right sub-tree of each node are again a binary search tree.

If we need to find the middle element of a linked list in one pass, we need to maintain two reference, one increment at each node at a time while the other increments after two nodes at a time.

We need to increment the first reference until it reaches the end of the linked list, by having this arrangement in the list, when the first pointer reaches the end, the second pointer will point to a middle element of the linked list, and we get the required element.

The advantage of heap memory over the stack are as follows:

• In Heap, we can allocate and reallocated memory dynamically according to our need that make it more flexible than stack memory.
• When we use recursion it requires a lot of memory, as the size of heap memory is more than stack it is preferred more.
• In Heap when we create any object that will be to all threads, whereas variables stored in stack are only visible to the owner as private memory.

Binary search is more efficient than a linear search because it performs fewer comparisons. In linear search, we can only eliminate one element/data per comparison every time we can’t find the target value, whereas in the binary search, we eliminate half the set with each comparison.

Binary search require O (log n) time compared to linear search’s O(n) time. This means that the more of the elements present in the array, the faster is the binary search compared to a linear search.