Results 1 to 2 of 2
  1. #1
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Question Do not allow duplicates in an ordered link list

    Good morning all,
    I am working on a link list and I am creating a random number generator that can be run multiple times and what I am trying to do is make sure that when it generates random numbers and they are already in the list, I don't want it to take any actions, but if it is not in the list to insert it correctly in the list between a node that has a lower value and a higher value.

    I have it so the if I put in one group of Random numbers, they are not duplicates. And when I select 1. Create or Add n nodes to Sorted List again, it goes through and adds additional random numbers but it allows duplicates

    So I have the nodeValue in the random Generator set to start at 1 and I have it so that it doesn't add that one, but anything after that, it can add duplicates for some reason.

    I can't use any of the Java Link List or List features as I have to write the link list from scratch. I might even be building this all in the wrong order so any suggestions would be appreciated.

    Thanks
    Wally

    I have pasted my code at the end, but the next code block is where I think I am having my problem.

    Java Code:
    if (myLL == current)
          {
            if (current.getValue() == temp.getValue())
            {
              temp = null;
            } else
            {
              temp.setNext(current);
              myLL = temp;
            }
          } else
          {
            temp.setNext(current);
            previous.setNext(temp);
          }
    this works up to the point of looking at the second node beyond the beginning.
    I have tried putting another if (current.getValue() == temp.getValue()) statement in the else block but I keep getting a nullPointerException error.

    Here is output of 2 runs:

    XML Code:
    Enter a number from the selection below:
    1. Generate Initial Sorted List
    2. Insert Value
    3. Remove Value
    4. Quit
    1
    How many Nodes do you want to start with?
    5
    List (Lowest --> to --> Highest): 1, 8, 19, 25, 31, 
    Enter a number from the selection below:
    1. Generate Initial Sorted List
    2. Insert Value
    3. Remove Value
    4. Quit
    1
    How many Nodes do you want to start with?
    5
    List (Lowest --> to --> Highest): 1, 3, 8, 10, 14, 19, 19, 25, 31, 
    Enter a number from the selection below:
    1. Generate Initial Sorted List
    2. Insert Value
    3. Remove Value
    4. Quit
    Notice how 1 was not added the second time, but 19 was allowed to be added during the second pass.

    My Whole Code follows:

    LLNode Code:
    Java Code:
    package steadman.linked.list;
    
    public class LLNode {
        private int value;
        private LLNode next;
        
        public void setNext(LLNode next)
        {
        this.next = next;
        }
        
        public LLNode getNext()
        {
        return next;
        }
            
        public LLNode(int val)
        {
        value = val;
        }
        
       
        public int getValue()
        {
        return value;
        }
        
        public void displayLink()      // display ourself
          {
          System.out.print(value + ", ");
          }
       }  // end class Link
    ListChange Class Code:
    Java Code:
    package steadman.linked.list;
    
    import java.util.Scanner;
    import java.util.Random;
    
    public class ListChange
    {
      // This is the start, must have to have a list
    
      LLNode myLL;
      Scanner myScanner = new Scanner(System.in);
      int selection;
    
      public void insertInOrder(LLNode temp)
      {
        LLNode previous, current;
        if (myLL == null)
        {
          myLL = temp;
        } else
        {
          previous = myLL;
          current = myLL;
          while (current != null && current.getValue() < temp.getValue())
          {
            previous = current;
            current = current.getNext();
          }
    
          if (myLL == current)
          {
            if (current.getValue() == temp.getValue())
            {
              temp = null;
            } else
            {
              temp.setNext(current);
              myLL = temp;
            }
          } else
          {
            temp.setNext(current);
            previous.setNext(temp);
          }
        }
      }
    
      public LLNode findAndDelete(int findMe)
      {
        LLNode current = myLL;
        LLNode previous = myLL;
        while ((current.getValue() != findMe) && (current.getNext() != null))
        {
          previous = current;
          current = current.getNext();
        }
        if (current == previous)
        {
          myLL = current.getNext();
          current.setNext(null);
          return current;
        } else if (current.getValue() == findMe)
        {
          previous.setNext(current.getNext());
          current.setNext(null);
          return current;
        } else
        {
          return null;
        }
      }
    
      public void displayList()
      {
        System.out.print("List (Lowest --> to --> Highest): ");
        LLNode current = myLL;       // start at beginning of list
        while (current != null) // until end of list,
        {
          current.displayLink();   // print data
          current = current.getNext();  // move to next link
        }
        System.out.println("");
      }
    
      public void createList()
      {
        System.out.print("How many Nodes do you want to start with?\n");
        try
        {
          selection = myScanner.nextInt();
        } catch (Exception ex)
        {
          String extraChars = myScanner.nextLine();
          selection = 999;
        }
        randomNumGen(selection);
      }
    
      private void randomNumGen(int totalValue)
      {
        Random generate = new Random();
        int loopCnt;
        int value = totalValue;
        int nodeValue = 1;
    
        for (loopCnt = 0; loopCnt < value; loopCnt++)
        {
    
          int entry = nodeValue;
          LLNode temp1 = new LLNode(entry);
          insertInOrder(temp1);
          nodeValue = nodeValue + generate.nextInt(10) + 2;
        }
      }
    }
    Main Body Code:
    Java Code:
    package steadman.linked.list;
    
    import java.util.Scanner;
    
    public class SteadmanLinkedList
    {
    
      public static void main(String[] args)
      {
        int selection;
        Scanner myScanner = new Scanner(System.in);
        ListChange myList = new ListChange();
    
        while (true)
        {
          System.out.println("Enter a number from the selection below:\n"
                  + "1. Create or Add n nodes to Sorted List\n"
                  + "2. Insert Value\n"
                  + "3. Remove Value\n"
                  + "4. Quit");
    
          try
          {
            selection = myScanner.nextInt();
          } catch (Exception e)
          {
            String extraChars = myScanner.nextLine();
            selection = 999;
          }
    
          switch (selection)
          {
    
            case 1:
              myList.createList();
              myList.displayList();
              break;
            case 2:
              break;
            case 3:
              break;
            case 4:
              System.out.print("Exiting program\n");
              System.exit(0);
              break;
            default:  // Default Value if no cases selected.
              System.out.print("Invalid Selection\n");
              break;
          }
        }
      }
    }

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    2,923
    Rep Power
    4

    Default Re: Do not allow duplicates in an ordered link list

    Hi,

    I noticed a couple of things in the insert section of code.

    Java Code:
    public void insertInOrder(LLNode temp) {
          LLNode previous, current;
          if (myLL == null) {
             myLL = temp;
          }
          else {
             previous = myLL;
             current = myLL;
             while (current != null && current.getValue() < temp.getValue()) {
                previous = current;
                current = current.getNext();
             }
    
    /**
      myLL will only be equal to current once per cycle because myLL is intialized to temp and it is never changed even as 
      current is updated.  I am not certain what this is supposed to do.
    **/
             if (myLL == current) {  
                System.out.println("myLL == current");  // added this to debug
                if (current.getValue() == temp.getValue()) {
                   temp = null;
                }
                else {
                   temp.setNext(current);
                   myLL = temp;
                }
             }
             else {
                if (temp.getValue() != previous.getValue()) {   // I added this
                   temp.setNext(current);
                   previous.setNext(temp);  
                }   // and this
             }
          }
       }
    I put in a comparison for equality of values in the last else clause to only add if they are not equal. It seems to work but I have not done extensive testing. I also recommend you document each section of your insertInOrder method so you can convince yourself what you are doing is correct and also let others know what you are intending to do and why.

    Regards,
    Jim

Similar Threads

  1. need help Write code link list
    By falcon2000 in forum New To Java
    Replies: 12
    Last Post: 01-18-2013, 09:30 PM
  2. Link list help
    By Poles_Apart in forum New To Java
    Replies: 5
    Last Post: 02-28-2012, 01:18 PM
  3. Ordered list - inserting wherever on the list
    By Mnem in forum New To Java
    Replies: 6
    Last Post: 01-10-2011, 12:21 PM
  4. How to link a Array elemant to a Linked list Node
    By ravinda in forum New To Java
    Replies: 2
    Last Post: 04-18-2009, 09:16 AM
  5. Link List
    By one198 in forum New To Java
    Replies: 0
    Last Post: 10-14-2007, 01:33 PM

Posting Permissions

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