1

I have a short (12 elements) LinkedList of short strings (7 characters each).

I need to search through this list both by index and by content (i.e. search a particular string and get its index in the list).

I thought about making a copy of the LinkedList as an array at runtime (just once, since the LinkedList is a static member of my class), so I can access the strings by index more quickly.

Given that the LinkedList is never changed at runtime, is this bad programming practice or is this an idea worth considering?

IMPORTANT EDIT: the array can't be sorted, I need it to map specific strings to specific numbers.

6
  • What is the relevance of the index in the list? Why do you need to get it? Aug 10, 2010 at 15:28
  • 2
    Why are you using a LinkedList? Linked lists are primarily for good insert/delete performance, and your list sounds like it's never changed. Aug 10, 2010 at 15:32
  • @Jon Benedicto my list is not sorted, so I thought a linear search would have been the best one. So why rewrite it when there's indexOf()? @Winston Smith: the strings are hex colors (i.e. "#aabbcc") and the index is its mapping in the API I'm using) Aug 10, 2010 at 15:47
  • @klex you're correct that a linear search would be the one to use, but a LinkedList is not the most efficient data structure to search in a linear manner, due to local cache misses. A Vector would be the most efficient data structure for linear search. Aug 10, 2010 at 15:58
  • 1
    @Jon Benedicto: no, Vector is a bad choice here. Vector is synchronized, which is unnecessary here, since the list is never modified, so the synchronization just adds overhead. Aug 10, 2010 at 16:10

6 Answers 6

4

Instead of a LinkedList just use an ArrayList - you can look up fast based on an index, and you can easily search through it.

2

What problem are you trying to solve here? Are you worried that accessing elements by index is too slow in LinkedList? If so, you might want to use ArrayList instead.

But for a 12-element list, the improvement probably won't make any measurable difference. Unless this is something you're accessing several hundred times a second, I wouldn't waste any time on trying to optimize it.

2
  • It can happen that I need to access it a hundred times in a row, and, since this will work on a internet-connected Android device, I think performance might be important. Aug 10, 2010 at 15:52
  • OK, in that case, use ArrayList. Aug 10, 2010 at 16:00
1

Another idea you might want to consider is using a Map:

Map someMap<int, String>

It's easy to search for values in a map by both key and value.

Might also not be the best idea, but at least better then creating 2 lists with the same values =)

0
1

The question is, why are you using a LinkedList in the first place?

The main reason to choose a LinkedList over an array list is if you need to make a number of insertions/deletions in the middle of the List or if you don't know the exact size of the list and don't want to make a number of reallocations of the Array.

The main reason to choose an ArrayList over a LinkedList is if you need to have random access to each of the elements.

(There are other advantages/disadvantages to each, but those are probably the main ones that come to mind)

It looks like you do need random access to the list, so why did you pick a LinkedList over an ArrayList

0

I would say it depends on your intention and the effect it really has.

With only 12 elements it seems unlikely to me that converting the LinkedList to an array has an impact on performance. So it could make the code unnecessarily (slightly) harder to understand for other people. From this point of view it could be considered a non optimal programming style.

If the number of elements increases, i.g. you're need to pre-process some data which would require a dynamic data structure. And for later use an indexed lookup performs much better, this wouldn't be a bad programming style, rather a required improvement.

0

Given that you know the exact amount of elements you are going to be using why not use an array from the start?

string[] myArray = new string[7];
// Add your data

Sort(myArray); // Sort your strings

int value = binarySearch(myArray, "key"); // Search your array

Or since you cant sort the array you could just make a linear search method

public int Search(string[] array, string key)
{
    for(int i = 0; i < array.legnth(); i++)
    {
        if(array[i] == key)
             return i;
    }
    return -1;
}

Edit: After re-loading the page and reading peoples responses I agree that ArrayList should be exactly what you need.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.