Inefficient Data Structures

// Anti-pattern: Using ArrayList for frequent insertions at arbitrary positions
public void processTasksInefficiently(List<Task> tasks) {
    List<Task> processingQueue = new ArrayList<>();
    
    // Fill the queue initially
    processingQueue.addAll(tasks);
    
    while (!processingQueue.isEmpty()) {
        // Remove from the beginning (causes shifting of all elements)
        Task task = processingQueue.remove(0);
        processTask(task);
        
        // Add new tasks at arbitrary positions
        if (task.hasHighPriority()) {
            // Insert at the beginning (causes shifting of all elements)
            processingQueue.add(0, createFollowUpTask(task));
        } else {
            // Add somewhere in the middle based on priority
            int insertPosition = findInsertPosition(processingQueue, task.getPriority());
            processingQueue.add(insertPosition, createFollowUpTask(task));
        }
    }
}

// Better approach: Using LinkedList for frequent insertions/deletions
public void processTasksEfficiently(List<Task> tasks) {
    LinkedList<Task> processingQueue = new LinkedList<>();
    
    // Fill the queue initially
    processingQueue.addAll(tasks);
    
    while (!processingQueue.isEmpty()) {
        // Remove from the beginning (O(1) operation for LinkedList)
        Task task = processingQueue.removeFirst();
        processTask(task);
        
        // Add new tasks at appropriate positions
        if (task.hasHighPriority()) {
            // Insert at the beginning (O(1) operation for LinkedList)
            processingQueue.addFirst(createFollowUpTask(task));
        } else {
            // For arbitrary insertions, LinkedList is still more efficient
            // though still O(n) to find the position
            int insertPosition = findInsertPosition(processingQueue, task.getPriority());
            
            // Use a ListIterator to avoid traversing the list twice
            ListIterator<Task> iterator = processingQueue.listIterator();
            for (int i = 0; i < insertPosition; i++) {
                iterator.next();
            }
            iterator.add(createFollowUpTask(task));
        }
    }
}

// Anti-pattern: Using array for frequent insertions/deletions
function processTasksInefficiently(tasks) {
  const processingQueue = [...tasks];
  
  while (processingQueue.length > 0) {
    // Remove from the beginning (causes shifting of all elements)
    const task = processingQueue.shift();
    processTask(task);
    
    // Add new tasks at arbitrary positions
    if (task.hasHighPriority) {
      // Insert at the beginning (causes shifting of all elements)
      processingQueue.unshift(createFollowUpTask(task));
    } else {
      // Add somewhere in the middle based on priority
      const insertPosition = findInsertPosition(processingQueue, task.priority);
      processingQueue.splice(insertPosition, 0, createFollowUpTask(task));
    }
  }
}

// Better approach: Using a more appropriate data structure
function processTasksEfficiently(tasks) {
  // For JavaScript, we can use a custom doubly-linked list implementation
  // or a library that provides one
  const processingQueue = new DoublyLinkedList();
  
  // Fill the queue initially
  for (const task of tasks) {
    processingQueue.append(task);
  }
  
  while (!processingQueue.isEmpty()) {
    // Remove from the beginning (O(1) operation)
    const task = processingQueue.removeFirst();
    processTask(task);
    
    // Add new tasks at appropriate positions
    if (task.hasHighPriority) {
      processingQueue.prepend(createFollowUpTask(task));
    } else {
      // For a more efficient implementation, consider using a priority queue
      // instead of finding insert positions manually
      const newTask = createFollowUpTask(task);
      processingQueue.insertAt(findInsertPosition(processingQueue, task.priority), newTask);
    }
  }
}

// Anti-pattern: HashMap with poor hash function
public class BadKey {
    private int id;
    
    public BadKey(int id) {
        this.id = id;
    }
    
    // Poor hash function that causes many collisions
    @Override
    public int hashCode() {
        return id % 10; // Only uses last digit, causing many collisions
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        BadKey other = (BadKey) obj;
        return id == other.id;
    }
}

// Usage that causes poor performance
Map<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put(new BadKey(i), "Value " + i);
}

// Better approach: Proper hash function
public class GoodKey {
    private int id;
    
    public GoodKey(int id) {
        this.id = id;
    }
    
    // Better hash function with good distribution
    @Override
    public int hashCode() {
        return Objects.hash(id); // Uses the entire id value
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        GoodKey other = (GoodKey) obj;
        return id == other.id;
    }
}

