Decrease time complexity in activity

Question

I have a timeline activity that will display users status using recyclerview. I'm using firebase server and rxjava to fetch data from database. Using Array List in my timeline adapter, i'm storing all the status objects. I am performing Insertions, Deletion and Updation operations in my timeline activity based on status uid. As i'm using Array List, the time complexity for insertion is O(1) but for deletion and updation the time complexity will be O(n). If there are thousands of records, it will take time to perform Deletion and Updation operation. In order to improve my time complexity, I used Hashmap that will store status uid and index. Like in below code

fun addStatus(status : Status?){
  statusList.add(status)
  statusMap.put("uid",status?.uid)
  statusMap.put("index",statusList?.indexOf(status)?.toString)
  notifyDataSetChanged()
}

Using HashMap, time complexity in worst case improves but it also gives me some issues when trying to delete status from statusList. When i perform delete operation in my arrayList, the index of remaining objects next to the object that is deleted will changed. It also forced me to update my HashMap indexing of remaining objects. In worst case if there are millions of records, HashMap will perform Update operation in O(1) but Delete operation will take O(k) time complexity. How can i improve my code to perform all three operations in O(1) time else suggest me any better data structure that gonna work best in my case.Thanks