Circular Linked List Help in Java

Discussion in 'OT Technology' started by SPACECATAZ, Nov 14, 2009.

  1. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    Hay guys, I'm having problems with the remove method for a circular linked list. I understand the concept of how the remove method is for a regular linked list and a circular one, but whenever I keep trying to remove the node that the cursor is pointing too. Nothing happens. I believe I have to redirect the pointer of the tail to the one after I want removed to get rid of it entirely.

    Halp me. :hs:

    Code:
    package assg04;
    
    public class CircLinkedList<E> implements CircListInterface<E> {
        
        
        /**
         * Last element of the list. 
         */
        private Node<E> tail;
        
        /**
         * The size of the circular linked list.
         */
        private int size;
        
        /**
         * The current node where the cursor is pointing to in the linked list.
         */
        private Node<E> current ;
        
        
        
        /**
         * The node last inserted in the list.
         */
        private Node<E> lastInserted;
        
        /**
         * Default constructor
         * Sets the circular linked list to their initial variables.
         */
        public CircLinkedList(){
            setLast(null);
            setSize(0);
            //this.current = getLast();
        }
        
    
        /**
         * Sets the size of the list.
         * @param size The value the list will be set too.
         */
        protected void setSize(int size){
            this.size = size;
        }
        
        /**
         * Decrements the size of the list.
         */
        protected void decrementSize(){
            size--;
        }
        
        /**
         * Increments the size of the list.
         */
        protected void incrementSize(){
            size++;
        }
        
        /**
         * Returns the the first node in the list to allow traversing.
         * @return
         */
        public Node<E> getFirst(){
            if(getLast()== null)
                return null;
            else return getLast().getNext();
        }
        
        /**
         * Returns the tail node in the list to allow traversing. 
         */
        public Node<E> getLast(){
            return tail;
        }
        
        /**
         * Sets the 
         * @param theTail
         */
        private void setLast(Node<E> theTail) {
              this.tail = theTail;
           }
        
        /**
         * Adds a new item to the list. If list is empty, item is added to list and cursor points to
         * that item. If list is not empty , item is added to position after where cursor is currently
         * pointed too.
         */
        public void add(E elem) {
            if(getLast() == null) {
                setLast(new Node<E>(elem));
                getLast().setNext(getLast());
                this.current = getLast();
            } else {
                Node<E> temp = new Node<E>(elem);
                temp.setNext(getLast().getNext());
                getLast().setNext(temp);
                setLast(temp);
                advance();
            }
            incrementSize();
        }
    
        /**
         * Moves the cursor from the current position to the next item.
         * If the cursor is at the end(tail) of the list, the cursor will point
         * to the first node in the list. 
         */
        public void advance() {
            if(size() == 1){
                current = getLast();
            } else {
                current = current.getNext();
                lastInserted = getLast();
            }
        }
    
        public E getCurrent() throws ListEmptyException {
            return current.getItem();
        }
        
        /**
         * Returns true if the list is empty, false otherwise.
         */
        public boolean isEmpty() {
            if(size() == 0) return true;
            else return false;
        }
    
        /**
         * Removes the node from the list current referenced by the cursor.
         * The cursor is assigned to the next node in the list.
         */
        public void remove() {
            
            tail.setNext(getFirst());
            current = getLast();
            current = current.getNext();
            tail.setNext(current);
        
        }
    
        /**
         * Moves the cursor to the first item in the list.
         */
        public void reset() {
            current = getLast().getNext();
        }
    
        /**
         * Returns the current size of the list.
         */
        public int size() {
            return size;
        }
    
    }
    
     
  2. GatorATL

    GatorATL New Member

    Joined:
    Oct 22, 2009
    Messages:
    8
    Likes Received:
    0
    Remove doesn't work because you're simply setting the tail to the head, which in a circular linked list is always the case anyway.
     
    Last edited: Nov 15, 2009
  3. Krakerjak

    Krakerjak Active Member

    Joined:
    Jul 7, 2003
    Messages:
    8,288
    Likes Received:
    0
    Location:
    Edmonton eh
    :werd: that code really does nothing
    Code:
    Node<E> ptr;
    while(ptr != current)
      ptr = current.getNext();  // effectively finds the node before current
    ptr.setNext(current.getNext());
    
    i think this might be more accurate
     
  4. GatorATL

    GatorATL New Member

    Joined:
    Oct 22, 2009
    Messages:
    8
    Likes Received:
    0
    Code:
    Node<E> ptr = getFirst();
    while(ptr.getNext() != current)
    {
       ptr = ptr.getNext();
    }
    // At this point, ptr.getNext() == current (previous node)
    // Set previous link to current.getNext() thus skipping/removing current
    ptr.getNext() = current.getNext();
    if(getLast() == current)
    {
       // If the node removed was the last node, set new tail
       tail = ptr;
    }
    
    
     
    Last edited: Nov 15, 2009
  5. SPACECATAZ

    SPACECATAZ New Member

    Joined:
    Dec 22, 2006
    Messages:
    2,502
    Likes Received:
    0
    Thank you for the help. I finally got it working almost correctly, but there's one snag. When the cursor is moved to alternate node with the advance method. The remove method is not able to handle that case. It just handles the case where the cursor is pointing at the tail node. I added an if statement in case the cursor happens to be pointing at the node, then it can handle that appropriately, but now it creates an infinite loop on the second remove now and when I ran the middle case by itself, it ended up removing the first item in the list and the cursor node, when I only wanted it to remove the cursor (an node in the middle of the list that I want to remove).

    Code:
        public void remove() {
            //Handles if cursor points to tail
            if(getLast() == current){
                Node<E> temp = getFirst();
                Node<E> temphead = temp;
                
                while (temp.getNext() != getLast())
                    temp = temp.getNext();
                setLast(temp);
                getLast().setNext(temphead);
            }
            else {
                //Handles middle case
                Node<E> temp = getFirst();
                
                while(temp.getNext() != current && temp != getLast()){
                    temp = temp.getNext();
    
                temp.setNext(temp.getNext().getNext());
                }
            }
            decrementSize();
        }
    
    
     

Share This Page