// Anti-pattern: Using objects as keys without proper consideration
function processUserData(users) {
  const userDataMap = {};
  
  for (const user of users) {
    // Using objects as keys without proper string conversion
    // JavaScript will convert these to '[object Object]'
    userDataMap[user] = calculateUserMetrics(user);
  }
  
  // This will likely not work as expected
  return userDataMap[someUser];
}

// Better approach: Using proper keys or Map object
function processUserDataEfficiently(users) {
  // Option 1: Using a unique identifier as key
  const userDataMap = {};
  
  for (const user of users) {
    userDataMap[user.id] = calculateUserMetrics(user);
  }
  
  return userDataMap[someUser.id];
  
  // Option 2: Using Map object which allows object keys
  const userMap = new Map();
  
  for (const user of users) {
    userMap.set(user, calculateUserMetrics(user));
  }
  
  return userMap.get(someUser);
}

// Anti-pattern: Inefficient collection iteration
public void processListInefficiently(List<String> items) {
    // Repeatedly checking size in each iteration
    for (int i = 0; i < items.size(); i++) {
        // Using get() on a LinkedList is O(n)
        String item = items.get(i);
        processItem(item);
    }
}

// Better approach: Efficient iteration
public void processListEfficiently(List<String> items) {
    // For ArrayList: Cache the size
    if (items instanceof ArrayList) {
        int size = items.size();
        for (int i = 0; i < size; i++) {
            String item = items.get(i);
            processItem(item);
        }
    } 
    // For LinkedList: Use iterator
    else if (items instanceof LinkedList) {
        for (String item : items) { // Uses Iterator internally
            processItem(item);
        }
    }
    // Generic approach that works well for both
    else {
        for (String item : items) {
            processItem(item);
        }
    }
}

// Anti-pattern: Inefficient array iteration
function processArrayInefficiently(items) {
  // Repeatedly checking length in each iteration
  for (let i = 0; i < items.length; i++) {
    processItem(items[i]);
  }
}

// Better approach: Efficient iteration
function processArrayEfficiently(items) {
  // Cache the length
  const length = items.length;
  for (let i = 0; i < length; i++) {
    processItem(items[i]);
  }
  
  // Or use forEach (though slightly less performant in some cases)
  items.forEach(item => processItem(item));
  
  // Or use for...of loop (good for most cases)
  for (const item of items) {
    processItem(item);
  }
}

// Anti-pattern: Using HashMap when insertion order matters
public void processOrdersInefficiently(List<Order> orders) {
    // HashMap doesn't maintain insertion order
    Map<String, Order> orderMap = new HashMap<>();
    
    for (Order order : orders) {
        orderMap.put(order.getId(), order);
    }
    
    // Iterating over entries (order not preserved)
    for (Map.Entry<String, Order> entry : orderMap.entrySet()) {
        processOrderInSequence(entry.getValue());
    }
}

// Better approach: Using the right Map implementation
public void processOrdersEfficiently(List<Order> orders) {
    // LinkedHashMap maintains insertion order
    Map<String, Order> orderMap = new LinkedHashMap<>();
    
    for (Order order : orders) {
        orderMap.put(order.getId(), order);
    }
    
    // Iterating over entries (insertion order preserved)
    for (Map.Entry<String, Order> entry : orderMap.entrySet()) {
        processOrderInSequence(entry.getValue());
    }
}

// Another example: Using TreeMap for sorted keys
public void displayOrdersSorted(List<Order> orders) {
    // TreeMap sorts entries by key
    Map<LocalDateTime, Order> orderMap = new TreeMap<>();
    
    for (Order order : orders) {
        orderMap.put(order.getCreatedAt(), order);
    }
    
    // Iterating over entries (sorted by creation time)
    for (Map.Entry<LocalDateTime, Order> entry : orderMap.entrySet()) {
        displayOrder(entry.getValue());
    }
}

// Anti-pattern: Using object when insertion order matters
function processOrdersInefficiently(orders) {
  // Regular objects don't guarantee property insertion order
  const orderMap = {};
  
  for (const order of orders) {
    orderMap[order.id] = order;
  }
  
  // Iterating over properties (order not guaranteed)
  for (const orderId in orderMap) {
    processOrderInSequence(orderMap[orderId]);
  }
}

// Better approach: Using Map to preserve insertion order
function processOrdersEfficiently(orders) {
  // Map preserves insertion order
  const orderMap = new Map();
  
  for (const order of orders) {
    orderMap.set(order.id, order);
  }
  
  // Iterating over entries (insertion order preserved)
  for (const [orderId, order] of orderMap.entries()) {
    processOrderInSequence(order);
  }
}

