CODEWITHSUNDEEP
javalinked-list
ping
ping

Reputation: 1239

Question regarding Java's LinkedList class

I have a question regarding the LinkedList class in Java. I have a scenario wherein i need to add or set an index based on whether the index exists in the linkedlist or not. A pseudo-code of what i want to achieve is --

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

I did go through the Javadocs for the LinkedList class but did not come across anything relevant.

Any ideas ?

Thanks p1ng

Upvotes: 0

Views: 344

Answers (6)

DrUseful
DrUseful

Reputation: 305

It looks like you're trying to use a as a key, and don't state whether you have items at index i < a. If you run your code when ll.size() <= a then you'll end up with a NullPointerException.

And if you add an item at index a the previous item at a will now be at a+1. In this case it would be best to remove item at a first (if it exists) then add item "arbit" into a. Of course, the condition above re: ll.size() <=a still applies here.

If the order of the results is important, a different approach could use a HashMap&lt;Integer,String&gt; to create your dataset, then extract the keys using HashMap&lt;?,?&gt;.getKeySet() then sort them in their natural order (they're numeric after all) then extract the values from the map while iterating over the keySet. Nasty, but does what you want... Or create your own OrderedMap class, that does the same...

Could you expand on why you need to use a LinkedList? Is ordering of the results important?

Upvotes: 0

Mark Peters
Mark Peters

Reputation: 81054

Map<Integer, String> is definitely a good (the best?) way to go here.

Here's an option for keeping with LinkedList if that's for some bizarre reason a requirement. It has horrible runtime performance and disallows null, since null now becomes an indicator that an index isn't occupied.

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);

If you're going to take this gross road, you might be better off with an ArrayList.

Why is it so bad? Say you had only one element at index 100,000. This implementation would require 100,000 entries in the list pointing to null. This results in horrible runtime performance and memory usage.

Upvotes: 1

Romain Hippeau
Romain Hippeau

Reputation: 24375

If you need sequential access as well as keyed access you might want to try a LinkedHashMap, available as from 1.4.2
http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html

Upvotes: 2

MBO
MBO

Reputation: 30985

LinkedList cannot have holes inside, so you can't have list [1,2,3,4] and then ll.add(10,10), so I think there's something wrong with your example. Use either Map or search for some other sparse array

Upvotes: 0

maximdim
maximdim

Reputation: 8169

Searching in linked list is not very efficient (O(n)). Have you considering using different data structure - e.g. HashMap which would give you O(1) access time?

Upvotes: 2

Bart Kiers
Bart Kiers

Reputation: 170148

What about using a Map for this:

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

// ...

int a = 5;

map.put(a, "arbit");

Even if a already exists, put will just replace the old String.

Upvotes: 3

Related Questions