wood burning stoves 2.0*
The moose likes Performance and the fly likes Sequential Search for two data variables in a linked list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Sequential Search for two data variables in a linked list" Watch "Sequential Search for two data variables in a linked list" New topic
Author

Sequential Search for two data variables in a linked list

Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 192
I just posted here to find the most efficient way to do this. I read in a csv file into a linked list and then I split the linked list into sections based on category for each element. Of course I used an array to split each element of the list. However I can do the sequential search by either ID and Name by using hashmap and making the key = name + ID and then doing key.contains(charSequence);. However I feel like this is inefficient and I would like to use the linked list instead of a hashmap which could be done by splitting the user input and used for method overloading by passing an int in one and a string in another. I feel like this approach is a little more redundant and maybe their is a better approach for searching for id and name. Please let me know your insight. Below is an example of the elements in a linked list.

note: their are more elements than this.

element 1

name: George
address: 4410 something dr.
phone number: 978-888-6666
id: 43


element 2

name: Karla
address: 339 something dr.
phone number: 334-338-6556
id: 23


Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7807
    
  21

Charles Sexton wrote:Of course I used an array to split each element of the list.

I'm afraid that's not obvious at all. A LinkedList already contains elements, so why would you feel the need to use arrays as well?

If, however, you mean that you're using an array to store the values of your "element" (name, address, etc), then you're almost certainly doing it WRONG.

This is precisely what Java classes were meant for, so just create a class that describes the contents of one element (Client? Customer?) and convert your input to instances of that class BEFORE you do any sorting/arranging.

Furthermore, the fields of that class should be the appropriate type, viz:and should contain all the logic for converting Strings (or CSV "elements") to those types.

Then your LinkedList becomes a LinkedList<Client>, and you can store it in whatever structure you see fit.

If it's only orderings you're worried about, it's worth remembering that there's absolutely nothing to stop you creating more than one Map - and if you need to access elements in those orders, I'd actually suggest a TreeSet or TreeMap, not a HashMap. There's very little space overhead, and you can create different orderings with Comparators (java.util.Comparator).

HIH; and if you have any further questions, please feel free to ask.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 192
Winston Gutkowski wrote:
Charles Sexton wrote:Of course I used an array to split each element of the list.

I'm afraid that's not obvious at all. A LinkedList already contains elements, so why would you feel the need to use arrays as well?

If, however, you mean that you're using an array to store the values of your "element" (name, address, etc), then you're almost certainly doing it WRONG.

This is precisely what Java classes were meant for, so just create a class that describes the contents of one element (Client? Customer?) and convert your input to instances of that class BEFORE you do any sorting/arranging.

Furthermore, the fields of that class should be the appropriate type, viz:and should contain all the logic for converting Strings (or CSV "elements") to those types.

Then your LinkedList becomes a LinkedList<Client>, and you can store it in whatever structure you see fit.

If it's only orderings you're worried about, it's worth remembering that there's absolutely nothing to stop you creating more than one Map - and if you need to access elements in those orders, I'd actually suggest a TreeSet or TreeMap, not a HashMap. There's very little space overhead, and you can create different orderings with Comparators (java.util.Comparator).

HIH; and if you have any further questions, please feel free to ask.

Winston


So basically I have a customer class and this class has attributes that defines each customer. When I store the elements in the linked list I should store them as customer/client objects. So basically I should read in the file from my customer class and use my linked list class to add each customer as a node. Then I do whatever I need to with the linked list.

I'm trying to do a sequential search on both the name and ID of the customer. Would a hashmap or linked list be easier for this? If you want to would you look at my class and tell me of beginner mistakes or changes to do? I am trying to improve.

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7807
    
  21

Charles Sexton wrote:So basically I have a customer class and this class has attributes that defines each customer. When I store the elements in the linked list I should store them as customer/client objects. So basically I should read in the file from my customer class and use my linked list class to add each customer as a node. Then I do whatever I need to with the linked list.

Pretty much, yes.

I'm trying to do a sequential search on both the name and ID of the customer. Would a hashmap or linked list be easier for this? If you want to would you look at my class and tell me of beginner mistakes or changes to do? I am trying to improve.

