Arrays in DSA

الـ Array هو عبارة عن مجموعة من البيانات المتجاورة (continues block of data) واللي بتتخزن بنفس الشكل في الـ RAM.

Storing arrays in RAM

• كل قيمة فردية في الـ Array (زي الـ int) بتتخزن في 4 bytes (يعني 32 bit). فمثلًا رقم 1 هيتخزن على شكل 00...1.
• الـ RAM بتتكون من حاجتين أساسيتين: القيمة (Value) والعنوان (Address) بتاعها.

Static Arrays

Reading Data from an Array

• العملية دي بتاخد وقت Big O(1)، يعني وقت ثابت (constant time).
• لما بنحتاج نقرأ أي عنصر من الـ Array، إحنا بنوصله عن طريق العنوان بتاعه، والبرنامج بيروح للـ RAM ويجيب القيمة اللي في العنوان ده.
• في الحقيقة، إحنا مش بنستخدم العنوان بشكل مباشر، لكن بنستخدم حاجة اسمها الـ index، وده بيمثل ترتيب العنصر في الـ Array وبيبدأ من 0.
• فلو عايزين نوصل لأول عنصر، هنستخدم index = 0.
• نقدر نوصل لكل البيانات اللي في الـ Array باستخدام for أو while loops.

Writing Data to an Array (Fixed)

• العملية دي كمان بتاخد وقت Big O(1).
• الـ Arrays ليها نوعين أساسيين: ثابتة (Fixed) وديناميكية (Dynamic).
• في الـ Fixed Array، مش بنقدر نضيف عناصر جديدة بعد ما نحدد حجمها، لإننا مش بنبقى عارفين إذا كان المكان اللي بعد الـ Array في الـ RAM فاضي ولا لأ.
• وكمان مش بنقدر نضيف قيمة في أي عنوان فاضي وخلاص، لازم تكون الإضافة بعد آخر عنصر موجود في الـ Array.

Remove a value at the end

• لما بنتكلم عن مسح عنصر في Static Array، فالمقصود مش إننا بنعمله deallocate من الذاكرة، لإن ده مستحيل يحصل في النوع ده.
• المعنى الحقيقي هو إننا بنعمل overriding للقيمة دي، يعني بنكتب فوقيها قيمة تانية، زي صفر مثلًا، وبنعتبر المكان ده مش مهم بالنسبة لنا بعد كده.
• العملية دي بتاخد Big O(1)، لإن كل اللي بنعمله هو عملية كتابة، وزي ما قلنا، الكتابة بتاخد وقت ثابت.

Insert value at the beginning or at middle

• إضافة عنصر في أول أو نص الـ Array عملية مش فعّالة (not efficient) زي الإضافة في الآخر.
• ده لإنك هتحتاج تعمل shift أو إزاحة لكل العناصر اللي بعد المكان اللي هتضيف فيه.
• الأول هتحرك كل العناصر اللي بعد المكان المطلوب خطوة لقدام (بتبدأ من الآخر للأول)، وبعدين تحط القيمة الجديدة في مكانها.
• العملية دي بتاخد وقت Big O(n)، لإن عدد عمليات الـ shift بيعتمد على عدد العناصر n.
• نفس المشكلة دي بتواجهنا لو جينا نحذف أي عنصر من أول أو نص الـ Array.

sequenceDiagram
    participant User
    participant Array
    
    User->>Array: Insert value 'X' at index 1
    Note right of Array: Array: [A, B, C, D]
    Array->>Array: Shift 'D' to index 4
    Note right of Array: Array: [A, B, C, _, D]
    Array->>Array: Shift 'C' to index 3
    Note right of Array: Array: [A, B, _, C, D]
    Array->>Array: Shift 'B' to index 2
    Note right of Array: Array: [A, _, B, C, D]
    Array->>Array: Place 'X' at index 1
    Note right of Array: Final Array: [A, X, B, C, D]

Multi Column

