Results 1 to 2 of 2
  1. #1
    Join Date
    Aug 2011
    Posts
    16
    Rep Power
    0

    Default Linked List swapping question

    The question goes like this
    Swaps two elements in the list,
    * list: A B C -> swap(A,B) will result in the list B A C
    * list: A C C -> swap(A, D) will throw a NoSuchElementException
    * list: A B C B -> swap (A, B) will result in the list B A C B
    * list: A B C A B B -> swap (A,B) will result in the list B A C A B B
    * a list with one or zero elements cannot do a swap

    I'm really out of wits and ran out of patience with this question, I've made a working version but just changing the values is not allowed and I have to relink them manually. I spend already 10 hours on figuring out how to relink them. I'm sick of my lecturer he just threw everything to us without explaining and my classmates would not help.
    I've checked out the internet all over but failed to understand why. This is my last resort.


    Java Code:
    import java.util.NoSuchElementException;
    
    public class SwapListImpl<T> implements SwapList<T>
    {
    
        int size=0;
        Node<T> first;
        Node<T> last;
        Node<T> list;
        Node<T> swapNode = new Node(0);
    
        public void add(T val)
        {
            if(size==0)
            {
                first = new Node<T>(val); //
                last = first; //
                size++;  //
            }
            else
            {
                if(size==1)
                {
                    list = new Node<T>(val);
                    last.prev = first;
                    last.next = list;
                    list.prev = first;
                    last = list;
                    size++;
                }else{
                    Node<T> nNode=new Node<T>(val);
                    nNode.prev=last;
                    last.next=nNode;
                    last=nNode;
                    size++;
                }
            }
        }
    
    
        public T get(int i)
        {
            Node<T> temp = first;
    
            for(int x=0; x<i;x++)
            {
                temp=temp.next;
            }
            return temp.val;
        }
    
    
        public void swap(T val1, T val2)
        {
            swap2(val1, val2);
        }
    
       public void swap2(T val1, T val2) throws NoSuchElementException
        {
            Node<T> elementA=first;
            Node<T> elementB=first;
            boolean found = false;
            int i =0;
            int x =0;
    
            if(size>1)
            {
                while(!elementA.val.equals(val1) && elementA.next!=null)
                {
                    elementA=elementA.next;
                    i++;
                }
    
    
                while(!elementB.val.equals(val2) && elementB.next!=null)
                {
                    elementB=elementB.next;
                    x++;
                }
    
                if(!elementA.val.equals(val1) && !elementA.equals(val2) || !elementB.val.equals(val1) && !elementB.val.equals(val2))
                {
                    throw new NoSuchElementException();
                }
            
             // I found the two nodes to swap but I cant ever get past the relink process
            //    swapNode.prev = elementA.prev;
            //    swapNode.next = elementB.prev;
             //   System.out.println(swapNode.prev.val+" "+swapNode.next.val);
    
    
            }
        }
    }
    Last edited by FiasseKrystella; 02-19-2012 at 10:35 AM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,363
    Blog Entries
    7
    Rep Power
    20

    Default Re: Linked List swapping question

    Think of the elements before nodes A and B, say prevA and prevB. Also think of the elements following A and B, say nextA and nextB. So prevA and nextA embrace element A an similar with prevB, nextB and B. Swapping elements A and B is just updating all the pointers in the nodes:

    Java Code:
    prevA.next= B;
    nextA.prev= B;
    B.prev= prevA;
    B.next= nextA;
    
    prevB.next= A;
    nextB.prev= A;
    A.prev= prevB;
    A.next= nextB;
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. a linked list question
    By smacker in forum New To Java
    Replies: 5
    Last Post: 05-04-2011, 12:57 PM
  2. n00b: linked list question
    By ankitmcgill in forum New To Java
    Replies: 2
    Last Post: 03-13-2009, 04:15 AM
  3. [SOLVED] Linked list question
    By ztrath in forum New To Java
    Replies: 8
    Last Post: 03-11-2009, 11:38 PM
  4. Revised Linked List printing method question
    By CirKuT in forum New To Java
    Replies: 7
    Last Post: 12-12-2008, 10:21 PM
  5. Linked List Question
    By CirKuT in forum New To Java
    Replies: 4
    Last Post: 12-10-2008, 06:56 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
  •