Static and Dynamic Data Structures

Data structures are the fundamental building blocks of computer programming. They determine how data is organized, stored, and manipulated within a software application. There are two main categories of data structures: static and dynamic. Static data structures have a fixed size and are allocated in memory during compile-time, while dynamic data structures can grow and shrink in size during runtime. This article will provide an overview of the key differences between static and dynamic data structures, their use cases, and the trade-offs to consider when choosing between them.

What is Static Data Structure?

Static data structures are characterized by their fixed size and predefined memory allocation. This means that the amount of memory allocated to the structure is determined at compile time and remains constant throughout the program’s execution. Examples of static data structures include arrays .

Features of Static Data Structures:

There are many features of static data structures. Let’s discuss the most popular of them:

• Memory Allocation: For static data structures, static memory is allocated at the compile time by the compiler, which is stored in the stack memory of the program.
• Memory Deallocation: Memory allocated to the static data structures deallocates when they go out of scope or the program ends.
• Continuous Memory Allocation: As we have discussed above, continuous memory is allocated to the static data structures, which means there is no need to store the structural information of the data structure or explicit data variable to store the information of the memory location.

Advantages of Static Data Structures:

• Static data structures have a fixed size and structure, making them simpler to implement and understand.
• Since the size is known in advance, the memory can be allocated efficiently.
• The behavior of static data structures is more predictable, making them suitable for real-time systems.
• Accessing elements in static data structures is generally faster than in dynamic data structures.

Disadvantages of Static Data Structures:

• The size and structure of static data structures are fixed, which can lead to inefficient memory usage if the data requirements change.
• Static data structures have a predefined size, limiting their ability to handle large and varying amounts of data.
• If the data size is smaller than the allocated memory, the unused memory is wasted.
• Expanding the size of a static data structure requires complex procedures, such as creating a new, larger structure and copying the data.

Examples of Static Data Structures:

Array : An array is a collection of elements identified by index or key values. The size of the array is specified at the time of creation and remains constant. For example, an array of integers can be declared as int arr[8]; in C++, which creates an array of size 8.

Note: Problem with above Array implementation: Once we create the Array we cannot alter the size of the array. So the size of the array is unalterable

Implementation:

#include <iostream>
using namespace std;

int main()
{
    // Declaration of an array of size 6
    int array[6];

    // initialize and printing values of array elements
    for (int i = 0; i < 6; i++) {
        array[i] = i;
        cout << array[i] << " ";
    }
    cout << endl;

    return 0;
}

public class Main {
    public static void main(String[] args)
    {
        // Declaration of an array of size 6
        int[] array = new int[6];

        // initialize and printing values of array elements
        for (int i = 0; i < 6; i++) {
            array[i] = i;
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

def main():
    # Declaration of a list of size 6
    array = [0] * 6

    # initialize and printing values of array elements
    for i in range(6):
        array[i] = i
        print(array[i], end=" ")
    print()


if __name__ == "__main__":
    main()

function main() {
    // Declaration of an array of size 6
    let array = new Array(6);

    // Initialize and print values of array elements
    for (let i = 0; i < 6; i++) {
        array[i] = i;
        process.stdout.write(array[i] + " ");
    }
    console.log();
}

// Call the main function to execute the code
main();

0 1 2 3 4 5 

In the above code: we declared an array of the fixed size. After that, we initialize some value using a loop and printed them.

What is Dynamic Data Structure?

Dynamic data structures are flexible in size and can grow or shrink as needed during program execution. This adaptability makes them suitable for handling data of varying sizes or when the size is unknown beforehand. Examples of dynamic data structures include linked lists, stacks, queues, and trees.

Features of Dynamic Data Structures:

There are many features of dynamic data structures. Let’s discuss the most popular of them:

• Dynamic Memory Allocation: Dynamic data structures allocate memory at runtime, rather than being pre-allocated at compile-time. This memory is stored in the program’s heap.
• Flexible Memory Usage: Unlike static data structures, the memory used by dynamic data structures is not limited to a fixed size. It can expand or contract as needed during program execution.
• Manual Memory Management: The memory allocated to dynamic data structures does not automatically deallocate when the structure goes out of scope. The programmer is responsible for manually deallocating this memory, often using functions like free() or delete(), to avoid memory leaks.
• Non-Contiguous Memory: The memory locations used by dynamic data structures are not guaranteed to be contiguous. This means additional metadata must be stored to track the locations of each element within the data structure.

Advantages of Dynamic Data Structures:

• Dynamic data structures can grow or shrink in size as needed, allowing for efficient use of memory.
• They can allocate and deallocate memory dynamically, preventing wastage of memory.
• Dynamic data structures can handle large and varying amounts of data without pre-defining the size.
• They provide a simpler programming interface compared to static data structures.

Disadvantages of Dynamic Data Structures:

• Dynamic memory allocation and deallocation can incur additional overhead compared to static data structures.
• Dynamic data structures can be more complex to implement and maintain than static data structures.
• Improper handling of dynamic memory can lead to memory leaks, which can cause performance issues.
• The performance of dynamic data structures can be less predictable than static data structures, especially in real-time systems.

Examples of Dynamic Data Structures:

Linked List : Linked Lists are linear data structures where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays.

Implementation:

#include <iostream>
using namespace std;

// defining a linked list
class LinkedList {
public:
    int data;
    LinkedList* next;
};

int main()
{
    // creating a linked list
    class LinkedList* node1 = new LinkedList();
    node1->data = 1;

    class LinkedList* node2 = new LinkedList();
    node2->data = 2;

    class LinkedList* node3 = new LinkedList();
    node3->data = 3;

    // linking all the nodes

    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;

    // printing value of linked list
    cout << node1->data << " " << node2->data << " "
         << node3->data << endl;

    return 0;
}

public class LinkedList {
    int data;
    LinkedList next;

    public static void main(String[] args)
    {
        // creating a linked list
        LinkedList node1 = new LinkedList();
        node1.data = 1;

        LinkedList node2 = new LinkedList();
        node2.data = 2;

        LinkedList node3 = new LinkedList();
        node3.data = 3;

        // linking all the nodes
        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        // printing value of linked list
        System.out.println(node1.data + " " + node2.data
                           + " " + node3.data);
    }
}

// This code is contributed by Shivam

class LinkedList:
    def __init__(self):
        self.data = None
        self.next = None


# creating a linked list
node1 = LinkedList()
node1.data = 1

node2 = LinkedList()
node2.data = 2

node3 = LinkedList()
node3.data = 3

# linking all the nodes
node1.next = node2
node2.next = node3
node3.next = None

# printing value of linked list
print(node1.data, node2.data, node3.data)

# This code is contributed by shivam

class LinkedList {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

function main() {
    // creating a linked list
    let node1 = new LinkedList(1);
    let node2 = new LinkedList(2);
    let node3 = new LinkedList(3);

    // linking all the nodes
    node1.next = node2;
    node2.next = node3;
    node3.next = null;

    // printing value of linked list
    let currentNode = node1;
    let output = "";
    while (currentNode !== null) {
        output += currentNode.data + " ";
        currentNode = currentNode.next;
    }
    console.log(output.trim());
}

main();

1 2 3

In the above code: A class LinkedList is defined with two members: data (an integer) and next (a pointer to the next node) and three nodes (node1, node2, node3) are created with data values of 1, 2, and 3 respectively. These nodes are then linked together to form a linked list: node1 points to node2, node2 points to node3, and node3 points to NULL, indicating the end of the list. Finally, the data values of the nodes are printed out, resulting in the output 1 2 3.

Difference between Static and Dynamic Data Structure:

Below are the comparison of static and dynamic data structure: