Поддерживать первоначальный порядок элементов списка при добавлении или удалении элементов в нем

Question

Мне нужно иметь возможность удалять элементы из списка и вставлять их обратно, сохраняя тот же порядок. Мой список начинается с начального набора предметов. Новые предметы не могут быть вставлены. Таким образом, добавленные элементы и максимальное количество элементов остаются неизменными.

Пример:

Мой первоначальный список выглядит следующим образом

0=201, 1=402, 2=952, 3=101, 4=-54, 5=0 

Если я удаляю элементы в 2, 4 позиции, у меня есть

0=201, 1=402, 3=101, 5=0 

Но, когда я добавляю элементы удаленных позиций обратно в список; {2, 4}, у меня есть

0=201, 1=402, 3=101, 5=0, 2=952, 4=-54

Я хочу, чтобы элементы были добавлены в начальном порядке. т.е.

0=201, 1=402, 2=952, 3=101, 4=-54, 5=0 

Они должны быть в том порядке, в котором они были удалены. Это только пример, эти значения не могут быть отсортированы. Они в том порядке, в котором они были добавлены.

Если вы предлагаете использовать резервный список оригиналов, как определить правильные соседние позиции в текущем списке? Таким образом, если в исходном списке 6 элементов, а значение -54 имеет индекс 4. Я удаляю {2, 3, 4} пунктов из списка. Размер нового списка меняется на 3. Я не могу добавить элемент с индексом 4 в исходном списке в новый список с индексом 4. Новый список будет содержать только {0, 1, 2} в качестве допустимых позиций. Кроме того, это может даже не поддерживать порядок.

Итак, вопрос в том, как удалить и добавить элементы в список и убедиться, что порядок сохранен?

Кроме того, если это быть сделано с LinkedList? Если да, то как?

Редактировать: Исходный список представляет собой ArrayList. Я не могу изменить этот тип. Конечно, после определения правильного индекса мне нужно будет кормить его предметами из другой коллекции.

Answer 1

Сначала создайте резервный список оригиналов, но в Map <Index, Map<oldValue, NewValue>> (согласно вашему требованию). Если вы удаляете любой элемент из ArrayList, отметьте Новое значение как null на карте.

Answer 2

import org.junit.Test

class Fixing60945040 {

    private val originalItems = mutableListOf(
        201, 402, 952, 101, -54, 19
    )

    /**
     * a backup map of original items
     *
     * Why LinkedHashMap? HashMap works with access-order implementation.
     * Items do not keep insertion order in HashMap. So, inserting original
     * items will look like: 402, 19, 101, -54, 952, 201
     *
     * LinkedHashMap keeps insertion-order by default.
     *
     * Map<Int, Boolean> = (value, hidden)
     *
     * So, items like 201, 402 etc are keys for the map
     * and boolean tells us if this item is visible
     */
    private lateinit var backupMap: LinkedHashMap<Int, Boolean>

    /**
     * create a backup of original items
     */
    private fun createBackupMap(): LinkedHashMap<Int, Boolean> {

        val backupMap = LinkedHashMap<Int, Boolean>()
        for (item in originalItems) {
            backupMap[item] = true
        }
        return backupMap
    }

    private fun removeItem(item: Int) {
        println("Removing: $item")

        assert(originalItems.contains(item)) { "Can't remove an item that doesn't exist in the list." }

        // remove this value from original list
        val modified = originalItems.remove(item)
        if (modified) {
            // item was removed. Now, mark this item as hidden in the backup map
            backupMap[item] = false
        }
    }

    private fun insertItem(item: Int) {
        println("Inserting: $item")

        assert(!originalItems.contains(item)) { "Can't insert duplicate item." }
        assert(backupMap.containsKey(item)) { "Can't insert unknown new item." }

        // mark this item as visible in the backup map
        backupMap[item] = true

        // to know the insertion index, we need to iterate through
        // backup map
        var insertionIndex = 0
        for (entry in backupMap) {

            if (!entry.value /* !isVisible */ ) {
                /* not visible, this item is marked as hidden; ignoring */
                continue
            }

            // Is this key same as the item to be inserted?
            if (entry.key == item) {
                // It is. Insert the item.
                originalItems.add(insertionIndex, item)
                break
            } else {
                // It isn't, increase the index; check the next key.
                insertionIndex++
            }
        }
    }



    @Test
    fun test() {
        backupMap = createBackupMap()

        println("list: $originalItems \n")

        removeItem(952)
        removeItem(-54)
        println("list: $originalItems \n")

        removeItem(101)
        println("list: $originalItems \n")

        insertItem(-54)
        println("list: $originalItems \n")

        insertItem(101)
        println("list: $originalItems \n")

        insertItem(952)
        println("list: $originalItems \n")
    }
}

Если кто-нибудь обнаружит какое-либо улучшение производительности, пожалуйста, прокомментируйте. Если вы считаете, что есть лучший подход, пожалуйста, добавьте ответ.

Answer 3

Вы можете сделать это с картой (если ваш первый номер является идентификатором) ...