// Anti-pattern: Inefficient string concatenation
public String buildReportInefficiently(List<String> items) {
    String report = "";
    for (String item : items) {
        // Creates a new String object in each iteration
        report = report + item + "\n";
    }
    return report;
}

// Better approach: Using StringBuilder
public String buildReportEfficiently(List<String> items) {
    // Preallocate capacity for better performance
    StringBuilder reportBuilder = new StringBuilder(items.size() * 20); // Assuming average item length
    for (String item : items) {
        reportBuilder.append(item).append("\n");
    }
    return reportBuilder.toString();
}

// Anti-pattern: Inefficient string concatenation
function buildReportInefficiently(items) {
  let report = '';
  for (let i = 0; i < items.length; i++) {
    // Creates a new string in each iteration
    report = report + items[i] + '\n';
  }
  return report;
}

// Better approach: Using array join
function buildReportEfficiently(items) {
  // Create array and join at the end (much more efficient)
  return items.join('\n') + '\n';
  
  // Alternative approach for more complex concatenation
  const parts = [];
  for (let i = 0; i < items.length; i++) {
    parts.push(items[i]);
  }
  return parts.join('\n') + '\n';
}

// Anti-pattern: Excessive boxing and unboxing
public int sumValuesInefficiently(List<Integer> values) {
    int sum = 0;
    for (int i = 0; i < values.size(); i++) {
        // Auto-unboxing Integer to int in each iteration
        sum += values.get(i);
    }
    return sum;
}

// Better approach: Using primitive collections
public int sumValuesEfficiently(List<Integer> values) {
    // Option 1: Minimize unboxing operations
    int sum = 0;
    for (Integer value : values) {
        // Still unboxes, but at least avoids repeated get() calls
        sum += value;
    }
    return sum;
    
    // Option 2: Using streams with specialized sum operation
    return values.stream().mapToInt(Integer::intValue).sum();
    
    // Option 3: Using specialized primitive collections library
    // (e.g., Trove, Fastutil, Eclipse Collections)
    TIntList primitiveList = new TIntArrayList(values.size());
    for (Integer value : values) {
        primitiveList.add(value);
    }
    return primitiveList.sum();
}

// JavaScript doesn't have explicit boxing/unboxing,
// but there are similar performance concerns with type conversions

// Anti-pattern: Inefficient number parsing in a loop
function sumValuesInefficiently(values) {
  let sum = 0;
  for (let i = 0; i < values.length; i++) {
    // Repeatedly parsing strings to numbers
    sum += parseInt(values[i]);
  }
  return sum;
}

// Better approach: Convert once, then operate
function sumValuesEfficiently(values) {
  // Convert all strings to numbers first
  const numbers = values.map(value => parseInt(value));
  
  // Then sum the numbers
  let sum = 0;
  for (let i = 0; i < numbers.length; i++) {
    sum += numbers[i];
  }
  return sum;
  
  // Or more concisely with reduce
  return values.map(value => parseInt(value))
    .reduce((sum, num) => sum + num, 0);
}

// Anti-pattern: Inefficient set operations
public List<String> findCommonElementsInefficiently(List<String> list1, List<String> list2) {
    List<String> result = new ArrayList<>();
    
    // O(n²) operation - checking each element against the other list
    for (String item : list1) {
        if (list2.contains(item)) { // Linear search in list2
            result.add(item);
        }
    }
    
    return result;
}

// Better approach: Using Set for efficient lookups
public List<String> findCommonElementsEfficiently(List<String> list1, List<String> list2) {
    // Convert smaller list to Set for O(1) lookups
    Set<String> set;
    List<String> otherList;
    
    if (list1.size() <= list2.size()) {
        set = new HashSet<>(list1);
        otherList = list2;
    } else {
        set = new HashSet<>(list2);
        otherList = list1;
    }
    
    List<String> result = new ArrayList<>();
    
    // Now check membership with O(1) lookups
    for (String item : otherList) {
        if (set.contains(item)) { // Constant-time operation
            result.add(item);
        }
    }
    
    return result;
    
    // Even better: Using built-in set operations
    Set<String> set1 = new HashSet<>(list1);
    Set<String> set2 = new HashSet<>(list2);
    set1.retainAll(set2); // Intersection operation
    return new ArrayList<>(set1);
}

// Anti-pattern: Inefficient set operations
function findCommonElementsInefficiently(array1, array2) {
  const result = [];
  
  // O(n²) operation
  for (const item of array1) {
    if (array2.includes(item)) { // Linear search
      result.push(item);
    }
  }
  
  return result;
}

