Implementation of Main Data Structures: Part 1

In my previous article on Big O Notation, I explored how time and space complexity can be evaluated using practical code examples. Now, let's deepen our understanding of Big O applied to the main data structures. You can find all code examples in my repository.

Array

An array is an ordered data structure that can store elements of any type. When we create an array in a programming language, the system allocates a contiguous block of memory for it and associates a variable with its initial address. Each element of the array occupies a fixed amount of memory.

There are two main types of arrays: static and dynamic.

Static Array:

Static arrays have a fixed size defined at creation time and cannot be resized later. This type of array is efficient in terms of memory usage and accessing elements, but it can be inflexible when we need to add or remove elements frequently.

Example Code:

public class StaticArray
{
    public int Search(int[] arr, int length, int target)
    {
        for (int i = 0; i < length; i++)
        {
            if (arr[i] == target)
            {
                return i;
            }
        }

        return -1;
    }

    public void InsertEnd(int[] arr, int n, ref int length, int capacity)
    {
        if (length < capacity)
        {
            arr[length] = n;
            length++;
        }
    }

    public void RemoveEnd(int[] arr, ref int length)
    {
        if (length > 0)
        {
            arr[length - 1] = 0;
            length--;
        }
    }

    public void InsertMiddle(int[] arr, int i, int n, ref int length)
    {
        for (int index = length - 1; index >= i; index--)
        {
            arr[index + 1] = arr[index];
        }

        arr[i] = n;
        length++;
    }

    public void RemoveMiddle(int[] arr, int i, ref int length)
    {
        for (int index = i + 1; index < length; index++)
        {
            arr[index - 1] = arr[index];
        }

        arr[length - 1] = 0;
        length--;
    }
 
}

Dynamic Array:

A dynamic array is a data structure that allows storing elements contiguously in memory, similar to a conventional array, but with the ability to grow or shrink in size during program execution. This is possible because a dynamic array manages the allocated memory space automatically: when it needs more space, a new memory area is allocated, usually larger than the previous one, and the elements are copied there. This flexibility makes dynamic arrays very useful in situations where the number of elements can vary over time, allowing efficient use of memory resources according to the program's needs.

Example Code:

public class DynamicArray
{
    private int[] arr;
    private int length;
    private int capacity;

    public DynamicArray()
    {
        capacity = 2;
        length = 0;
        arr = new int[capacity];
    }

    public int Length
    {
        get { return length; }
    }

    public void PushBack(int n)
    {
        if (length == capacity)
        {
            Resize();
        }

        arr[length] = n;
        length++;
    }

    private void Resize()
    {
        capacity = 2 * capacity;

        int[] newArr = new int[capacity];

        for (int i = 0; i < length; i++)
        {
            newArr[i] = arr[i];
        }

        arr = newArr;
    }

    public void PopBack()
    {
        if (length > 0)
        {
            length--;
        }
    }

    public int Get(int i)
    {
        if (i < length)
        {
            return arr[i];
        }

        throw new IndexOutOfRangeException();
    }

    public void Insert(int i, int n)
    {
        if (i < 0 || i > length)
        {
            throw new IndexOutOfRangeException();
        }

        if (length == capacity)
        {
            Resize();
        }

        for (int j = length - 1; j >= i; j--)
        {
            arr[j + 1] = arr[j];
        }

        arr[i] = n;
        length++;
    }

    public void RemoveAt(int i)
    {
        if (i < 0 || i >= length)
        {
            throw new IndexOutOfRangeException();
        }

        for (int j = i; j < length - 1; j++)
        {
            arr[j] = arr[j + 1];
        }

        length--;
    }

    public int Search(int n)
    {
        for (int i = 0; i < length; i++)
        {
            if (arr[i] == n)
            {
                return i;
            }
        }

        return -1;
    }
}

Big O Explanation:

In the context of arrays, both static and dynamic, direct access to elements is facilitated by contiguous memory allocation. This means that each element of the array is stored in consecutive memory positions, allowing any element to be accessed directly by its index in constant time, O(1).

On the other hand, operations that involve searching for a specific element in the array, such as finding the index of a number, require traversing the array until the desired element is found. In an unordered array, this typically involves checking each element sequentially, resulting in linear time complexity, O(n), where n is the number of elements in the array.

For insertion and removal operations:

• Insertion/removal at the end of the array: These operations are efficient with complexity O(1), as they only affect the last element of the array and do not require shifting of elements.
• Insertion/removal at a specific position or at the beginning: These operations have a complexity of O(n), because they require shifting elements to make space or adjust the array structure.

In the case of dynamic arrays:

• Array expansion: When a dynamic array reaches its maximum capacity and needs to grow to accommodate new elements, it typically reallocates a new memory area with greater space. This process involves copying the elements from the old array to the new memory area, resulting in linear time complexity relative to the current number of elements in the array, i.e., O(n).

Single Linked-List

A linked list is a data structure that organizes elements in a sequence in the computer's RAM. Each element of this sequence, called a node, consists of two main components: the data to be stored and a pointer that indicates the next node in the sequence.

Unlike structures like arrays, where elements are stored contiguously in memory, the nodes of a linked list can be scattered throughout memory, connected only by pointers. This means that each node can reside anywhere in memory, allowing the linked list to grow dynamically as new elements are added.

In addition to the pointers in each node, a linked list typically maintains special pointers called head and tail. The head pointer points to the first node of the list, while the tail pointer points to the last node of the list. These pointers are crucial for efficient operations of inserting and removing elements at the beginning and end of the list.

Example Code:

public class ListNode
{
    public int val;      
    public ListNode? next;   

