Linked Lists. Head and Tail References

Question

Im trying to make an Add and Delete method to my linked list class. I made 2 references with the names Head and Tail.

Head -> 1 -> 2 -> 3 -> Tail:null

I keep getting problems when I try and delete specific nodes because Java says I'm out of bounds. I think it is because my Head isn't pointing to the first Node? What do you guys think? Or am i going about this the total wrong way...

public class LinkedList{

    private Node head;
    private Node tail;
    private int listCount;

    public LinkedList()
    {
        head = new ListNode(null);
        tail = new ListNode(null);
        listCount = 0;
    }

    public void add(Object elem){
        ListNode newNode = new ListNode(elem);
        if (size() == 0){
            newNode = head;
            tail = head;
        }
        newNode.setLink(tail);
        tail = newNode;
        listCount++;
        }

    public Object delete(int index)
    // post: removes the element at the specified position in this list.
    {
        // if the index is out of range, exit
        if(index < 1 || index > size())
            throw new IndexOutOfBoundsException();

        ListNode current = head;
        for(int i = 1; i < index; i++)
        {
            if(current.getLink() == null)
                throw new IndexOutOfBoundsException();

            current = current.getLink();
        }
        current.setLink(current.getLink().getLink());
        listCount--; // decrement the number of elements variable
        return current.getInfo();
    }

    public int size() {
        return listCount;
    }

}

public class Node {

    private Node link;
    private Object info;

    public Node(Object info)
    {
        this.info = info;
        link = null;
    }

    public void setInfo(Object info)
    {
        this.info = info;
    }

    public Object getInfo()
    {
        return info;
    }

    public void setLink(Node link)
    {
        this.link = link;
    }

    public Node getLink()
    {
        return link;
    }
}

Answer 1

Looks like you did not initialize the link from head to tail when you set up your initial (empty) linked list.

Ok. Here is a strategy to use when working with singly linked lists (forward link only). You need to determine what actions will be allowed on the list (e.g. add/remove from head or tail only?; or add and remove nodes anywhere in the linked list (bringing the list back together once you have cut a node out). If you will be allowing nodes to be deleted from anywhere, then you will need to have a way of UNIQUELY identifying each node (so you can unambiguously determine the node that will be deleted). You may also want to be able to add a node before or after some other node . and uniqueness may be needed for that. If you do NOT care which value you delete or add before/after then you can relax the uniqueness constraint.

Now for strategy to implement. Start with a head (initially null).

1. To add a node, walk down your linked list until you find a null next link. Replace that with your node, and have your nodes forward link set to null. (Efficiency improvement, have a tail that always has the last node in the linked list, or null if there is nothing in the list).
2. To delete a node, walk your list until you find the node you want to delete, change the previous link to the link in the node to be deleted (you are now done)
3. To add a node at the end of the list, go to the link pointed to by tail (if null, list is emplty); change its link to your node, ensure your new node has a null in its link; and set the tail to your node
4. To count size of linked list, either walk your tree and count (or, for computational efficiency, keep a running size that is incremented or decremented when you add or delete a node.

Does this help?

Look at this link for a full description!

Answer 2

I think it's because your head never links to anything. What I would do to fix it is in your add method, check the size of your list; if it's 0, set the head to the new element and set the tail equal to the head. If it's 1, link the head to the new node and set tail. If it's 2, just set the tail's link to the new node and set the tail (like you have now).

Also, I'm not sure how you implemented it, but newNode.setLink(tail); seems wrong...the tail should be linked to newNode. From the way it looks, it seems like you're trying to do newNode -> tail

EDIT: Ok, here is why I would try

public void add(Object elem){
    ListNode newNode = new ListNode(elem);
    if (size() == 0){
        newNode = head;
        tail = head;
    }else if(size() == 1){
        head.setLink(newNode);
        tail = newNode;
    }else{
        tail.setLink(newNode);
        tail = newNode;
    }
    listCount++;
}