0

I am coding a doubly circular linked list and implementing various methods. 2 of which consist on returning the union or intersection of 2 lists given as an argument. I am pretty sure that my logic is correct but I'm not understanding why I'm not getting any result. I'm not getting errors just no response.

This is my code:


public class DCLL {
    //ascending order
    class Element{
        
        int data;     // int type used as example
        Element next = null; // reference of the successor
        Element previous = null;
        Element(int value) {
            this.data = value;
            this.next = this;
            this.previous = this;
        }
        
    }
    
    private Element head = null;
    private Element rear = null;
    private int length = 0;
    
    
    public DCLL() {
        this.head = this.rear = null;
        this.length = 0;
    }
    
    
    public DCLL(DCLL a) {
        this();
        
        //list a is empty
        if(a.isEmpty())
            return;
        
        Element cur = a.head;
        do {
            this.insert(cur.data);
            cur = cur.next;
            
        }while(cur != a.head);
        
    }
    
    
    public int getLength() {
        return this.length;
    }
    
    public boolean isEmpty() {
        return this.length == 0;
    }
    
    
    @Override
    public String toString() {
        String s = " ";
        if(this.isEmpty())
            return"Empty list";
        
        Element cur = this.head;
        s = " | " + cur.data + " | ";
        cur = cur.next;
        while(cur != this.head) {
            s+= cur.data + " | ";
            cur = cur.next;
        }
        return s;
    }
    
    
    public int countEven() {
        if(this.isEmpty())
            return 0;
        
        Element cur = this.head;
        int c = 0;
        while(cur != this.rear) {
            if(cur.data % 2 == 0)
                c++;
            cur = cur.next;
        }
        return c;
    }
    
    
    public int findFirstOccurence(int value) {
        
        if(this.isEmpty())
            return -1;
        
        Element cur = this.head;
        int c = - 1;
        while(cur != this.rear) {
            c++;
            if(cur.data == value)
                return c;
            cur = cur.next;
        }
        return c;
    }
    
    
    public int findLastOccurence(int value) {
        
        if(this.isEmpty())
            return - 1;
        
        Element cur = this.rear;
        int c = length ;
        while(cur != this.head) {
            c--;
            if(cur.data == value)
                return c;
            cur = cur.previous;
        }
        return c;
    }
    
    
    public boolean isInList(int value) {
        
        if(this.isEmpty())
            return false;
        
        Element cur = this.head;
        while(cur != this.head) {
            if(cur.data == value)
                return true;
            cur = cur.next;
        }
        return false;
    }
    
    
    public boolean insertAtHead(int value) {
        Element tmp = new Element (value);
        
        if(this.isEmpty()) {
            this.head = this.rear = tmp;
            return true;
        }
        
        this.head.previous = null;
        this.rear.next = null;
        
        tmp.next = this.head;
        this.head = tmp;
        this.length++;
        
        this.head.previous = this.rear;
        this.rear.next = this.head;
        return true;
    }
    

    public boolean insert(int value) {
        Element tmp = new Element(value);
        
        if(this.isEmpty()) {
            this.head = this.rear = tmp;
        this.length++;
        return true;
        }
        
        //inserting before the head
        if(this.head.data > tmp.data) {
            tmp.next = this.head;
            this.head.previous = tmp;
            tmp.previous = this.rear;
            this.rear.next = tmp;
            this.head = tmp;
            this.length++;
            return true;
        }
        
        //inserting after the rear
        if(this.rear.data < tmp.data) {
            tmp.previous = this.rear;
            tmp.next = this.head;
            this.rear.next = tmp;
            this.head.previous = tmp;
            this.rear = tmp;
            this.length++;
            return true;
        }
        
        // general case insert between head and rear (no repetition)
        Element cur = this.head;
        while(cur != this.rear && cur.data < tmp.data)      
            cur = cur.next;
        
        if(cur.data == tmp.data)
            return false;
        
        tmp.next = cur;
        tmp.previous = cur.previous;
        cur.previous.next = tmp;
        cur.previous = tmp;
        this.length++;
        return true;
    }
    
    
    public boolean delete(int value) {
        //list is empty
        if(this.isEmpty())
            return false;
        
        //testing if value is outside the range [head.data and rear.data]
        if(this.head.data > value || this.rear.data < value)
            return false;
        
        // list of 1 element
        if(this.head == this.rear && this.head.data == value) {
            this.head = this.rear = null;
        this.length = 0;
        return true;
        }
        
        //delete the head
        if(this.head.data == value) {
            this.rear.next = this.head.next;
            this.head.next.previous = this.rear;
            this.head = this.head.next;
            this.length--;
            return true;
        }
        
        //delete the rear
        if(this.rear.data == value) {
            this.rear.previous.next = this.head;
            this.head.previous = this.rear.previous;
            this.rear = this.rear.previous;
            this.length--;
            return true;
        }
        
        //general case: delete between head and rear
        Element cur = this.head;
        while(cur != this.rear && cur.data < value)
            cur = cur.next;
        
        if(cur == this.rear || cur.data != value)
            return false;
        
        cur.next.previous = cur.previous;
        cur.previous.next = cur.next;
        this.length--;
        return true;
        
    }
    
    
    public void deleteEven() {
        
        if(this.isEmpty())
            return;
        
        this.head.previous = null;
        this.rear.next = null;
        
        if(this.head == this.rear && this.head.data % 2 == 0) {
            this.head = this.rear = null;
            this.length = 0;
        }
        
        while(this.head != null && this.head.data % 2 == 0) {   
            this.head = this.head.next;
            this.length--;
        }
        
        if(this.head == null) {
            this.rear = null;
            return;
        }
        
        while(this.rear != null && this.rear.data % 2 == 0) {
            this.rear = this.rear.previous;
            this.length--;
        }
        
        this.head.previous = this.rear;
        this.rear.next = this.head;
        
        Element cur = this.head;
        while(cur != this.rear) {
            if(cur.data % 2 == 0) {
                cur.next.previous = cur.previous;
                cur.previous.next = cur.next;
                this.length--;
            }
            cur = cur.next;
        }       
        
    }
    
    
    public void deleteHigher(int value) {
        
        if(this.isEmpty())
            return;
        
        this.head.previous = null;
        this.rear.next = null;
        
        if(this.head == this.rear && this.head.data > value) {
            this.head = this.rear = null;
            this.length = 0;
        }
        
        while(this.head != null && this.head.data > value) {   
            this.head = this.head.next;
            this.length--;
        }
        
        while(this.rear != null && this.rear.data > value) {
            this.rear = this.rear.previous;
            this.length--;
        }
        
        this.head.previous = this.rear;
        this.rear.next = this.head;
        
        Element cur = this.head;
        while(cur != this.rear) {
            if(cur.data > value) {
                cur.next.previous = cur.previous;
                cur.previous.next = cur.next;
                this.length--;
            }
            cur = cur.next;
        }       
        
    }
    
    
    public void deleteLastOccurence(int value) {
        
        if(this.isEmpty())
            return;
        
        if(this.head == this.rear && this.head.data == value) {
            this.head = this.rear = null;
            this.length = 0;
        }
        
        if(this.rear.data == value) {
            this.head.previous = this.rear;
            this.rear.next = this.head;
            this.rear = this.rear.previous;
            this.length--;
        }
        
        Element cur = this.rear;
        while(cur != this.head) {
            if(cur.data == value) {
                cur.next.previous = cur.previous;
                cur.previous.next = cur.next;
            }
            cur = cur.previous;
        }
    }
    
    
    public void deleteAllOccurrences(int value) {
        
        if(this.isEmpty())
            return;
        
        this.head.previous = null;
        this.rear.next = null;
        
        while(this.head != null && this.head.data == value) {
            this.head = this.head.next;
            this.length--;
        }
        
        if(this.head == null) {
            this.rear = null;
            return;
        }
        
        while(this.rear != null && this.rear.data == value) {
            this.rear = this.rear.previous;
            this.length--;
        }
        
        this.head.previous = this.rear;
        this.rear.next = this.head;
        
        Element cur = this.head;
        while(cur != this.rear) {
            if(cur.data == value) {
                cur.next.previous = cur.previous;
                cur.previous.next = cur.next;
            }
            cur = cur.next;
        }
    }
    
    
    public DCLL union(DCLL a, DCLL b) {
        Element curA = a.head;
        Element curB = b.head;
        DCLL c = new DCLL();

        do {
            if(curA.data > curB.data) {
                c.insert(curA.data);
                curA = curA.next;
                this.length++;
            }else {
                c.insert(curB.data);
                curB = curB.next;
                this.length++;
            }
        }while(curA != a.rear && curB != b.rear);
        
        do {
            c.insert(curA.data);
            curA = curA.next;
            this.length++;
        }while(curA != this.rear);
        
        do {
            c.insert(curB.data);
            curB = curB.next;
            this.length++;
        }while(curB != this.rear);
        return c;
    }
    
    
    public DCLL intersection(DCLL a, DCLL b) {
        Element curA = a.head;
        DCLL c = new DCLL();
        
        if(a.head == null || b.head == null)
            return c;
        
        do {
            if(b.isInList(curA.data)) {
                c.insert(curA.data);
                curA = curA.next;
            }
        }while(curA != this.rear);
        return c;
    }
    
    

    public static void main(String[] args) {
        DCLL list = new DCLL();
        DCLL list1 = new DCLL();
        DCLL list2 = new DCLL();
        
        list.insert(2);
        list.insert(5);
        list.insert(9);
        list.insert(2);
        list.insert(58);
        list.insert(-8);
        list.insert(6);
        System.out.println(list);
        
        list1.insert(3);
        list1.insert(7);
        list1.insert(17);
        list1.insert(6);
        list1.insert(5);
        list1.insert(-8);
        list1.insert(-50);
        System.out.println(list1);
        
//      list.insertAtHead(3);
//      System.out.println(list);
        
//      System.out.println(list.countEven());
//      
//      System.out.println(list.findFirstOccurence(5));
        
//      list.delete(2);
//      System.out.println(list);
        
//      list.deleteEven();
//      System.out.println(list);
        
//      list.deleteHigher(5);
//      System.out.println(list);
        
//      list.deleteLastOccurence(5);
//      System.out.println(list);
        
//      list.deleteAllOccurrences(58);
//      System.out.println(list);
        
//      System.out.println(list.findLastOccurence(6));
        
        list2.union(list, list1);
        System.out.println(list2);
        
//      list2.inter(list, list1);
//      System.out.println(list2);
        
    }

}
P-Em
  • 115
  • 9
  • You need to show what is the input/output for which you are not getting any response and what is the expected output? – SomeDude May 10 '21 at 17:16
  • @SomeDude I didn't understand what you mean. The input is in the main method, and the output is returned in the method. – P-Em May 10 '21 at 17:19
  • But what is expected output? – SomeDude May 10 '21 at 17:21
  • You have an infinite loop in your `union` method (actually two of them) because `curA` will never equal `this.rear` (and neither will `curB`). Frankly, I don't understand the purpose of the latter two loops. Shouldn't you be inserting the contents of `c` into `this` (or, rather, replacing the contents of `this` with the contents of `c`)? For that matter, why do you need `c` at all in that method? – Ted Hopp May 10 '21 at 17:30
  • @TedHopp I should be inserting the content of ```a``` and ```b``` in ```c```. Then on what element should the while loop stop at? I tried to make the next of rear = to null and the previous of head = null, do the operations needed while the while loop is ```while(cur != null)``` for a and b, and the relinkin the head and rear. but I got a nullPointerException. – P-Em May 10 '21 at 17:39
  • The first loop is fine as far as I can tell. I'm suggesting that you don't need the second or third loops at all; when the first loop finishes, `c` will contain everything from `a` and `b`. However, in `main()`, you are throwing away the return value and printing the contents of `list2`. That suggests to me that `union()` should be inserting the contents of `a` and `b` into `this`, not into `c`. Get rid of loops 2 and 3, get rid of `c`, and replace every occurrence of `c` with `this` in the first loop and see how that works. – Ted Hopp May 10 '21 at 17:42
  • @TedHopp Before trying to do that I just want to mention that I did the second and third loop so that if the program finished comparing the ```list a``` (which means if ```list a``` don't have any more elements but ```list b``` have, it should be inserting into ```c``` the rest of elements of ```b```. – P-Em May 10 '21 at 17:46
  • @TedHopp I removed ```c```, and replaced it with ```this```. But the problem is I can't print it. – P-Em May 10 '21 at 17:51
  • Ah, I see. You need to modify the terminating conditions for the second or third loops to be `while(curA != a.rear)` and `while(curB != b.rear)` (not `this.rear`) in both cases. – Ted Hopp May 10 '21 at 17:53
  • @TedHopp yeah you're right I missed this, but now I got a nullPointerException on the toString method ```s = " | " + cur.data + " | ";``` – P-Em May 10 '21 at 18:12
  • You should post a separate question about that, since it's completely unrelated to this question. However, first check out https://stackoverflow.com/q/218384/535871 – Ted Hopp May 10 '21 at 18:53

0 Answers0