// Better approach: Using Set for efficient lookups
function findCommonElementsEfficiently(array1, array2) {
  // Convert smaller array to Set for O(1) lookups
  let set, otherArray;
  
  if (array1.length <= array2.length) {
    set = new Set(array1);
    otherArray = array2;
  } else {
    set = new Set(array2);
    otherArray = array1;
  }
  
  // Filter other array using the set
  return otherArray.filter(item => set.has(item));
}

// Even better: Using Set intersection
function findCommonElementsWithSetIntersection(array1, array2) {
  const set1 = new Set(array1);
  const set2 = new Set(array2);
  
  // Create intersection
  return [...new Set([...set1].filter(item => set2.has(item)))];
}

// Anti-pattern: Inefficient collection resizing
public List<String> buildLargeListInefficiently(int size) {
    // Default initial capacity is 10
    List<String> list = new ArrayList<>();
    
    // Will cause multiple resizing operations
    for (int i = 0; i < size; i++) {
        list.add("Item " + i);
    }
    
    return list;
}

// Better approach: Preallocating capacity
public List<String> buildLargeListEfficiently(int size) {
    // Preallocate with known capacity
    List<String> list = new ArrayList<>(size);
    
    // No resizing needed
    for (int i = 0; i < size; i++) {
        list.add("Item " + i);
    }
    
    return list;
}

// Anti-pattern: Inefficient array growth
function buildLargeArrayInefficiently(size) {
  const array = [];
  
  // Will cause multiple internal resizing operations
  for (let i = 0; i < size; i++) {
    array.push(`Item ${i}`);
  }
  
  return array;
}

// Better approach: Preallocating array
function buildLargeArrayEfficiently(size) {
  // Preallocate array with known size
  const array = new Array(size);
  
  // Fill array without resizing
  for (let i = 0; i < size; i++) {
    array[i] = `Item ${i}`;
  }
  
  return array;
}

// Anti-pattern: Inefficient multi-dimensional array access
public void processMatrixInefficiently(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    
    // Column-major traversal in a row-major array
    for (int col = 0; col < cols; col++) {
        for (int row = 0; row < rows; row++) {
            // Poor cache locality
            processElement(matrix[row][col]);
        }
    }
}

// Better approach: Cache-friendly traversal
public void processMatrixEfficiently(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    
    // Row-major traversal in a row-major array
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            // Better cache locality
            processElement(matrix[row][col]);
        }
    }
}

// Anti-pattern: Inefficient multi-dimensional array access
function processMatrixInefficiently(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  
  // Column-major traversal in a row-major array
  for (let col = 0; col < cols; col++) {
    for (let row = 0; row < rows; row++) {
      // Poor cache locality
      processElement(matrix[row][col]);
    }
  }
}

// Better approach: Cache-friendly traversal
function processMatrixEfficiently(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  
  // Row-major traversal in a row-major array
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      // Better cache locality
      processElement(matrix[row][col]);
    }
  }
}

Data Structure Selection Checklist:

1. Access Pattern Analysis
   - Identify the most frequent operations (add, remove, search, iterate)
   - Determine if random access or sequential access is needed
   - Consider if ordering is important (insertion order, natural order)
   - Evaluate the frequency of modifications vs. reads
   - Determine if duplicate elements are allowed

2. Collection Type Selection
   - Lists: ArrayList for random access, LinkedList for frequent insertions/deletions
   - Sets: HashSet for fast lookups, TreeSet for ordered elements, LinkedHashSet for insertion order
   - Maps: HashMap for fast lookups, TreeMap for sorted keys, LinkedHashMap for insertion order
   - Queues: ArrayDeque for FIFO, PriorityQueue for priority-based processing
   - Specialized: Consider BitSet, EnumSet, EnumMap for specific use cases

3. Performance Considerations
   - Estimate the expected size of the collection
   - Consider memory constraints and overhead
   - Evaluate the impact of resizing operations
   - Consider thread-safety requirements
   - Evaluate the need for primitive collections vs. object collections

4. Implementation Details
   - Preallocate collections with known or estimated size
   - Implement proper equals() and hashCode() for custom keys
   - Consider immutability for keys in hash-based collections
   - Use appropriate iteration methods for the collection type
   - Implement proper cleanup for large temporary collections

5. Special Cases
   - Very large collections: Consider specialized libraries or external storage
   - Concurrent access: Use thread-safe collections or proper synchronization
   - Memory-constrained environments: Consider compact representations
   - Performance-critical code: Consider custom implementations or specialized libraries
   - Specific algorithms: Match data structures to algorithmic requirements