DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Home » Data Structure

Introduction to Data Structure

What is Data Structure?

A data structure is a method of organizing and storing data so that it can be accessed and processed efficiently. It defines how individual data elements are arranged and how different operations can be performed on them.

Data structure is a logical organization of data.
It specifies how to store and access the data from memory.

Data Structure Operations

Data structures provide several basic operations for managing and processing stored data. The operations performed depend on the type of data structure and the requirements of the application.

Traversing Accessing each element exactly once, is knows as traversing. It is also known as visiting.
Insertion Adding a new element to data structure.
Deletion Removing an element from the data structure.
Searching Finding the location of an item in data structure.
Sorting Arranging the items in ascending or descending order is known as sorting.

Importance of Data Structure Operations

Data structure operations are important because programs frequently need to add, remove, locate, rearrange, or access data. The efficiency of these operations can affect the overall performance of an application. Choosing a suitable data structure can make frequently performed operations easier and more efficient.

Types of Data Structures

There are two types of Data Structure: Linear Data Structure and Non Linear Data Structure. The classification depends on how data elements are logically arranged and related to each other.

1. Linear data structure

A data structure is said to be linear if items are arranged in linear or sequential format. In a linear data structure, elements are generally processed one after another in a logical sequence.

Array
Stack
Queue
Linked List

2. Non-linear data structure

Non-linear data structure does not support sequential format. In a non-linear data structure, an element may be connected to multiple other elements. These structures are useful for representing hierarchical and network-based relationships.

Tree
Graph

Difference Between Linear and Non-linear Data Structures

Linear and non-linear data structures differ mainly in the way their elements are organized. Linear structures arrange elements in a sequential manner, whereas non-linear structures can represent more complex relationships between elements.

Linear: Elements are arranged sequentially.
Non-linear: Elements can have multiple relationships or connections.
Linear examples: Array, Stack, Queue, and Linked List.
Non-linear examples: Tree and Graph.

Arrays

An array is one of the most commonly used data structures for storing a collection of elements. It provides a way to store multiple values under a single variable name and access individual elements using an index.

Array is a list of a finite number of homogeneous data items (i.e. data items of the same type).
Array is also known as subscripted variable.
Array can be accessed by index.
Number of elements in array is known as length of array.
LENTH = UB – LB + 1
Where UB is upper bound and LB is lower bound. Here length = UB when LB = 1.
The element of an array A may be denoted by subscript notation.
A1, A2, A3, ……. An
By the parentheses notation
A(1),A(2), …….. A(N)
By the bracket notation
A[1],A[2],A[3], ….A[N]

Characteristics of Arrays

Arrays have several characteristics that make them useful when a program needs to store multiple values of the same type. Elements are generally stored in a continuous memory arrangement, allowing an element to be accessed directly using its index.

Arrays generally store elements of the same data type.
Elements can be accessed using an index or subscript.
The size of an array is generally defined when the array is created.
Array elements can be processed using loops.
Arrays can be one-dimensional or multidimensional.

Representation of linear arrays in memory

An array occupies a sequence of memory locations. Since each element has a fixed size, the address of an element can be calculated using the base address of the array and the position of that element.

Suppose A be an array in the memory. As we know that memory of the computer is simply a sequence of addressed location.
LOC(A[i]) = address of element A[i] of the array A
```
            1000
            1001
            1002
            1003
            Computer Memory
        
```
Address of first element of array is known as base address.
Using base address, the computer calculates the address of any element of array.
LOC(A[i]) = base(A) + w ( I – lower bound)
Where w is the number of words(bytes) per element of array.
Arrays are similar to matrices. There can be single dimensional array or multidimensional array.
Ex:
int a[5];
Here int is data type, and a is array name and 5 is the size of array. All element of the array must be of same data type. In this sense, it is a homogenous data structure.
The allocation of information about an array is fixed at compile time. Its entry is done inn symbol table at compile table.
During execution the memory space is allocated for array. For all element of array continuous space is allocated. The array name is the start address of this memory.

Array Indexing

