1 2 Previous Next 19 Replies Latest reply: Feb 5, 2009 12:46 PM by 800323 RSS

    LinkedList - how to override the contains method?

    800790
      Hi all

      I think I have a fairly common java problem...

      I have a linkedList LL, LL contains a many objects O, each O object contains 2 values - an integer I and a String S

      The LL has grown to be quite large, and I am trying to perform a search through the linked list for string S.

      So... The problem for me is that I would like to simply call the "contains" method and search for string S! BUT I can't do this because LL is not a <String> LinkedList, it is an <O> LinkedList.
      Thus, I inefficiently have been looking at every O object in the list, checking to see if the O's String value was equal to S.

      Which is wildly inefficient. I would love to reduce the amount of time of this process... I thought that there may be a simple way to re-implement the contains method of the linked list? But I still don't know if that would help seeing how I am going to be writing it myself and I am not that knowledgable about writing an efficient "contains" method...

      Any (related) thoughts?
        • 1. Re: LinkedList - how to override the contains method?
          807588
          As a rule of thumb, you almost never have to subclass any concrete collection type. They do their job and you merely use them.

          What it sounds line to me is that you are using the wrong collection type! Instead of
          List<Pair<Integer, String>>
          You may need a
          Map<String, Integer>
          If the String is unique or
          Map<String, Set<Integer>>
          ... for example, if the string is not unique.

          I suggest you do what you should have done in your initial post: describe the problem, not your attempted solution.
          • 2. Re: LinkedList - how to override the contains method?
            800790
            Ah,

            Sorry! I actually have something like

            LinkedList<myObject> x = new LinkedList<myObject>();

            myObject actaully contains more than the 2 variables, and I felt that an object would be more fitting than a long list of

            LinkedList <value types><value types><value types><value types><value types><value types><value types><value types><value types><value types>

            So... I didn't subclass the LinkedList, rather I am using the linkedList to use <myObject> as it's list type
            • 3. Re: LinkedList - how to override the contains method?
              807588
              You still haven't described your problem, only your attempted solution.

              For example, are the strings unique? have you considered Map?
              • 4. Re: LinkedList - how to override the contains method?
                800790
                I believe the string to be unique, however it may not be... I am not really considering a map at this time.

                I am looking for an efficient way to search for the presence of the string in the linkedList and obtain it's index value. This way I can update one of the variables contained within the object that is located in the same index value of the linkedList

                Edited by: adamorn on Feb 5, 2009 9:54 AM
                • 5. Re: LinkedList - how to override the contains method?
                  807588
                  adamorn wrote:
                  I believe the string to be unique, however it may not be... I am not really considering a map at this time.

                  I am looking for an efficient way to search for the presence of the string in the linkedList and obtain it's index value. This way I can update one of the variables contained within the object that is located.
                  The efficient way to search a List ... is to use a Map instead!

                  You can keep the list sorted, but then adding elements will not be efficient.
                  • 6. Re: LinkedList - how to override the contains method?
                    800790
                    I understand that you are really pushing maps... But I was hoping for a solution based on the linked list problem that I've been working with.... I have created a bit of a long program with the linked list and hope not to have to redo large portions of the code to work with a map...

                    Or do you really feel I should give up and use a map object - confusing myself and to also try to figure out how to properly search for the string in the map... Only to find out that maybe the end result is a different problem in terms of efficiency...
                    • 7. Re: LinkedList - how to override the contains method?
                      807588
                      It sounds like you are unfamiliar with Map. Is that so?
                      • 8. Re: LinkedList - how to override the contains method?
                        800790
                        yes. and I don't want to risk converting my entire program to using map objects just so I can use the unique contains feature of it, while losing the functionality of the linked list that Ive been working with...
                        • 9. Re: LinkedList - how to override the contains method?
                          807588
                          I don't want to say "told you so" but this is the reason for encapsulation: if you have designed your program correctly, the implementation decision "implements using a list" would have been encapsulated in a class and localized. And thus easier to change.

                          Any way, sorting the list may be an option, but that carries its own complications.
                          • 10. Re: LinkedList - how to override the contains method?
                            800790
                            So what you're saying is that there is not way to customize the "contains" method in any simliar way to the comparable interface for Collections.sort, so that it would merely search the string object rather than the entire object O?

                            Or are you just really against using linkedLists?
                            • 11. Re: LinkedList - how to override the contains method?
                              807588
                              adamorn wrote:
                              So what you're saying is that there is not way to customize the "contains" method in any simliar way to the comparable interface for Collections.sort, so that it would merely search the string object rather than the entire object O?
                              Do not subclass LinkedList. Simply write code to search the list.

                              Did you understand the sorting hint?
                              Or are you just really against using linkedLists?
                              I use lists all the time. When appropriate.
                              • 12. Re: LinkedList - how to override the contains method?
                                800790
                                I didn't subclass the linked list (unless Im getting your terminology wrong)

                                I AM trying to figure out how to more efficiently search the list.

                                I have code that searches the linkedList but it is wildly inefficient, and the purpose of this post was to find out if anyone had any advice on how to efficiently search a linkedlist
                                • 13. Re: LinkedList - how to override the contains method?
                                  800323
                                  adamorn wrote:
                                  So what you're saying is that there is not way to customize the "contains" method in any simliar way to the comparable interface for Collections.sort, so that it would merely search the string object rather than the entire object O?

                                  Or are you just really against using linkedLists?
                                  I would attempt to use the good Doctor's advice first; but...
                                  You do not customize the contains() method; you just customize the equals() method of your object class (and don't forget the hash() method). However, this will effect other methods of the LinkedList (indexOf(), etc.) and, in this case, the equals() method would not use the entire state of the class (the String part but not the int part).

                                  Also, this will not improve the efficiency.

                                  Edited by: jbish on Feb 5, 2009 6:46 PM
                                  • 14. Re: LinkedList - how to override the contains method?
                                    807588
                                    The easiest way to improve searching efficiency is to sort and use a binary search.
                                    1 2 Previous Next