Вопрос относительно класса Java LinkedList

Question

У меня вопрос по поводу класса LinkedList в Java.У меня есть сценарий, в котором мне нужно добавить или установить индекс в зависимости от того, существует ли индекс в связанном списке или нет.Псевдокод того, чего я хочу достичь, -

if index a exists within the linkedlist ll 
     ll.set(a,"arbit")
else
      ll.add(a,"arbit")

Я прошел Javadocs для класса LinkedList, но не нашел ничего уместного.1006 *

Спасибо, p1ng

Answer 1

Как насчет использования Карта для этого:

Map<Integer, String> map = new HashMap<Integer, String>();

// ...

int a = 5;

map.put(a, "arbit");

Даже если a уже существует, put просто заменит старую строку.

Answer 2

Если вам нужен последовательный доступ, а также доступ по ключу, вы можете попробовать LinkedHashMap, доступный с 1.4.2
http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html

Answer 3

Поиск в связанном списке не очень эффективен (O (n)).Рассматриваете ли вы использовать другую структуру данных - например, HashMap, которая даст вам O (1) время доступа?

Answer 4

Map<Integer, String> это определенно хороший (лучший?) Способ пойти сюда.

Вот вариант для сохранения с LinkedList, если по какой-то странной причине это требование. Он имеет ужасную производительность во время выполнения и запрещает null, поскольку теперь null становится индикатором того, что индекс не занят.

String toInsert = "arbit";
int a = 5;

//grow the list to allow index a
while ( a >= ll.size() ) {
   ll.add(null);
}

//set index a to the new value
ll.set(a, toInsert);

Если вы собираетесь пойти по этому грубому пути, вам может быть лучше с ArrayList.

Почему это так плохо? Скажем, у вас был только один элемент с индексом 100 000. Эта реализация потребует 100 000 записей в списке, указывающих на null. Это приводит к ужасной производительности во время выполнения и использованию памяти.

Answer 5

Похоже, вы пытаетесь использовать a в качестве ключа и не указывать, есть ли у вас элементы с индексом i < a.Если вы запустите свой код, когда ll.size() <= a, вы получите NullPointerException.

. И если вы добавите элемент с индексом a, предыдущий элемент на a теперь будет иметь значение a+1.В этом случае лучше всего сначала удалить элемент на a (если он существует), а затем добавить элемент "arbit" в a.Конечно, условие выше re: ll.size() <=a все еще применяется здесь.

Если порядок результатов важен, другой подход мог бы использовать HashMap<Integer,String> для создания вашего набора данных, а затем извлечь ключи с помощью HashMap<?,?>.getKeySet() затем сортируйте их в естественном порядке (в конце концов, они числовые), затем извлекайте значения из карты, перебирая набор ключей.Неприятно, но делает то, что вы хотите ... Или создайте свой собственный класс OrderedMap, который делает то же самое ...

Не могли бы вы рассказать, почему вам нужно использовать LinkedList?Важна ли упорядоченность результатов?

Answer 6

LinkedList не может иметь дыр внутри, поэтому у вас не может быть списка [1,2,3,4], а затем ll.add(10,10), поэтому я думаю, что с вашим примером что-то не так. Используйте либо Map, либо ищите какой-нибудь другой разреженный массив