Linked List question
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Linked List question

  1. #1
    Join Date
    Mar 2009
    Posts
    78

    Linked List question

    Ok, so this is a standard linked list. The output is shown at the bottom. How to I access the input and sort it by, let's say, ISBN number? So that it's going to display it.
    I have no idea how to do this.


    Code:
    class LinkedList1
    {
        
        
        private class Node
        {
            String value;   
            Node next;      
            
            
            
            Node(String val, Node n)
            {
                value = val;
                next = n;
            } 
            
            
            
            Node(String val)
            {
               // Call the other (sister) constructor.
               this(val, null);            
            }
        }	
    	 
        private Node first;  // list head
        private Node last;   // last element in list
    	     
        /**
           Constructor.
        */
        
        public LinkedList1()
        {
            first = null;
            last = null;        
        }
        
        /**
           The isEmpty method checks to see 
    		 if the list is empty.
    		 @return true if list is empty, 
    		 false otherwise.
        */
        
        public boolean isEmpty()
        {        
            return first == null;       
        }
        
        
        
        public int size()
        {
           int count = 0;
           Node p = first;     
    		 while (p != null)
           {
               // There is an element at p
               count ++;
               p = p.next;
           }
           return count;
        }
        
      
        public void add(String e)
        {
          if (isEmpty()) 
          {
              first = new Node(e);
              last = first;
          }
          else
          {
              // Add to end of existing list
              last.next = new Node(e);
              last = last.next;
          }      
        }
        
       
        
        public void add(int index, String e)
        {
             if (index < 0  || index > size()) 
             {
                 String message = String.valueOf(index);
                 throw new IndexOutOfBoundsException(message);
             }
             
             // Index is at least 0
             if (index == 0)
             {
                 // New element goes at beginning
                 first = new Node(e, first);
                 if (last == null)
                     last = first;
                 return;
             }
             
             // Set a reference pred to point to the node that
             // will be the predecessor of the new node
             Node pred = first;        
             for (int k = 1; k <= index - 1; k++)        
             {
                pred = pred.next;           
             }
             
             // Splice in a node containing the new element
             pred.next = new Node(e, pred.next);  
             
             // Is there a new last element ?
             if (pred.next.next == null)
                 last = pred.next;         
        }
        
        
        public String toString()
        {
          StringBuilder strBuilder = new StringBuilder();
          
          // Use p to walk down the linked list
          Node p = first;
          while (p != null)
          {
             strBuilder.append(p.value + "\n"); 
             p = p.next;
          }      
          return strBuilder.toString(); 
        }
        
        
        public String remove(int index)
        {
           if (index < 0 || index >= size())
           {  
               String message = String.valueOf(index);
               throw new IndexOutOfBoundsException(message);
           }
           
           String element;  // The element to return     
           if (index == 0)
           {
              // Removal of first item in the list
              element = first.value;    
              first = first.next;
              if (first == null)
                  last = null;             
           }
           else
           {
              // To remove an element other than the first,
              // find the predecessor of the element to
              // be removed.
              Node pred = first;
              
              // Move pred forward index - 1 times
              for (int k = 1; k <= index -1; k++)
                  pred = pred.next;
              
              // Store the value to return
              element = pred.next.value;
              
              // Route link around the node to be removed
              pred.next = pred.next.next;  
              
              // Check if pred is now last
              if (pred.next == null)
                  last = pred;              
           }
           return element;        
        }  
        
       
        
        public boolean remove(String element)
        {
           if (isEmpty()) 
               return false;      
          
           if (element.equals(first.value))
           {
              // Removal of first item in the list
              first = first.next;
              if (first == null)
                  last = null;       
              return true;
           }
          
          // Find the predecessor of the element to remove
          Node pred = first;
          while (pred.next != null && 
                 !pred.next.value.equals(element))
          {
              pred = pred.next;
          }
    
          // pred.next == null OR pred.next.value is element
          if (pred.next == null)
              return false;
          
          // pred.next.value  is element
          pred.next = pred.next.next;    
          
          // Check if pred is now last
          if (pred.next == null)
              last = pred;
          
          return true;       
        }
        
        public static void main(String [] args)
        {
            LinkedList1 ll = new LinkedList1();
            ll.add("Book1, ISBN12345");
            ll.add("Book2, ISBN28439");
            ll.add("Book3, ISBN39482");
            ll.add("Book4, ISBN38372");
            ll.add("Book5, ISNN93827");
            System.out.println("The members of the list are:");
            System.out.print(ll);
        }
    }

  2. #2
    Join Date
    May 2006
    Location
    UK
    Posts
    4,474

    Re: Linked List question

    A easy way is to convert your LinkedList to an array (or ArrayList) and the use the java.util.Arrays.sort() method (or java.util.Collections.sort() method) to do the sort and then convert the sorted array (or ArrayList) back to your LinkedList.

    The best way is to get your class to implement the java.util.List interface and then use java.util.Collections.sort() method to do the sort.

    The hard way is to write your own sort class that can work with your LinkedList class.
    Posting code? Use code tags like this: [code]...Your code here...[/code]
    Click here for examples of Java Code

  3. #3
    Join Date
    Mar 2009
    Posts
    78

    Re: Linked List question

    Quote Originally Posted by keang View Post
    A easy way is to convert your LinkedList to an array (or ArrayList) and the use the java.util.Arrays.sort() method (or java.util.Collections.sort() method) to do the sort and then convert the sorted array (or ArrayList) back to your LinkedList.

    The best way is to get your class to implement the java.util.List interface and then use java.util.Collections.sort() method to do the sort.

    The hard way is to write your own sort class that can work with your LinkedList class.
    Ok, Collections.sort sounds better. I want to do it using a linked list.

    Like this?

    import java.util.Arrays;
    import java.util.Collections;
    import java.util.List;
    public class MainClass {
    public static void main(String args[]) throws Exception {
    List list = Arrays.asList("a","c","b");
    Collections.sort(list);
    for (int i = 0, n = list.size(); i < n; i++) {
    if (i != 0)
    System.out.print(", ");
    System.out.print(list.get(i));
    }
    System.out.println();
    }
    }
    I have several things in the nodes, though. How does it know what is what? It needs to sort the ISBN only.
    Last edited by XodoX; April 29th, 2012 at 04:41 PM.

  4. #4
    Join Date
    May 2006
    Location
    UK
    Posts
    4,474

    Re: Linked List question

    You use the 2 parameter sort method and pass in a Comparator that defines the ordering you require.
    Posting code? Use code tags like this: [code]...Your code here...[/code]
    Click here for examples of Java Code

  5. #5
    Join Date
    Mar 2009
    Posts
    78

    Re: Linked List question

    No, never-mind about that. I need a list interface then for collections.sort. I'm teaching this myself and it's the linked list chapter, so I can't use anything else. I have some books and it needs to display them. The sorting can be added later. So that's a simple linked list then, is it not? I don't need add or remove because the input is already in there.

    Code:
    public class Node
    {
       Books book;
       Node next;
    
       public Node( Books bookA)
       {
           book = bookA;
       }
    }
    
    public class MyLinkedList()
    {
       private Node head;
       public MyLinkedList(Books bookA)
       {
          head = new Node(bookA);
       }
       public add(Books bookA)
       {
          MyLinkedList current = this;
          
    
    // here
    
    
    
    
          while ( current.next != NULL )
          {
             current = current.next;
          }
          current.next = new Node(bookA);
       }
    }
    That's the short version. So that's one book. I'm not sure about the adding of additional books. How would I do this? But this would require user input. Or should I just remove the add/remove etc. from the list in #1 and use that instead? ughh, this is confusing.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center