Home
Data Structures

Array-based implementation

An array-based implementation of the List ADT uses a contiguous block of memory (an array) to store elements sequentially. This method is often called a "linear list" or "contiguous list" because the elements are stored in adjacent positions within the array.

Key Characteristics

  • Fixed Maximum Size: The maximum number of elements the list can store is determined at creation, as arrays have a fixed capacity.

  • Sequential Storage: Each element’s position in the array matches its position in the logical list.

  • Static Allocation: Memory for the array is allocated before run-time, so unused spaces (if the list is not full) may waste memory.

Core Components

  • Data Array: Stores the actual list elements (e.g., listArray[]).

  • Size Variable: Tracks the current number of elements in the list (e.g., size or listSize).

  • Maxsize Variable: Holds the capacity of the array (e.g., MAX or maxSize).

Main Operations

OperationDescription
CreateInitialize the array and set the current size to zero.
Insert(element, pos)Insert an element at a specific position; may require shifting elements to the right.
Delete(pos)Remove the element at a specific position; shift elements to the left to fill the gap.
Search(element)Find the position of the first occurrence of an element.
Display/ListPrint or traverse the elements in the list.
IsEmpty()Check if the list contains no elements.
IsFull()Check if the list has reached maximum capacity.

Example C Structure

#define MAX 100
int listArray[MAX];
int size = 0; // Current number of elements

// Inserting at position pos (0-based indexing)
void insert(int element, int pos) {
    if (size == MAX) return; // List is full
    for(int i = size; i > pos; i--)
        listArray[i] = listArray[i - 1];
    listArray[pos] = element;
    size++;
}

// Deleting from position pos
void delete(int pos) {
    if (size == 0) return; // List is empty
    for(int i = pos; i < size - 1; i++)
        listArray[i] = listArray[i + 1];
    size--;
}

Advantages

  • Fast direct access: Accessing an element by its index is O(1)O(1) time.

  • Simple implementation: Arrays are widely supported and easy to use.

Disadvantages

  • Insertion/Deletion inefficiency: Inserting or deleting elements (not at the end) requires shifting, which is O(n)O(n).

  • Fixed size: List cannot grow beyond its initially declared capacity, potentially wasting or lacking space.

This approach is favored for scenarios where the number of elements is known and relatively static, and when random access is more important than insert/delete performance.

Real-World Examples of Array-Based Implementation

Array-based implementations are widely used in software and systems where fast, random access to data elements and efficient storage are priorities. Below are several real-world scenarios and domains where array-based lists are integral.

1. Storing Fixed Collections

  • Contact Lists in Phones: Many phones use arrays for storing contacts when the maximum number of contacts is known or limited, providing instant access to a contact by index.

  • Student Scores: Arrays are often chosen to store exam or test scores for a class, as the number of students is usually fixed and accessing any student's score by roll number is fast.

2. Tabular Data Storage

  • Matrices and Spreadsheets: Two-dimensional arrays represent tables or matrices, common in spreadsheet applications and matrix arithmetic in scientific computing.

  • Image Processing: Images are stored as arrays of pixels, allowing software to access or modify each pixel by its row and column indices efficiently.

3. Implementing Algorithms

  • Sorting and Searching: Classic algorithms like bubble sort, selection sort, and binary search typically work directly on array-based lists for performance and direct access.

  • Dynamic Programming: Arrays are used to store intermediate results of subproblems in algorithms such as computing Fibonacci numbers, route optimization, or text processing.

4. Data Buffers

  • Network and Communication Buffers: Arrays provide a temporary holding area (“buffer”) for data such as network packets, audio streams, or file blocks before they are processed or transmitted.

  • Queue Implementations: Array-based queues are used for efficiently managing and processing buffered data in many embedded systems and applications.

5. Hardware and Embedded Systems

  • Sensor Data Storage: Embedded systems often record readings from sensors in array-based lists, as the data size and sample rate are typically fixed and known in advance.

  • Game Boards: Board games like chess or tic-tac-toe are implemented as arrays, where each cell holds the current state (empty, occupied, color, etc.).

6. Text and String Management

  • Text Editors: Characters in each line are stored in arrays for direct retrieval, editing, and manipulation within text editors and IDEs.

  • String Handling: Most programming languages represent strings as arrays of characters, making operations like substring extraction, replacement, and reversal straightforward.

Summary Table

Application AreaHow Arrays Are Used
Contact/Score ListsQuick access and update to fixed-size collections
Matrices/SpreadsheetsRow-column storage for efficient processing and computation
ImagesPixel data stored as 2D arrays for fast rendering/editing
Algorithm ImplementationDirect use in sorting, searching, and dynamic programming for better performance
Data BuffersTemporary holding pools for streaming data, networks, and communication
Hardware StorageRecording sensor/embedded system data with predictable memory layout
Text/String ManagementFast, in-place editing and searching in text and documents