7-1 递增有序顺序表的插入java

在Java中，如果你有一个递增有序顺序表，比如一个基于数组实现的List，插入新元素通常需要保持原有的排序。以下是向这样的列表插入新元素的一个简单示例：

import java.util.ArrayList;
import java.util.List;

public class IncrementalOrderedList {
    private List<Integer> list = new ArrayList<>();

    // 插入方法，保留有序性
    public void insert(int value) {
        // 首先查找插入位置，从后向前遍历找到第一个大于等于value的位置
        int index = list.size(); //默认值为list最后一位
        for (int i = index - 1; i >= 0 && list.get(i) < value; i--) {
            index = i;
        }

        // 将新元素添加到该位置
        list.add(index, value);
    }

    // 示例
    public static void main(String[] args) {
        IncrementalOrderedList list = new IncrementalOrderedList();
        list.insert(5);  // 初始为空，直接插入在第一位
        list.insert(3);  // 插入3，现在是[3, null]
        list.insert(6);  // 插入6，现在是[3, 5, 6]
        list.insert(4);  // 插入4，在5之前，现在是[3, 4, 5, 6]
    }
}

在这个例子中，`insert`方法首先找到新元素应该插入的适当位置，然后用`add`方法将其添加。注意，如果列表已满且所有现有元素都小于新值，那么新元素会添加到列表的末尾。