    public ListNode(int val = 0, ListNode? next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class LinkedList
{
    private ListNode head;
    private ListNode tail;

    public LinkedList()
    {
        head = new ListNode(-1);
        tail = head;
    }

    public bool IsEmpty()
    {
        return head.next == null;
    }

    public void InsertBeginning(int val)
    {
        ListNode newNode = new ListNode(val);

        newNode.next = head.next;
        head.next = newNode;

        if (tail == head)
        {
            tail = newNode;
        }
    }

    public void InsertEnd(int val)
    {
        tail.next = new ListNode(val);
        tail = tail.next;
    }

    public void RemoveBeginning()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("The list is empty. Unable to remove elements.");
        }

        head.next = head.next.next;

        if (head.next == null)
        {
            tail = head;
        }
    }

    public void RemoveEnd()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("The list is empty. Unable to remove elements.");
        }

        ListNode curr = head;

        while (curr.next != tail)
        {
            curr = curr.next;
        }

        curr.next = null;
        tail = curr;
    }

    public void Remove(int index)
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("The list is empty. Unable to remove elements.");
        }

        if (index < 0)
        {
            throw new IndexOutOfRangeException("Index cannot be negative.");
        }

        int i = 0;
        ListNode curr = head;

        while (i < index && curr.next != null)
        {
            i++;
            curr = curr.next;
        }

        if (curr.next != null)
        {
            curr.next = curr.next.next;

            if (curr.next == null)
            {
                tail = curr;
            }
        }
        else
        {
            throw new IndexOutOfRangeException("Index out of bounds. Nothing was removed.");
        }
    }
}

Big O Explanation:

In the context of linked lists, checking if the list is empty simply involves verifying if the head.next pointer is null. This check is done in constant time, O(1), as it requires only a simple pointer check.

Insertion and Removal:

• Insertion at the Beginning: To insert a new element at the beginning of the list, you just need to create a new node and adjust the pointers so that the new node becomes the first in the list. This operation is efficient, with a complexity of O(1), since it doesn't require traversing the list.
• Insertion at the End: By using a tail pointer that points to the last node in the list, it's possible to insert a new element at the end in constant time, O(1). This involves creating a new node, adjusting the pointer of the last node to point to the new node, and then updating the tail pointer to point to the new node.
• Removal from the Beginning: Removing the first element from the list is also a constant time operation, O(1), as it involves simply adjusting the head pointer to point to the second node in the list. If the list becomes empty after the removal, the tail pointer is also adjusted to point to head.
• Removal from the End: To remove the last element from a linked list, you need to traverse the list to the second-to-last node, resulting in a linear time complexity, O(n), where n is the number of elements in the list. This is necessary to find the node whose next pointer points to the last node, so that you can adjust this next pointer to null and update the tail pointer to point to the second-to-last node.
• Removal by Index: Removing a node at a specific position also involves traversing the list to the desired node, resulting in a linear time complexity, O(n). This is necessary to adjust the pointers of the node before the node to be removed to point to the node after the node to be removed.

Stacks

A stack is a data structure that follows the "last in, first out" (LIFO) concept. This means that the most recently added item to the collection will be the first one to be removed, regardless of how many items it contains.

You can visualize this in the real world with a "stack" of documents on a desk. When you add a new document, you place it on top of the stack. If you need a specific document, you start at the top, removing the most recent documents first.

There are two common implementations of stacks: using arrays and linked lists.

Example of a Stack with Array:

public class Stack<T>
{
    private T[] stack;
    private int top = 0;
    private const int DefaultCapacity = 5;

    public Stack(int initialCapacity = DefaultCapacity)
    {
        stack = new T[initialCapacity];
    }

    public bool IsEmpty()
    {
        return top == 0;
    }

    public void Push(T element)
    {
        if (top == stack.Length)
        {
            T[] newStack = new T[stack.Length * 2];

            for (int i = 0; i < stack.Length; i++)
            {
                newStack[i] = stack[i];
            }

            stack = newStack;
        }

        stack[top] = element;
        top++;
    }

    public T Pop()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Stack Underflow");
        }
        else
        {
            top--;
            T element = stack[top];
            stack[top] = default;

            return element;
        }
    }
}

Example of a Stack with Linked List:

public class Node<T>
{
    public T Element { get; set; }
    public Node<T> Next { get; set; }

    public Node(T element, Node<T> next)
    {
        Element = element;
        Next = next;
    }
}

public class Stack<T>
{
    private Node<T> top;
    private int size = 0;

    public int Size => size;

    public bool IsEmpty()
    {
        return top == null;
    }

    public void Push(T element)
    {
        Node<T> node = new(element, top);
        top = node;
        size++;
    }

    public T Pop()
    {
        if (IsEmpty())
            throw new Exception("Stack Underflow");
        else
        {
            var temp = top.Element;
            top = top.Next;
            size--;

            return temp;
        }
    }
}

Big O Explanation:

• IsEmpty(): Both implementations check a simple condition (top == 0 or top == null), so they operate in constant time, O(1).
• Push(T element): In the array implementation, if the stack is full and needs to be resized, the operation is O(n), where n is the number of elements in the current stack. This is because all elements need to be copied to a new array with double the original size. In the linked list implementation, the operation is always O(1) because there is no need to reallocate elements.
• Pop(): Both implementations have constant time, O(1), for the removal operation. They check if the stack is empty, and if not, remove or unlink the top element, which is a simple operation independent of the stack size.

Conclusion

The analysis of time complexity (Big O) in data structure operations allows us to understand their efficiencies and limitations. Each structure, such as static arrays, dynamic arrays, linked lists, and stacks, offers specific advantages depending on the type of operation performed. This understanding is crucial for selecting the most appropriate structure according to the specific needs of each application.