customize an indexof call for a linkedlist (java)

Question

Hey techies,

I'm working with a very large (custom Object) linkedlist, and I'm trying to determine if an object that I'm trying to add to the list is already in there.

The issue is that the item I am searching for is a unique object containing: A 1st String A 2nd String A unique Count #

I'm trying to find out if there is an item in my linked list that contains the (1st String) and (2nd String), but ignore (the unique Count #).

This can be done the dumb way (the way I tried it first) by going through each individual linkedlist item - but this takes way too long. I'm trying to speed it up! I figured using (indexOf) would help, but I don't know how I can customize what it is searching for.

Any ideas?

Answer 1

indexOf() has O(n) performance as well because it progressively scans the List until it finds the element you're looking for.

Is the list sorted? If so, you might be able to search for an element using something like quicksort.

If you need constant time access for random elements, I don't think a Linked List is your best bet.

Answer 2

Do you NEED to use a LinkedList? If it's not legacy code, I would recommend either HashSet or LinkedHashMap. Both will give you constant-time lookup, and if you still need insertion-order iteration, LinkedHashMap has an internal LinkedList running through the keys.

Answer 3

Unfortunately the "dumb way" is the most effiecient way to do so, although you could use

if ( linkedList.contains(objectThatMayBeInList) ) { //do something }

The problem is that a LinkedList has a best case search of O(N) where N is the size of the list. That means that on any given search you have a worst case scenario of N computations. Linked lists are not the best data structure for that kind of an operation, but at the same time, it's not that bad, and it shouldn't be too slow, computers are good at doing that. Is there more specifics you can give us as to the size of the list?

Answer 4

Basically you want to find out if object A exists in linked list L. This is the search problem, and if the list is unordered you cannot do it faster than O(n).

If you kept the list sorted (making insertion slower), you could do a binary search to see if A is in the list, which would be much faster.

Perhaps you could also keep a Map (HashMap or TreeMap for instance) in addition to the list, where you keep track of what stuff is in the list.