(ii). Non-Primitive Data Structures / Compound Data Structure

Simple Data Structures are combined in many ways to form more complex structures called a compound data structure. Non-primitive types are the sophisticated members of the data structure family. They don’t just store a value, but rather a collection of values in various formats.

In the traditional computer science world, the non-primitive data structures are divided into:

1. **Linear Data Structure**: These are single-level data structure. A data structure is said to be linear if its elements forms a sequence. Example Stack, Queue and Linked List

2. **Non Linear Data Structure:-** These are mutlilevel data structures. Example Tree.

**Linear Lists/ Arrays:**

Linear lists or Arrays refer to a named list of a finite number n of similar data elements. Each of the data elements can be referenced respectively by a set of consecutive numbers. Example if the name of a linear list is ARR, and it contains 10 elements then its list elements will be referenced by ARR[0], ARR[1], ARR[2],……..ARR[9].

**STACKS:**

Stacks data structures refer to the lists stored and accessed in a special way, where LIFO(Last In First Out) technique is followed. In stacks insertion and deletion take place only at one end called the top. Example: Stacks of plate where plates can be inserted or removed from the top only.

**Queues:**

Queues data structures are FIFO( First In First Out) lists, where insertion takes place at one end that is the rear end and deletion takes place at the front end of the queues. Example: people standing in a queue for their turn to vote where the first person will vote first and leave the queue and a new person will join the queue at the rear end.

**Linked lists:**

Linked lists are special lists of some data elements linked to one another. The logical ordering is represented by having each element pointing to the next element. Each element is called a node, which has two parts. The info part stores the information and the reference pointer part which stores the reference to the next element.

**Operations on data Structures:**

The basic operations that are performed on the data structures are as follows:

1. Insertion: addition of a new data element.

2. Deletion: Removal of the data element.

3. Searching: Searching for the specified data element.

4. Traversal: Processing all data elements of a data structure one by one.

5. Sorting: Arranging data elements of a data structure in a specified order.

6. Merging: Combining data elements of two similar data structures to form a new data structure of the same type.