Categories: Data Structure

DSA: Concept of Array

A group of related data elements stored at adjacent memory locations is referred to as an array. One of the most basic data structures, it allows for random access to each data element by its index number.

Properties of an Array:

Arrays contain a number of crucial characteristics that make them helpful in a wide range of applications:

  • Constant-time access: Regardless of the size of the array, accessing an element using its index takes a fixed amount of time since the elements of an array are stored in contiguous memory locations.
  • Sequential storage is made simple by the fact that arrays keep their components in proximity to one another in memory.
  • Fixed-size: An array’s fixed size refers to the fact that the maximum number of elements it may store is decided at the time of formation.
Representation of an array:

An array is typically represented as a block of contiguous memory locations, each of which stores an element of the array. Let us see an array declaration :

int arr[5]={1 , 2 , 3 , 4 , 5};

here,

  • Name of the array: arr
  • Type: int
  • Size: 5, which means up to 5 elements can be stored in the array.
  • Starting index: 0
Memory allocation of an array:

As mentioned earlier, an array’s data elements are all kept together in the main memory at contiguous locations. The base address, or the address of the first member in main memory, is represented by the array name. The array’s elements are each properly represented by an index. We can define the indexing of an array in the below ways –

  • 0 (zero-based indexing): The first element of the array will be arr[0].
  • 1 (one-based indexing): The first element of the array will be arr[1].
  • n (n – based indexing): The first element of the array can reside at any random index number.
Basic Operations:

Following are the basic operations supported by an array.

OperationDescription
TraverseIterating over every element in the array, this operation applies an operation to each element, such as printing its value.
InsertAdds a new element to the array at a specified index.
DeleteRemoves an element from the array at a specified index, shifting the remaining elements to fill the gap left by the deleted element.
UpdateThis operation alters the value of an element at a certain index.
SearchSearches for a specific element in the array either by its index or by its value.
Complexity of Array operations:

Time and space complexity of various array operations are described in the following table.

Time Complexity

OperationAverage CaseWorst Case
AccessO(1)O(1)
SearchO(n)O(n)
InsertionO(n)O(n)
DeletionO(n)O(n)

Space Complexity

In array, space complexity for the worst case is O(n).

Note: also read about SQL: Sequence

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Recent Posts

Generate Parenthesis | Intuition + Code | Recursion Tree | Backtracking | Java

Problem Statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example…

2 months ago

Square Root of Integer

Given an integer A. Compute and return the square root of A. If A is…

1 year ago

Build Array From Permutation

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…

1 year ago

DSA: Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is…

1 year ago

DSA: Trie

What is a Trie in DSA? A trie, often known as a prefix tree, is…

1 year ago

Trees: Lowest Common Ancestor

What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…

1 year ago