Summary

Operation	Time Complexity
Read	O(1)
Search	O(n)
Insert (at end)	O(1)
Insert (at middle)	O(n)
Delete (at end)	O(1)
Delete (at middle)	O(n)

Code

Python

# Insert n into arr at the next open position.
# Length is the number of 'real' values in arr, and capacity
# is the size (aka memory allocated for the fixed size array).
def insertEnd(arr, n, length, capacity):
    if length < capacity:
        arr[length] = n
 
# Remove from the last position in the array if the array
# is not empty (i.e. length is non-zero).
def removeEnd(arr, length):
    if length > 0:
        # Overwrite last element with some default value.
        # We would also decrease the length by 1.
        arr[length - 1] = 0
 
# Insert n into index i after shifting elements to the right.
# Assuming i is a valid index and arr is not full.
def insertMiddle(arr, i, n, length):
    # Shift starting from the end to i.
    for index in range(length - 1, i - 1, -1):
        arr[index + 1] = arr[index]
    # Insert at i
    arr[i] = n
 
# Remove value at index i before shifting elements to the left.
# Assuming i is a valid index.
def removeMiddle(arr, i, length):
    # Shift starting from i + 1 to end.
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]
    # No need to 'remove' arr[length - 1], it's now a duplicate but outside the new length.

C#

public static class StaticArrayOps
{
    // Insert n into arr at the next open position.
    // 'length' is the logical size, passed by reference to be modified.
    public static void InsertEnd(int[] arr, int n, ref int length)
    {
        // arr.Length is the physical capacity
        if (length < arr.Length)
        {
            arr[length] = n;
            length++; // Increment the logical length
        }
    }
 
    // Remove from the last logical position.
    public static void RemoveEnd(ref int length)
    {
        if (length > 0)
        {
            // Just decrement the logical length. The old value is ignored.
            length--;
        }
    }
    
    // Insert n at index i. Assumes there is capacity.
    public static void InsertMiddle(int[] arr, int i, int n, ref int length)
    {
        // Shift elements to the right, from the end towards i
        for (int index = length - 1; index >= i; index--)
        {
            arr[index + 1] = arr[index];
        }
        // Insert at i
        arr[i] = n;
        length++; // Increment logical length
    }
 
    // Remove value at index i.
    public static void RemoveMiddle(int[] arr, int i, ref int length)
    {
        // Shift elements to the left, from i+1 to the end
        for (int index = i; index < length - 1; index++)
        {
            arr[index] = arr[index + 1];
        }
        // Decrement logical length
        length--;
    }
}

Dynamic Arrays

لغات زي JavaScript و Python كل الـ Arrays فيها Dynamic بشكل افتراضي. في C# بنستخدم List<T>.

• الـ Dynamic Arrays حجمها بيتغير، وبنقدر نزود ونضيف فيها عناصر زي ما إحنا عايزين.
• بيكون فيها حاجة زي Pointer بيشاور على آخر index إحنا ضيفناه.

Push

• عملية الـ push هي إضافة قيمة جديدة في آخر الـ Array.
• بتاخد وقت O(1)، وده بفضل وجود الـ Pointer اللي بيعرفنا آخر مكان فاضي فين.
• في البداية، الـ Array بيكون ليها Capacity معينة (سعة تخزينية)، حتى لو كانت Dynamic.
• طيب لو الـ Array اتملت على آخرها وحاولنا نعمل push لعنصر جديد، إيه اللي بيحصل؟
  1. بيتم إنشاء Array جديدة خالص بـ Capacity ضعف القديمة.
  2. بيتم نسخ كل العناصر من الـ Array القديمة للجديدة.
  3. بيتم مسح الـ Array القديمة (deallocate) عشان نفضي مساحتها من الذاكرة.
