1. Using Delimiters or Separators
In this approach, elements of all the lists are stored sequentially in the array, and a special marker (or delimiter) is used to indicate the boundary between different lists.
Example:
Consider three lists:
• L1 = [10, 20]
• L2 = [30, 40, 50]
• L3 = [60]
We store all these lists in a single array and use a special marker like -1 to separate the lists.
Array: [10, 20, -1, 30, 40, 50, -1, 60, -1]
Here, -1 acts as the delimiter that separates the individual lists.
Advantages:
• Easy to implement.
• Efficient in memory usage since all elements are stored in a single array.
Disadvantages:
• Searching or accessing individual lists requires traversing the array to find the delimiters, which can be inefficient.
• Deletion or insertion of elements may require shifting elements and adjusting delimiters.
2. Using an Index Table
In this method, you store the elements of all lists in a single array, but use a separate table (another array) to keep track of the starting index of each list.
Example:
Consider three lists:
• L1 = [10, 20]
• L2 = [30, 40, 50]
• L3 = [60]
Store the elements in a single array:
Array: [10, 20, 30, 40, 50, 60]
Use another array (index table) to store the starting index of each list:
less
Copy code
Index Table: [0, 2, 5]
• L1 starts at index 0, so its elements are 10, 20.
• L2 starts at index 2, so its elements are 30, 40, 50.
• L3 starts at index 5, so its element is 60.
Advantages:
• Efficient access to each list by directly referring to the index table.
• No need for delimiters, making traversal faster.
Disadvantages:
• The index table adds some extra overhead in memory, though it's relatively small compared to the size of the array.
• Managing the starting indices requires care when lists grow or shrink.
3. Fixed-Size Blocks
Another approach is to divide the array into fixed-size blocks, with each block allocated for a specific list. This method is less flexible because each list is limited to a predefined size.
Example:
Assume you want to store three lists with a maximum of 3 elements each.
Allocate a single array for the lists:
Array: [10, 20, -1, 30, 40, 50, -1, 60, -1, -1]
Each list occupies a fixed range in the array:
• L1: [10, 20, -1] (where -1 is padding).
• L2: [30, 40, 50].
• L3: [60, -1, -1] (where -1 is padding).
Advantages:
• Simple and straightforward to implement.
• Accessing elements is efficient because the starting point for each list is fixed.
Disadvantages:
• Wastes memory if the lists don't fully use their allocated space.
• It does not work well if lists are highly dynamic in size.
Summary:
Multiple lists in a single array is a technique used to store several lists efficiently in a single memory block. You can implement it using delimiters, index tables, or fixed-size blocks, each with its own trade-offs in terms of memory efficiency, access speed, and ease of management. The choice of method depends on the application’s requirements, such as whether lists are fixed or dynamic in size and the performance trade-offs, you are willing to make.