1. Contiguous Memory (Arrays)

• An array is stored in contiguous (continuous) memory locations.
  • Example: If an array starts at memory address 1000 and each element takes 4 bytes, then:
    • element[0] → 1000
    • element[1] → 1004
    • element[2] → 1008
    • … and so on.
• This makes it easy to access any element directly using the index (because we can calculate the memory address using a formula).
  • Access time = O(1) (direct indexing).
• Problem: Insertion and deletion are costly because shifting elements may be required.
• Memory limitation: Needs a fixed size (or resizing causes overhead).

2. Non-Contiguous Memory (Linked List)

• A linked list does not require contiguous memory.
  • Each element (called a node) has:
    • Data (the actual value)
    • A pointer/reference to the next node’s address
• Example of memory layout:
  • Node1 (at address 5000) → Data: 10, Next: 7000
  • Node2 (at address 7000) → Data: 20, Next: 3000
  • Node3 (at address 3000) → Data: 30, Next: NULL
• As you can see, nodes are scattered in memory, but connected via pointers.
• Advantages:
  • Easy to insert or delete nodes (just change pointers).
  • Dynamic size (no need to know size in advance).
• Disadvantages:
  • Accessing an element requires traversal from the head (no direct indexing).
  • Extra memory for storing pointers.