• عملية تغيير الحجم دي بتاخد وقت O(n)، لإنشاء Array جديدة ونسخ n من العناصر بياخد وقت متناسب مع عددهم. لكن عملية الـ push نفسها لو مفيش تغيير حجم بتاخد O(1).
• عشان نتجنب التكلفة دي كل مرة، إحنا بنضاعف الـ Capacity ومش بنزودها بمقدار واحد بس، وفي نفس الوقت مش بنزودها زيادة عن اللزوم عشان منستهلكش مساحة كبيرة من الذاكرة على الفاضي.
• العملية دي بنسميها Amortized Analysis، وبسببها بنقدر نعتبر إن تكلفة الـ push في المجمل هي O(1).

graph TD
    A["Array (Capacity: 4, Length: 4)"] -->|Push 'E'| B{Length == Capacity?};
    B -->|Yes| C["Create New Array (Capacity: 8)"];
    C --> D[Copy A, B, C, D to New Array];
    D --> E[Deallocate Old Array];
    E --> F[Add 'E' to New Array];
    B -->|No| G[Add element directly];

Pop

• عملية مسح آخر عنصر في الـ Array.
• بتاخد وقت O(1).

Summary

نفس الـ Static Arrays مع الأخذ في الاعتبار إن الـ Insert (at end) تكلفتها O(1) بشكل amortized.

Operation	Time Complexity
Read	O(1)
Search	O(n)
Insert (at end)	O(1) Amortized
Insert (at middle)	O(n)
Delete (at end)	O(1)
Delete (at middle)	O(n)

Code

Python

# Python lists are dynamic by default, but this is an example of resizing.
class Array:
    def __init__(self):
        self.capacity = 2
        self.length = 0
        self.arr = [0] * 2 # Array of capacity = 2
 
    # Insert n in the last position of the array
    def pushback(self, n):
        if self.length == self.capacity:
            self.resize()
        # insert at next empty position
        self.arr[self.length] = n
        self.length += 1
 
    def resize(self):
        # Create new array of double capacity
        self.capacity *= 2
        newArr = [0] * self.capacity
        # Copy elements to newArr
        for i in range(self.length):
            newArr[i] = self.arr[i]
        self.arr = newArr
        
    # Remove the last element in the array
    def popback(self):
        if self.length > 0:
            self.length -= 1
    
    # Get value at i-th index
    def get(self, i):
        if i < self.length:
            return self.arr[i]
        # Here we would throw an out of bounds exception
 
    # Insert n at i-th index
    def insert(self, i, n):
        if i < self.length:
            self.arr[i] = n
            return
        # Here we would throw an out of bounds exception       

C#

// C# has List<T> for dynamic arrays, but this class mimics the behavior.
public class DynamicArray
{
    private int[] arr;
    private int capacity;
    private int length;
 
    public DynamicArray()
    {
        this.capacity = 2;
        this.length = 0;
        this.arr = new int[this.capacity];
    }
 
    // Insert n in the last position of the array
    public void Pushback(int n)
    {
        if (this.length == this.capacity)
        {
            Resize();
        }
        // Insert at next empty position
        this.arr[this.length] = n;
        this.length++;
    }
 
    private void Resize()
    {
        // Create new array of double capacity
        this.capacity *= 2;
        int[] newArr = new int[this.capacity];
        // Copy elements to newArr
        for (int i = 0; i < this.length; i++)
        {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }
 
    // Remove the last element in the array
    public void Popback()
    {
        if (this.length > 0)
        {
            this.length--;
        }
    }
 
    // Get value at i-th index
    public int Get(int i)
    {
        if (i < this.length && i >= 0)
        {
            return this.arr[i];
        }
        // Throw an out of bounds exception if index is invalid
        throw new IndexOutOfRangeException();
    }
 
    // Overwrite value at i-th index
    public void Set(int i, int n)
    {
        if (i < this.length && i >= 0)
        {
            this.arr[i] = n;
            return;
        }
        // Throw an out of bounds exception if index is invalid
        throw new IndexOutOfRangeException();
    }
}