CODEWITHSUNDEEP
javalist
Parasite
Parasite

Reputation: 37

Inserting an element in a circular linked list

I'm trying to implement a method in a circular linked list where I should insert an element in this list but the list should sorted. I tried my approache but it didn't work, but I think that my logic is correct.

This is my approach:

public void insert(int value) {
        Element tmp = new Element (value);      
        
        if(this.isInList(value))
            return;
        
        //special case: empty list
        if(this.head == null) {
            tmp.next = tmp;
            this.head = tmp;
            this.rear = tmp;
        }
//      
        if(this.head.data > value) {
            this.rear.next = tmp;
            tmp.next = this.head;
            this.head = tmp;            
            }
        
        if(this.rear.data < value) {
            this.rear.next = tmp;
            tmp.next = this.head;
            this.rear = tmp;
        }
        
        Element cur = this.head;
        while(cur != this.rear && cur.data < value) {
            cur = cur.next;
        }
        
        tmp.next = cur.next;
        cur.next = tmp;  
}

The method is always looping i'm never getting a result, why is that?

Upvotes: 0

Views: 132

Answers (1)

Joop Eggen
Joop Eggen

Reputation: 109547

Handled special cases should end with a return (or else).

Then if you insert between old_cur (lesser data) and cur (greater data) you have to change old_cur.next. In java one unfortunately need a previous node.

public void insert(int value) {

    if (head == null) {
        head = new Element(value);
        head.next = nead;
        rear = head;
        return;
    }
    
    Element cur = this.head;
    Element prev = rear;
    while (cur != this.rear && cur.data < value) {
        prev = cur;
        cur = cur.next;
    }
    if (cur.data == value) {
        return;
    }
    Element addition = new Element(value);
    addition.next = cur;
    prev.next = addition;
}

The above does not exploit having a rear (also called tail in computer science). Also sometimes an Element (node) is double linked, having a .previous. Which would allow navigation in both directions with some advantages.

Upvotes: 1

Related Questions