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.

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

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

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.

Quote:

---

Originally Posted by Junky

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

This is my code for removeFirst and removeLast

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

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;
    }

---

Quote:

---

Originally Posted by Dee

Hi
remove should extract the given element from the list and return it.

---

What "given element"?

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

Code:

---

head = head.getNext();

---

Something similar can be done for removeLast.

Quote:

---

Originally Posted by Junky

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

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

Quote:

---

Originally Posted by Junky

What "given element"?

---

Given element I would assume is the objects added i.e. list of names.

Quote:

---

Originally Posted by Junky

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

Code:

---

head = head.getNext();

---

Something similar can be done for removeLast.

---

Have changed that do your suggestion.
Thanks

Quote:

---

Originally Posted by Dee

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?

BTW if this is a doubly linked list then you will also need

Code:

---

head.setPrevious(null);

---

or whatever method/mechanism you have.

Hi

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

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

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

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();
    }
}

---

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?

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

Quote:

---

Originally Posted by Junky

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.

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.

Quote:

---

Originally Posted by Dee

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.

Quote:

---

Originally Posted by Junky

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.

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.