2 Replies Latest reply: Oct 15, 2006 6:32 PM by 807607 RSS

    adding element to a specific index in a singly linked list

    807607
      Im having trouble with adding an element to a specific spot in the list. I dont know how to move all the other elements over by one... this is what i have so far.
           public boolean add(int index, int element);
           
           int counter = 0;
           Node m = new Node(int element);
                if(head == null){
                return false;
                }
                Node current = head;
                while(current.next !=null)
                     current = current.next;
                     counter++;
                     if(counter == index)
        • 1. Re: adding element to a specific index in a singly linked list
          796440
          You don't have to move them all. You only have to move the one before the position where you're inserting
          Before
          
                  +-----+
                  |  X  |
                  +-----+
                  
          +-----+   +-----+   +-----+   +-----+
          |  A  |-->|  B  |-->|  C  |-->|  D  |
          +-----+   +-----+   +-----+   +-----+
          
           
          After
          
          +-----+   +-----+   +-----+   +-----+   +-----+
          |  A  |-->|  B  |-->|  X  |-->|  C  |-->|  D  |
          +-----+   +-----+   +-----+   +-----+   +-----+
          All you're doing is changing B's next pointer to point to X instead of C. X points to C, and nothing beyond that has to change.
          • 2. Re: adding element to a specific index in a singly linked list
            807607
            It's just a matter of moving pointers around. You don't have to move anything over by one, except implicitly if you want to look at it that way.
            > if(head == null){
            
            return false;
            }
            You probably don't want to just return false there; the point is to add the value to the list, right?
            You probably want to set head to m and then return true. Or (depending on what you want to do) maybe you'd want to see if the index is 0, and if it is you can add OK, otherwise not add and return false.
            >      if(counter == index)
            At this point, assuming you want the new node to come after the current node, then you'd set the current node's next pointer to the new node, and set the new node's next pointer to the current node's. Thus the new node is spliced in.

            By the way please format your code meaningfully. Don't just indent stuff for the hell of it. It makes your code hard to read.