Array indexing provides a way to identify and access individual elements stored in an array. Each element is associated with an index, and the index is used to retrieve or modify the corresponding value.

The starting index of an array depends on the programming language being used. For example, many commonly used programming languages use zero-based indexing, where the first element is stored at index 0.

One Dimensional Array

A one-dimensional array stores elements in a single sequence. It is useful when data can be represented as a simple list of values, such as marks, prices, ages, or identifiers.

int a[5];

In this declaration, int represents the data type, a represents the array name, and 5 represents the number of elements that the array can store.

Two Dimensional Array

A two dimensional array is like a two dimensional matrix, that has rows and columns. An integer 2D array with 10 rows and 20 columns can be declared as:

int a[10][20];

Here 10 is number of rows and 20 is number of columns.

A two-dimensional array is useful when data needs to be represented in a tabular form. Each element can be identified using two indexes, generally representing its row and column.

Storing In Main Memory

A two dimensional matrix is represented in two dimensions. It is to be stored in the main memory, which is one dimensional. Hence some conversion processes has to be adapted from two dimensions to one dimension. There are two conversion schemes.

Row major storing.
Column major storing.

These storage methods determine the order in which the elements of a two-dimensional array are arranged in the computer's memory.

Row major implementation

In row major storing elements are stored, row by row, first store first row and then second row and so on.

Row-major storage is commonly used when the elements of each row need to be processed sequentially. The elements of the first row are stored before the elements of the second row.

Q.1: see the declaration:

#define RMAX        10
#define CMAX        20

What is the address of element a[r][c] by using row major storing?

Ans: Location of a[r][c]
a + (r*CMAX+c)
Where array name "a" is the base address of the array. Only CMAX is needed, not RMAX.

Column major implementation

In column major storing elements are stored, column by column, first store first column and then second column and so on.

In column-major storage, all elements belonging to the first column are stored before the elements of the second column. This arrangement is useful in environments where data is processed column by column.

Q.1: see the declaration:

#define RMAX        10
#define CMAX        20

What is the address of element a[r][c] by using column major storing?

Ans: Location of a[r][c]
a + (c*RMAX+r)

Where array name “a” is the base address of the array. Only RMAX is needed, not CMAX.

Difference Between Row Major and Column Major Storage

Row-major and column-major are two different methods of storing multidimensional arrays in linear memory. The main difference is the order in which the elements are stored.

Row major: Elements are stored row by row.
Column major: Elements are stored column by column.
Row major formula: Uses the number of columns to calculate the location.
Column major formula: Uses the number of rows to calculate the location.

Applications of Arrays

Arrays are used in many programming and data processing applications because they provide an organized way to store multiple values of the same type. Some common applications include:

Storing lists of numbers or values.
Representing tables and matrices.
Implementing sorting and searching algorithms.
Storing collections of records or measurements.
Representing images and other grid-based data.
Supporting other data structures and algorithms.

Advantages of Arrays

Arrays provide several benefits when the number of elements and their data type are known in advance. Their indexed structure makes accessing individual elements straightforward.

Elements can be accessed directly using an index.
Arrays are simple to understand and implement.
They provide efficient storage for collections of similar data.
They are useful for implementing many algorithms.
They can be used to represent one-dimensional and multidimensional data.

Limitations of Arrays

Although arrays are useful for many applications, they also have some limitations. In many programming environments, the size of an array is fixed after allocation, which can make dynamic insertion and deletion more difficult.

The size of a traditional array is generally fixed.
Insertion or deletion in the middle may require shifting elements.
Unused allocated space can result in memory wastage.
Arrays are generally most suitable when elements have the same data type.

Conclusion

Data structures provide an organized way to store and process information in computer programs. They define how data is arranged and how common operations such as insertion, deletion, searching, sorting, and traversal can be performed.

Arrays are one of the fundamental data structures and can be used to store homogeneous elements in a sequential memory arrangement. Understanding arrays, indexing, memory representation, and row-major and column-major storage provides an important foundation for learning more advanced data structures and algorithms.