Results 1 to 19 of 19

Thread: Linked Lists

  1. #1
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default Linked Lists

    Hi Everyone

    I am new to Java and trying to work on an exercise for college.

    I am busy with Linked Lists and Doubly Linked Lists and I have created my main classes. However in my List class I am trying to create a remove method and have tried various ways of getting there and keep on getting different error messages.
    All I am suppose to get is that Remove should extract the given element from my list and then return it.

    Java Code:
      public T remove() throws NoSuchElementException
        {
            if (isEmpty() )
            {
                throw new NoSuchElementException("Attempt to remove item from an empty queue.");
            }
            else 
            {
                return head=tail;
            }
        }
    My Error is as followsincompatible types - found Node<T> but expected T

    I also tried the following which did not give me an error but I am sure its not what is really needed

    Java Code:
        public void remove()
        {
            if ( empty() )
                throw new EmptyStackException();
            else 
            {
                head = tail;
            }
        }
    Can anyone just direct me in the right direction please because I really dont want to start dreaming code.

    Thanks in advance
    PS: I am using BlueJ for my code
    Last edited by Dee; 02-02-2011 at 01:55 AM. Reason: Add a note

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Java Code:
    head = tail;
    Do you really want to do this. If the List has ten Nodes then you will "remove" all of them except the last one.

    What exactly is the remove method supposed to do? Should it remove a specific Node? Then you need to have some information passed into the method to identify which Node to remove. Then you need to iterate over the List until you find the correct Node. Then you need to have the pevious Node "point" to the next Node.

  3. #3
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    Java Code:
    head = tail;
    Do you really want to do this. If the List has ten Nodes then you will "remove" all of them except the last one.

    What exactly is the remove method supposed to do? Should it remove a specific Node? Then you need to have some information passed into the method to identify which Node to remove. Then you need to iterate over the List until you find the correct Node. Then you need to have the pevious Node "point" to the next Node.
    Hi
    Thanks for replying

    To answer the first question, no I dont really want to do that. I have spoken to a friend earlier today and was told that is how it should be but when looking through the code its does not look right for me.

    Firstly the linked-list is suppose to store a collection of objects.
    I need to have the remove operation in and remove should extract the given element from the list and return it.

    We are also suppose to have removeFirst and removeLast This code I do have and seem to work fine it is just remove that I am struggling with

  4. #4
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    This is my code for removeFirst and removeLast

    Java Code:
        /**
         * extracts the given element from the head of the list and returns it
         */
        public T removeFirst()
        {
            if(head ==null)    //empty list
                return null;
    
            T result = head.getValue();
            if(head==tail)     //single entry
            {
                head = null;
                tail = null;
                return result;
            }
    
            Node<T>second = head.getNext();    //multiple entries
            Node<T>third = second.getNext();
            head = new Node<T>(null,second.getValue(),third);
            if (third==null)        //was two entries
                tail = head;
            return result;
        }
    and


    Java Code:
        public T removeLast()
        {
            if(tail ==null)    //empty list
                return null;
    
            T result = tail.getValue();
            if(tail==head)     //single entry
            {
                head = null;
                tail = null;
                return result;
            }
    
            Node<T>third = tail.getPrevious();    //multiple entries
            Node<T>second = third.getPrevious();
            tail = new Node<T>(null,third.getValue(),head);
            if (second==null)        //was two entries
                head = tail;
            return result;
        }

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Quote Originally Posted by Dee View Post
    Hi
    remove should extract the given element from the list and return it.
    What "given element"?

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Java Code:
    Node<T>second = head.getNext();    //multiple entries
            Node<T>third = second.getNext();
            head = new Node<T>(null,second.getValue(),third);
            if (third==null)        //was two entries
                tail = head;
    All that can be simplified to
    Java Code:
    head = head.getNext();
    Something similar can be done for removeLast.

  7. #7
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    Java Code:
    Node<T>second = head.getNext();    //multiple entries
            Node<T>third = second.getNext();
            head = new Node<T>(null,second.getValue(),third);
            if (third==null)        //was two entries
                tail = head;
    All that can be simplified to
    Java Code:
    head = head.getNext();
    Something similar can be done for removeLast.
    Thanks for this, I did that part of code in class as part of our exercise and my lecturer guide me through that. He then told us to do removeLast on our own using the example of removeFirst

  8. #8
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    What "given element"?
    Given element I would assume is the objects added i.e. list of names.

  9. #9
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    Java Code:
    Node<T>second = head.getNext();    //multiple entries
            Node<T>third = second.getNext();
            head = new Node<T>(null,second.getValue(),third);
            if (third==null)        //was two entries
                tail = head;
    All that can be simplified to
    Java Code:
    head = head.getNext();
    Something similar can be done for removeLast.
    Have changed that do your suggestion.
    Thanks

  10. #10
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Quote Originally Posted by Dee View Post
    Given element I would assume is the objects added i.e. list of names.
    Which element is the remove method supposed to remove? How does it know which one? Did you completely read my first reply?

  11. #11
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    BTW if this is a doubly linked list then you will also need
    Java Code:
    head.setPrevious(null);
    or whatever method/mechanism you have.

  12. #12
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Hi

    I have read your posts. Maybe its easier for now if I put all my code in here.
    My List Class

    Java Code:
    import java.util.EmptyStackException;
    import java.util.NoSuchElementException;
    import java.util.LinkedList;
    
    public class List<T>
    {
        private Node<T> head, tail;
        public int x;
    
        /**
         * Starts with an empty list
         */
        public List()
        {
            head = null;
            tail = null;
        }
    
        /**
         * check if the list is still empty
         */
        public boolean isEmpty()
        {
            return head == null;
        }
    
        /**
         * add a given element to the end of the list
         */
        public void add( T x)
        {
            tail = new Node<T>(tail, x, null);
            if (head == null)
                head=tail;
        }
    
        /**
         * insert an item at the head of the list 
         */
        public void addFront( T x )
        {
            head = new Node<T>( null, x, head );
            if( tail == null )
                tail = head;
        }
    
        /** 
         * add an item to the tail of the list 
         */
        public void addTail( T x )
        {
            tail = new Node<T>( tail, x, null );
            if( head == null )
                head = tail;
        }
    
        /**
         * returns the element at the start of the list
         * (or null if empty)
         */
        public T head()
        {
            if
            (isEmpty())
                throw new EmptyStackException();
            else
                return head.getValue();
        }
    
        /**
         * returns the element at the end of the list
         * (or null if empty)
         */
        public T tail()
        {
            if
            (isEmpty())
                throw new EmptyStackException();
            else
                return tail.getValue();
        }
    
        public void remove()
        {
            if (isEmpty() )
                throw new NoSuchElementException("Attempt to remove item from an empty queue.");
            else 
            {
                head = tail;
            }
        }
    
        /**
         * extracts the given element from the head of the list and returns it
         */
        public T removeFirst()
        {
            if(head ==null)    //empty list
                return null;
    
            T result = head.getValue();
            if(head==tail)     //single entry
            {
                head = null;
                tail = null;
                return result;
            }
    
            Node<T>second = head.getNext();    //multiple entries
            Node<T>third = second.getNext();
            head = new Node<T>(null,second.getValue(),third);
            if (third==null)        //was two entries
                tail = head;
            return result;
    
        }
    
        public T removeLast()
        {
            if(tail ==null)    //empty list
                return null;
    
            T result = tail.getValue();
            if(tail==head)     //single entry
            {
                head = null;
                tail = null;
                return result;
            }
    
            Node<T>third = tail.getPrevious();    //multiple entries
            Node<T>second = third.getPrevious();
            tail = new Node<T>(null,third.getValue(),head);
            if (second==null)        //was two entries
                head = tail;
            return result;
    
        }
    
        /**
         * removes all data from the list and frees previously allocated memory
         */
        public void clear()
        {
            head = null;
            tail = null;
        }
    
        /** 
         * returns the number of names currently held in the list 
         */
        public int size()
        {
            int count = 0;
            for( Node<T> n = head; n != null; n = n.getNext() )
                count ++;
            return count;
        }
    
        /** 
         * list the names of the people currently held in the list in the order they are stored 
         */
        public String toString()
        {
            if( isEmpty() )
                return "(empty)";
    
            String result = head.toString();
            for( Node<T> n = head.getNext(); n != null; n = n.getNext() )
                result = result + ", " + n.toString();
            return result;
        }
    
        /**
         * returns the given element from the head of the list
         */
        public T getHead()
        {
            return head.getValue();
        }
    
        /**
         * returns the given element from the tail of the list
         */
        public T getTail()
        {
            return tail.getValue();
        }
    
        public MyIterator<T>iterator()
        {
            return new MyIterator<T>(head);
        }
    
    }

    My Node Class

    Java Code:
    public class Node<T>
    {
        private T value;
        private Node<T> before, after;
    
        /**
         * Link another node to the list
         */
        public Node( Node<T> previous, T t, Node<T> next )
        {
            this.before = previous;
            if( previous != null )
                previous.after = this;
            this.after = next;
            if( next != null )
                next.before = this;
            this.value = t;
        }
    
        /** return the value from this node */
        public T getValue()
        {
            return value;
        }
    
        /** return the node before this one */
        public Node<T> getPrevious()
        {
            return before;
        }
    
        /** return the node after this one */
        public Node<T> getNext()
        {
            return after;
        }
    
        /** convert the value to a String */
        public String toString()
        {
            return value.toString();
        }    
    }
    MyIterator Class

    Java Code:
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    import java.lang.UnsupportedOperationException;
    
    class MyIterator<T> implements Iterator<T>
    {
        private Node<T> node;
    
        public MyIterator( Node<T> next )
        {
            node = next;
        }
    
        public boolean hasNext()
        {
            return node != null;
        }
    
        public T next()
        {
            if( node == null )
                throw new NoSuchElementException();
            else
            {
                T val = node.getValue();
                node = node.getNext();
                return val;
            }
        }
    
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

  13. #13
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    You still haven't answered my question. Lets assume the List is a list of Strings (one two three four five six seven). If I call the remove method which String gets removed?

  14. #14
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    My whole code should do the followig:
    Produce a linked-list class to store a collection of objects
    Develop own code for linked list as a series of functions and procedures. Ensure it provides the following operations:

    add - adds the given element to the end of the list
    size - returns the number of names currently held in the list
    toString - list the names of the people currently held in the list in the order they are stored, as a String
    addFront - adds the given element at the start of the list
    head - returns the element at the start of the list or null if empty
    last, get, returns the element at the end of the list or null if empty
    get - returns the given element from the middle of the list; get(0) gives the element at the head of the list
    remove - extracts the given element from the list and return it.


    Create an iterator to step through the list or throw appropriate exceptions

    And then lastly we must create a little interface for Size, Add, Show, Find, Clear

  15. #15
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    You still haven't answered my question. Lets assume the List is a list of Strings (one two three four five six seven). If I call the remove method which String gets removed?
    Hi Junky, please bear with me.

    According to the lecturer we have to have a the 3 remove one for the head, one for the tail and another one that should remove from the middle of the list. Because we need to add Front, Back and middle and I am still figuring how to add and to the middle.

    Hope that makes more sense now.

  16. #16
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Ok

    Looks like my question is not promoting your thought processes. Currently your remove method has no parameters. Perhaps you should pass it one so it knows which element to remove.

  17. #17
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Quote Originally Posted by Dee View Post
    that should remove from the middle of the list.
    There we go, the missing information that I have been after.

    If you want to find the middle then create 2 temp pointers: one that starts at the head and moves to the tail and one that starts at the tail and moves to the head. The middle is when they reach each other.

    Beware the trap when there are an even number of elements in the list.

  18. #18
    Dee
    Dee is offline Member
    Join Date
    Feb 2011
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    There we go, the missing information that I have been after.

    If you want to find the middle then create 2 temp pointers: one that starts at the head and moves to the tail and one that starts at the tail and moves to the head. The middle is when they reach each other.

    Beware the trap when there are an even number of elements in the list.
    Hi

    I am glad that I am finally following you, please bear with me I am 8 months pregnant and suffering from insomnia.

    Can you please direct me either via a good link or something of how I go about doing what you suggesting.

  19. #19
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Java Code:
    int[] arr = {1,2,3,4,5};
    int front = 0;
    int back = arr.length - 1;
    while(front != back) {
        front++;
        back--;
    }
    System.out.println(arr[front]);
    That gives you some idea using an array. In your case you would continually call front.next and back.previous until they met. Once again beware an even List when front and back will pass each other.

Similar Threads

  1. Linked Lists Queue
    By bdario1 in forum New To Java
    Replies: 0
    Last Post: 04-28-2010, 04:40 AM
  2. Concatenate Linked Lists
    By tttestall in forum New To Java
    Replies: 1
    Last Post: 04-20-2010, 07:03 PM
  3. Linked Lists
    By vendetta in forum New To Java
    Replies: 6
    Last Post: 01-26-2010, 08:23 AM
  4. Single linked lists - help
    By Srcee in forum New To Java
    Replies: 10
    Last Post: 10-29-2009, 05:35 PM
  5. question about linked lists
    By jkurth in forum Advanced Java
    Replies: 1
    Last Post: 11-11-2007, 08:33 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •