CODEWITHSUNDEEP
javalistlinked-listabstract-data-type
P-Em
P-Em

Reputation: 115

Deleting the rear element of a circular linked list

I am trying various methods in a circular linked list in java and one of them is to delete the rear element. I'm pretty sure that my logic is correct but I think there is something wrong in my code.

The logic is to browse the list until cur.next is before the rear element and then delete it. Then I should link the new rear element to the head and initialize the new rear.

I am not getting error, it's just that the wrong element is being deleted.
This is what I'm getting:
input: 8 | 4 | -8 | 5 | 10 | 3 | 4 | 8 |
output: 8 | 4 | 5 | 10 | 3 | 4 | 8 |

This is the method:

public void deleteAtRear() {
        if(this.head == null)
            return;
        
        Element cur = this.head;
        while(cur.next != this.rear) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        this.rear = cur;
        
    }

And this is the whole class:

public class CircularLinkedList {
    
class Element{
        
        int data;     // int type used as example
        Element next; // reference of the successor
        
        Element(int value) {
            this.data = value;
            this.next = this;
        }
        
    }

    private Element head = null;
    private Element rear = null;

    public CircularLinkedList() {
        this.head = this.rear = null;
    }
    
    
    public boolean isEmpty() {
        return head == null;
    }
    
    
    public boolean findValue(int value) {
        Element cur = this.head;
        
        while(cur != null) {
            if (cur.data == value)
                return true;
            cur = cur.next;
        }
        return false;
    }
    
    
    public int countValue(int value) {
        int c = 0; // counter
        Element cur = this.head;
        
        if(cur == null) 
            return 0;
        
        do {
            if(cur.data == value) 
                c++;
            cur = cur.next;
            
        }while (cur != this.head);
            
        return c;
    }
    
    
    @Override
    public String toString() {
        String str = "";
        Element cur = this.head;
        
            if(cur == null) 
                return "The list is empty";
        
            do {
                str += cur.data + " | ";
                cur = cur.next;
            
            }while (cur != this.head);
            
        return str;
        }
    
    
    
    public void insert(int value) {
        Element tmp = new Element (value);
        
        //special case: empty list
        if(this.head == null) {
            this.head = tmp;
            this.rear = tmp;
            
        }else { // general case
            tmp.next = this.head.next;
            this.head.next = tmp; 
            this.rear = tmp.next;
        }
            
    }
    
    
    public void deleteAtHead() {
        if(this.head == null) 
            return;
        
        Element cur = this.head;    
        while(cur.next != this.head) {            
             cur = cur.next;
            }
            cur.next = cur.next.next;       
            this.head = this.head.next;                
            return ;    
    }
    
    
    public void deleteAtRear() {
        if(this.head == null)
            return;
        
        Element cur = this.head;
//      Element prev = null;
        while(cur.next != this.rear) {
//          prev = cur;
            cur = cur.next;
        }
        cur.next = cur.next.next;
        this.rear = cur;
        
    }
    
        
    public boolean delete(int value) {
        Element cur = this.head;
        
        if(this.head.data == value) {                  //if the node to be deleted is head node
        
            while(cur.next != this.head) {         //iterate till the last node i.e. the node which is pointing to head         
                cur = cur.next;
            }
            cur.next = cur.next.next;       // update current node pointer to next node of head
            this.head = this.head.next;                //update head node
            return true;
        }
        else {                              // if node to be deleted is other than head node
        
            Element prev = cur;               // track previous node from current (node)
            while(cur.data != value) {       // find the node           
                prev = cur;
                cur = cur.next;
            }
            prev.next = cur.next; //updating next field of previous node to next of current node.current node deleted
            return true;
        }
    }
    
    
    
