Добавление элемента в ArrayList в правильной записи

Question

У меня есть пользовательский интерфейс ArrayList, который расширяет класс Comparable и находится в порядке возрастания. Класс, над которым я работаю, реализует этот интерфейс.

Моя проблема в том, что мне нужно отредактировать метод add, чтобы он добавлял элемент в ArrayList, оставлял порядок в List и следил за тем, чтобы не было дубликатов.

Было бы легко сделать все это отдельными способами, но это не вопрос. Мне нужен один метод, чтобы сделать все это, чтобы при вызове метода (если он не является дубликатом) элемент добавлялся в правильную позицию.

Кроме того, чтобы проверить положение индекса, в который нужно вставить метод, я должен использовать метод compareTo (), унаследованный от класса Comparable. Единственная проблема заключается в том, что я должен реализовать свой собственный метод compareTo () в классе, над которым я работаю. Я осмотрелся повсюду и запутался, как это сделать для этого определенного класса.

Вот мой код:

    public void add(E item) throws IndexOutOfBoundsException {

        if (contains(item)) {
            throw new IllegalArgumentException("This is a duplicate!");
        }
        //here is where I need the implementation to add the item to the array, in order

    }

Тогда вот мой метод compareTo ():

        public int compareTo(E item) {

        if () {
          return -1;
        } 
        else if () {
          return 1;
        } 
        else {
            return 0;

        }
      }

Answer 1

Один из способов сделать это - сначала проверить, если

myArrayList.contains(item)

, а затем, если нет, просто вставьте и пересортируйте массив:

myArrayList.add(item);
Collections.sort(myArrayList);

Обратите внимание, что в целом, если вы хотите сохранить отсортированный набор без дубликатов, существуют структуры данных лучше, чем ArrayList.

Answer 2

Добавление элемента в правильную позицию аналогично невозможности выполнить двоичный поиск и записи последней сравниваемой позиции.

Проверьте документацию для Arrays.binarySearch.Надеюсь, это даст достаточно информации для его реализации.Ваша реализация сопоставимых должна быть такой же, как вы бы использовали для сортировки.Вот соответствующая выдержка из документации:

индекс ключа поиска, если он содержится в массиве;в противном случае (- (точка вставки) - 1).Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента больше, чем ключ, или a.length, если все элементы в массиве меньше указанного ключа.Обратите внимание, что это гарантирует, что возвращаемое значение будет> = 0, если и только если ключ найден.

Answer 3

Вы не так много информации даете.Если то, что вы действительно реализуете, является структурой данных, подобной ArrayList, то вам сначала нужно посмотреть, достаточно ли велик массив для добавления нового элемента.Если нет, вам нужно создать новый массив.В первом случае вам нужно найти место для ввода нового элемента, переместить все с этой позиции на одну, а затем добавить элемент.Во втором случае вы можете «объединить» старый список с новым элементом (то есть продолжать добавлять из старого списка до тех пор, пока не появится место, где должен появиться новый элемент, добавить новый элемент и продолжить).Другой вопрос, который у меня есть: куда помещается CompareTo (Object o)?Если вы добавляете класс ArrayList, это довольно бессмысленно, поскольку вы не хотите сравнивать массивы.Если он находится в классе, хранящемся в ArrayList, вы хотите вернуть -1, если объект this предшествует переданному объекту, -1, если объект this следует после,и 0, если они равны.Если вы можете выбрать свою структуру данных, вы можете рассмотреть связанный список: их очень легко добавлять и удалять из.

Если вы расширяете класс ArrayList, то это супер (каламбур)легко.В вашем методе add вы должны определить местоположение для добавления элемента, а затем вызвать метод super.add (int loc)

Answer 4

А как насчет TreeSet ?Кажется, у вас такое поведение, которое вы ищете.