如何基于时间升序将数据存储至ArrayList？附数据结构代码

Hey there! Let's figure out how to keep your MyDataTemplate list sorted by occurenceTime—even when new data arrives out of sequence. Below are three practical approaches tailored to different use cases:

1. Insert Directly into the Correct Position in ArrayList #

If you want to stick with ArrayList and keep it sorted at all times, you can use binary search to find the right insertion index for each new element. Here's how to do it:

First, update your MyDataTemplate class to implement Comparable (so we can compare elements by time):

public class MyDataTemplate implements Comparable<MyDataTemplate> {
    long occurenceTime;
    int val1;
    int val2;

    public MyDataTemplate(long nanoTime, int val1, int val2) {
        this.occurenceTime = nanoTime;
        this.val1 = val1;
        this.val2 = val2;
    }

    // Implement comparison based on occurenceTime (ascending order)
    @Override
    public int compareTo(MyDataTemplate other) {
        return Long.compare(this.occurenceTime, other.occurenceTime);
    }

    // Add a getter for occurenceTime (useful for custom comparators later)
    public long getOccurenceTime() {
        return occurenceTime;
    }
}

Then, create a helper method to add elements in sorted order:

public void addSortedData(List<MyDataTemplate> dataList, MyDataTemplate newData) {
    // Use binary search to find the insertion point
    int insertionIndex = Collections.binarySearch(dataList, newData);
    
    // If binarySearch returns a negative number, convert it to the correct index
    if (insertionIndex < 0) {
        insertionIndex = -insertionIndex - 1;
    }
    
    // Insert the new element at the calculated position
    dataList.add(insertionIndex, newData);
}

Pros & Cons: #

• ✅ Uses your existing ArrayList structure
• ✅ List stays sorted at all times
• ❌ Insertions take O(n) time (shifting elements in ArrayList is expensive) — best for small datasets or low insertion frequency

2. Use TreeSet for Automatic Sorting #

If you don't strictly need ArrayList's random access capabilities, TreeSet is a great alternative. It automatically maintains elements in sorted order based on a comparator or Comparable implementation.

Option A: Allow Duplicate occurenceTime Values #

By default, TreeSet considers elements "equal" if compareTo returns 0, so it won't add duplicates. To allow multiple elements with the same occurenceTime, use a custom comparator that checks other fields too:

// Create a comparator that sorts by time first, then val1, then val2
Comparator<MyDataTemplate> timeBasedComparator = (data1, data2) -> {
    int timeComparison = Long.compare(data1.getOccurenceTime(), data2.getOccurenceTime());
    if (timeComparison != 0) {
        return timeComparison;
    }
    // Break ties with val1, then val2
    int val1Comparison = Integer.compare(data1.val1, data2.val1);
    return val1Comparison != 0 ? val1Comparison : Integer.compare(data1.val2, data2.val2);
};

// Initialize the sorted set
Set<MyDataTemplate> sortedDataSet = new TreeSet<>(timeBasedComparator);

Option B: No Duplicates Needed #

If you don't care about duplicate time entries, just use the Comparable implementation from approach 1:

Set<MyDataTemplate> sortedDataSet = new TreeSet<>();

Then, adding elements is as simple as:

sortedDataSet.add(new MyDataTemplate(System.nanoTime(), 10, 20));

Pros & Cons: #

• ✅ Insertions take O(log n) time (way faster than ArrayList for large datasets)
• ✅ No manual sorting required — the set stays sorted automatically
• ❌ No random access (you can't call get(index) like with ArrayList)

3. Batch Add & Sort Later #

If your data arrives in batches or you don't need the list to be sorted immediately, you can just add all elements to ArrayList first, then sort it when needed:

// Add elements in any order
List<MyDataTemplate> myData = new ArrayList<>();
myData.add(new MyDataTemplate(1620000000000L, 5, 15));
myData.add(new MyDataTemplate(1610000000000L, 2, 8));

// Sort when you're ready to use the data
Collections.sort(myData);
// Or use a comparator if you didn't implement Comparable:
// Collections.sort(myData, (a, b) -> Long.compare(a.getOccurenceTime(), b.getOccurenceTime()));

Pros & Cons: #

• ✅ Most efficient for large batches of data (sorting once is O(n log n) vs O(n²) for repeated insertions)
• ✅ Simple to implement
• ❌ List is unsorted until you call sort() — not ideal if you need real-time sorted access

Final Recommendation #

• Pick Approach 1 if you need ArrayList and small/low-frequency insertions
• Pick Approach 2 if you need fast insertions and don't require random access
• Pick Approach 3 if you're dealing with batch data or can tolerate delayed sorting

内容的提问来源于stack exchange，提问作者bhaskarc