    public void deleteEven() {
//      if(this.head == null)
//          return;
//      
//      //case of deleting the head
//      if(this.head.data % 2 == 0) {
//          this.head.next = this.head;
//          this.rear.next = this.head;
//      if(this.head == null) 
//          this.rear = null;
//      }
//      
//      Element cur = this.head;
//      Element prev = cur;
//      while(cur != this.head) {
//          prev = cur;
//          cur = cur.next;
//      }
//      prev.next = cur.next;
        
        if(this.head == null)
            return;
        Element cur = this.head;
        while(cur.next != this.head) {
            if(cur.data % 2 == 0)
                this.delete(cur.data);
            cur = cur.next;
        }
    }
    
    
    public void deleteLastOccurence(int value) {
        Element cur = this.head;
        Element prev = null;
        Element tmp = null;
        
        if(this.head == null)
            return;
        
//      if(this.head.data == value) {
//          this.head = null;
//          return;
//      }
        
        while(cur != this.rear) {
            while(cur.next != this.head && cur.next.data == value) {
                prev = cur;
                tmp = cur.next;
            }
            cur = cur.next;
        }
        prev.next = tmp.next;
    }
    
    
    public void deleteAllOccurrences(int value) {
        Element cur = this.head;
        Element next = null;

        if (cur.data == value) {
            cur = cur.next;
            this.head = cur;
        }

        do {
            next = cur.next;
            if (next.data == value) {
                cur.next = next.next;
            }
            cur = next;

        } while (cur != this.head);
    }
    
    
    public CircularLinkedList union(CircularLinkedList a, CircularLinkedList b) {
        Element curA = a.head;
        Element curB = b.head;
        CircularLinkedList c = new CircularLinkedList();
        
//      do {
//          if(curA.data < curB.data) {
//              c.insert(curA.data);
//          curA = curA.next;
//          }else {
//              c.insert(curB.data);
//              curB = curB.next;
//          }
//      }while(curA != a.rear && curB != b.rear);
        
        do {
            c.insert(curA.data);
            curA = curA.next;
        }while(curA != a.rear);
        
        do {
            c.insert(curB.data);
            curB = curB.next;
        }while(curB != b.rear);
        return c;
    }
//  
//  
//  public CircularLinkedList inter(CircularLinkedList a, CircularLinkedList b) {
//      
//  }
    
    
//  public boolean isEqualTo(CircularLinkedList a) {
//      
//  }
    
    
    public int countOddNbrs() {
        if(this.head == null)
            return 0;
        
        int c = 0;
        Element cur = this.head;
        do {
            if(cur.data % 2 != 0)
                c++;
            cur = cur.next;
        }while(cur != this.head);
        return c;
    }

    
//  public int findLastOccurence(int value) {
//      
//  }
    
    

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        CircularLinkedList list1 = new CircularLinkedList();
        CircularLinkedList list2 = new CircularLinkedList();
        
        list.insert(8);
        list.insert(8);
        list.insert(4);
        list.insert(3);
        list.insert(10);
        list.insert(5);
        list.insert(-8);
        list.insert(4);     
        System.out.println(list);
        
        list1.insert(5);
        list1.insert(1);
        list1.insert(3);
        list1.insert(7);
        list1.insert(0);
        list1.insert(6);
        list1.insert(-4);
        list1.insert(1);        
//      System.out.println(list1);
        
//      System.out.println(list.findValue(2)); // working
        
//      list.delete(8);  // working
//      System.out.println(list);
                
//      System.out.println(list.countOddNbrs());  //working
        
//      list.deleteEven();  //  working
//      System.out.println(list);
        
//      list.deleteAtHead();  //  working
//      System.out.println(list);
        
        list.deleteAtRear();  //  working
        System.out.println(list);
        
//      list.deleteLastOccurence(4);  //not working
//      System.out.println(list);
        
//      list.deleteAllOccurrences(8);  // working
//      System.out.println(list);
        
//      list2.union(list, list1);  //not working
//      System.out.println(list2);

    }

}

Upvotes: 3

Views: 216

Answers (1)

Matt
Matt

Reputation: 13923

The problem is in the insert method where you don't assign the references properly in the general case (assuming insertion of tmp at the end of the list):

  • tmp.next should point to the first element (this.head) to have proper circularity [A]
  • this.rear.next (not this.head.next) should point to the new element [B]
  • this.rear should point to the element being inserted as it is now the new last element of the list [C]

Additionally, you are not assigning a self-reference to the single element of the list when inserting into an empty list in the special case [D].

Here is a working example of the insert method:

public void insert(int value) {
    final Element tmp = new Element(value);
    if (this.head == null) { // special case: empty list
        tmp.next = tmp; // <-- [D]
        this.head = tmp;
        this.rear = tmp;
    } else { // general case
        tmp.next = this.head; // <-- [A]
        this.rear.next = tmp; // <-- [B]
        this.rear = tmp; // <-- [C]
    }
}

Upvotes: 1

Related Questions