CS210 Tutorial 3

Complete the following exercises pasted below (or reference to texbook)

Q1. Give an implementation of the size() method for the SingularlyLinkedList class, assuming that we did not maintain size as an instance variable.

Q2. Implement a rotate() method in the SinglyLinkedList class, which has semantics equal to addLast(removeFirst( )), yet without creating any new node.

Q3. Describe an algorithm for concatenating two doubly linked lists L and M, into one doubly linked list N that contains all the nodes of L followed by all the nodes of M.

Q4. Describe how to swap two nodes x and y (and not just their contents) in a doubly linked list L given references only to x and y. Write method swap(Node x, Node y) to implement your code in java.

Q5. Describe in detail an algorithm for reversing a doubly linked list L using only a constant amount of additional space. Write method reverse() that reverses all contents in the list.

Q6. Write Java code to duplicate a circular list returning a pointer to the newly created list. Use header CList Duplicate(CList c1);

Q7. Give an algorithm for displaying contents of a Circular List in ascending order. Everytime you display contents of node, it should be removed from this list.

 

//Q1
    public int Q1(SingleLinkedList S)
    {
        int count =0;
        Node itr = S.head;
        
        while(itr!=null)
        {
            count++;
            itr=itr.next;
        }
        return count;
    }


//Q2
    public void Q2(SingleLinkedList S)
    {
        Node First = S.head;
        
        S.head=S.head.next;
        
        Node Last = S.head;
        while(Last.next!=null)
            Last=Last.next;
        
        Last.next = First;
        First.next=null;
    }
    


//Q3
    public DoublyLinkedList Q3(DoublyLinkedList L, DoublyLinkedList M)
    {
        DoublyLinkedList N = new DoublyLinkedList();
        //Note: Concat will destroy the L and M;
        
        //connect the tail and head of L and M
        L.Tail.next = M.Head;
        M.Head.prev = L.Tail;
        
        //adjust the new head and tail
        N.Head = L.Head;
        N.Tail = M.Tail;
        
        //set the size
        N.size = L.size + M.size;
        
        return N;
    }


//Q4
    public void swap(Node x, Node y)
    {
        // Note: we have to be careful with this swap method
        // do nothing if either of the Nodes is null
        if(x==null || y==null)
            return;
        
        // do nothing if x is a head
        if(x.prev == null)
            return;
        
        // do nothing if y is a tail
        if(y.next==null)
            return;

        //we need to treat the head and tail as special cases.
        /*Assume you have a long DLL with many nodes; x and y are some nodes 
        in the middle of the list. We need to find the Predecessor and 
        Successor of x and y
        */
        
        Node Px = x.prev;
        Node Sx = x.next;
        
        Node Py = y.prev;
        Node Sy = y.next;
        
        //remove x from list
        Px.next = y;
        Sx.prev = y;
        y.next = Sx;
        y.prev = Px;
        
        Py.next = x;
        Sy.prev = x;
        x.next = Sy;
        x.prev = Py;
    }


//Q5
    public void Q5(DoublyLinkedList L)
    {
        //the following is an algorithm
        Node x = L.Head;
        Node y = L.Tail;
        
        for(int i=0; i

//Q6
    public CircularList Duplicate(CircularList C1)
    {
        CircularList C2 = new CircularList();
        
        for(int i=1; i < C1.size; i++)
        {
            int x = C1.Cursor.val;
            C2.insert(x);
        }
        return C2;
  
    }


//Q7
   public int Q7(CircularList C, int s)
    {
        //find the min;
        int min = C.Cursor.val;
        for(int i=1;i C.Cursor.val)
                min = C.Cursor.val;
            C.Cursor=C.Cursor.next;
        }
        C.remove(min);
        return min;
    }
    public void Q7(CircularList C)
    {
        //find the max;
        int s = C.size;
        for(int i=1; i