Data Structure
A data structure is a way of organizing and storing data in a computer so that it
can be accessed and used efficiently. It refers to the logical or mathematical
representation of data, as well as the implementation in a computer program.
Data structures can be classified into two broad categories:
• Linear Data Structure: A data structure in which data elements are
arranged sequentially or linearly, where each element is attached to its
previous and next adjacent elements, is called a linear data structure.
Examples are array, stack, queue, etc.
• Non-linear Data Structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures.
Examples are trees and graphs.
Classification of Data Structure
• Applications of Data Structures:
Data structures are used in a wide range of computer programs and
applications, including:
• Databases: Data structures are used to organize and store data in a
database, allowing for efficient retrieval and manipulation.
• Operating systems: Data structures are used in the design and
implementation of operating systems to manage system resources, such
as memory and files.
• Computer graphics: Data structures are used to represent geometric
shapes and other graphical elements in computer graphics applications.
• Artificial intelligence: Data structures are used to represent knowledge
and information in artificial intelligence systems.
• Advantages of Data Structures:
The use of data structures provides several advantages, including:
• Efficiency: Data structures allow for efficient storage and retrieval of data,
which is important in applications where performance is critical.
• Flexibility: Data structures provide a flexible way to organize and store
data, allowing for easy modification and manipulation.
• Reusability: Data structures can be used in multiple programs and
applications, reducing the need for redundant code.
• Maintainability: Well-designed data structures can make programs easier
to understand, modify, and maintain over time.
Array
An array is a linear data structure that stores a fixed-size sequence of elements
of the same data type in contiguous memory locations. Each element can be
accessed directly using its index, which allows for efficient retrieval and
modification.
The properties of the arrays vary in different programming languages. We are
discussing with C language.
1. Fixed Size of an Array
In C, the size of an array is fixed after its declaration. It should be known at the
compile time and it cannot be modified later.
2. Homogeneous Collection
An array in C cannot have elements of different data types.
3. Indexing in an Array
Indexing of elements in an Array in C starts with 0 instead of 1. It means that the
index of the first element will be 0 and the last element will be (size - 1) where
size is the size of the array.
4. Dimensions of the Array
An array in C can be a single dimensional like a 1-D array or multidimensional
like a 2-D array, 3-D array, and so on. The number of elements in a
multidimensional array is the product of the size of all the dimensions.
5. Contiguous Storage
All the elements in an array are stored at contiguous or consecutive memory
locations. We can easily imagine this concept in the case of a 1-D array but
multidimensional arrays are also stored contiguously. It is possible by storing
them in row-major or column-major order where the row after row or column
after the column is stored in the memory. We can verify this property by using
pointers.
6. Random Access to the Elements
It is one of the defining properties of an Array in C. It means that we can
randomly access any element in the array without touching any other element
using its index. This property is the result of Contiguous Storage as a compiler
deduces the address of the element at the given index by using the address of
the first element and the index number.
Address of ith = Address of 1st Element + (Index * Size of Each Element)
7. Relationship between Array and Pointers
Arrays are closely related to pointers in the sense that we can do almost all the
operations possible on an array using pointers. The array's name itself is the
pointer to its first element.
8. Bound Checking
Bound checking is the process in which it is checked whether the referenced
element is present within the declared range of the Array. In C language, array
bound checking is not performed so we can refer to the elements outside the
declared range of the array leading to unexpected errors.
9. Array Decay
Array decay is the process in which an array in C loses its dimension in certain
conditions and decays into pointers. After this, we cannot determine the size of
the array using sizeof() operator. It happens when an array is passed as a
pointer.
A string is a sequence of characters. The following facts make string an
interesting data structure.
• Small set of elements. Unlike normal array, strings typically have smaller
set of items. For example, lowercase English alphabet has only 26
characters. ASCII has only 256 characters.
• Strings are immutable in programming languages like Java, Python,
JavaScript and C#.
• Many String Problems can optimized using the fact that the character set
size is small. For example sorting can be done faster, counting frequencies
of items is faster and many interesting interview questions are based on
this.