Actually, I'd say neither. Assuming that you're not interested in duplicates (which a Map would preclude anyway), I'd suggest that what you actually want is a Set - specifically, a NavigableSet (←click) - and TreeSet (←also click) would seem to me the most obvious choice. And the nice thing about TreeSet's is that you can supply Comparators to them (java.util.Comparator (←again click)).

Just set up Comparators to compare your Customers by whatever way you want, and use them to order your dataset.

A word of warning though: ID is probably a unique key to your Customer, but "name" may well not be (you might have more than one "John Smith" in your Customer list), and if you create a TreeSet ordered by name, it will only allow ONE Customer with that name. In that case, you might be better off creating a TreeSet for the ones ordered by ID, and a List (and I'd suggest an ArrayList, rather than a linked one) to store your "name-based" Customers. However, in that case, you'll have to sort your List before you use it (have a look at Collections.sort(List, Comparator)).

Unfortunately, there is no "OrderedList" interface (ie, a List which maintains its own order when things are added or removed), nor a true SkipList (which would be my choice for such a class), in the standard Java Collections classes. So you're pretty much forced to sort a standard List every time you update it, or add everything you need, and then sort.

If you're interested in a neat exercise, you might fancy writing a SkipList. They're kind of fun, and the pseudocode is freely available, as well as William Pugh (the inventor)'s original papers. Alternatively, there are almost certainly implementations out there in Internet-land.

Winston
Charles Sexton
Ranch Hand

Joined: Sep 26, 2013
Posts: 192
Winston Gutkowski wrote:
Charles Sexton wrote:So basically I have a customer class and this class has attributes that defines each customer. When I store the elements in the linked list I should store them as customer/client objects. So basically I should read in the file from my customer class and use my linked list class to add each customer as a node. Then I do whatever I need to with the linked list.

Pretty much, yes.

I'm trying to do a sequential search on both the name and ID of the customer. Would a hashmap or linked list be easier for this? If you want to would you look at my class and tell me of beginner mistakes or changes to do? I am trying to improve.

Actually, I'd say neither. Assuming that you're not interested in duplicates (which a Map would preclude anyway), I'd suggest that what you actually want is a Set - specifically, a NavigableSet (←click) - and TreeSet (←also click) would seem to me the most obvious choice. And the nice thing about TreeSet's is that you can supply Comparators to them (java.util.Comparator (←again click)).

Just set up Comparators to compare your Customers by whatever way you want, and use them to order your dataset.

A word of warning though: ID is probably a unique key to your Customer, but "name" may well not be (you might have more than one "John Smith" in your Customer list), and if you create a TreeSet ordered by name, it will only allow ONE Customer with that name. In that case, you might be better off creating a TreeSet for the ones ordered by ID, and a List (and I'd suggest an ArrayList, rather than a linked one) to store your "name-based" Customers. However, in that case, you'll have to sort your List before you use it (have a look at Collections.sort(List, Comparator)).

Unfortunately, there is no "OrderedList" interface (ie, a List which maintains its own order when things are added or removed), nor a true SkipList (which would be my choice for such a class), in the standard Java Collections classes. So you're pretty much forced to sort a standard List every time you update it, or add everything you need, and then sort.

If you're interested in a neat exercise, you might fancy writing a SkipList. They're kind of fun, and the pseudocode is freely available, as well as William Pugh (the inventor)'s original papers. Alternatively, there are almost certainly implementations out there in Internet-land.

Winston


Thank You Winston, my next task that I want to do is write a program that compares quick sort and heap sort for large amounts of data. After that I will try to write a skip list and I will bookmark this......I have looked into comparator and it is a very good class to use. Comparator and comparable are excellent choices for sorting data structures.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7807
    
  21

Charles Sexton wrote:Thank You Winston...

You're most welcome. And good luck with your future plans.

And just for future reference, you don't need to include the entire post inside quote tags when you're replying - it tends to make threads very long - just include enough so we know what you're replying to.

Winston
 
wood burning stoves
 
subject: Sequential Search for two data variables in a linked list