[badjava]

macosxnerd101, on 03 December 2009 - 10:50 AM, said:

Linked Lists are an alternative to ArrayLists that Computer Scientists have come up with.

Thank you for the tutorial macosxnerd101. I am getting back in to teaching myself JAVA so I am looking for all good beginner tutorials, tips, advice etc.

Can I assume that all of the fixes or improvements mentioned in the reviews following this post have been updated in the main body of your post? I thought I would ask before going through and trying to verify / compare all of the replies with your original post.

Thanks again! I look forward to seeing you out here on DIC.

BadJ

[macosxnerd101]

Yes- my tutorial has been revised/updated with the fixes in the OP!

[tjoney]

Thank you very much for this linked list tutorial. I have been searching for weeks for a good insertAt method for a linked list and yours has helped me immensely. Thanks again. You are a lifesaver.

[macosxnerd101]

Glad you found my tutorial helpful!

[Karel-Lodewijk]

I like my data structures like I like my code, short and recursive

Spoiler

public class LinkedList<E> {
    E item;
    LinkedList<E> next;

    void add(int index, E item) {
        assert(index >= 0);
        if (index == 0) {
            if (this.item == null) {
                this.item = item; 
            } else {
                LinkedList<E> node = new LinkedList<E>();
                node.item = item;
                node.next = next;
                next = node;
            }
        } else if (next != null) {
            next.add(index-1, item);
        }
    }

    void add(E item) {
        add(size()-1, item);
    }

    void remove(int index) {
        assert(index >= 0);
        if (index == 0) next = next.next;
        else if (next.item != null) next.remove(index-1);
    }

    void remove(E item) {
        if (this.item == item) next = next.next;
        else if (next != null) next.remove(item);
    }

    boolean contains(E item) {
        if (this.item == item) return true; //found
        else if (next == null) return false; //reached the end, not found
        else return next.contains(item); //continue searching
    }

    public E get(int index) {
        assert(index >= 0);
        if (index == 0) return item;
        else return (next == null) ? null : next.get(index-1); //index out of range : keep searching
    }

    int size() {
        if (next == null) return (item == null) ? 0 : 1;
        else return 1 + next.size();
    }
}

Although some of the performance characteristics are horrible. size and add are now both O(n) operation due to not keeping count and not keeping a tail.

You know, I think I can do better if I make the list circular.

This post has been edited by Karel-Lodewijk: 03 July 2011 - 07:28 AM

[macosxnerd101]

Quote

I like my data structures like I like my code, short and recursive

In other words, treat the Linked List like a Tree.

[Karel-Lodewijk]

You probably will want to ignore the remove functions above, they are kind of tricky to get right with this implementation.

void remove(E item) {
    if (next.item == item) next = next.next;
    else if (next != null) next.remove(item);
}

seems perfectly reasonable but issues occur when you try to remove the head.

macosxnerd101, on 03 July 2011 - 08:08 AM, said:

In other words, treat the Linked List like a Tree.

Yes, exactly. If you think about it, the same recursive rules apply. As in, any node of a linked list is in itself a linked list.

[macosxnerd101]

Definitely! Imo, iteration is cleaner for Linked Lists b/c they are one-dimensional. With Trees, there can be multiple child paths for a Node, so recursion makes sense for easy backtracking. With Linked Lists, it just adds to the runtime since all the calls are pushed onto the call stack, then have to be popped off. Understanding the recursive definition is great for certain operations like creating a sublist and sorting (namely mergesort). For a lot of levels, it de-optimizes the Linked List.

[Karel-Lodewijk]

Well this fixed it with the least amount of change. I avoid the problem by letting the root not contain an item and actually be sort of a fake node. It does take away some of the elegance of the previous implementation. Things like "if (index+1 == 0)", because the indexes the user supplies are now off by one. And the trickery in the size function for example.

public class LinkedList<E> {
    E item;
    LinkedList<E> next;

    void add(int index, E item) {
        assert(index >= -1);
        if (index+1 == 0) {
            LinkedList<E> node = new LinkedList<E>();
            node.item = item;
            node.next = next;
            next = node;
        } else if (next != null) {
            next.add(index-1, item);
        }
    }

    void add(E item) {
        add(size()-1, item);
    }

    void remove(int index) {
        assert(index >= 0);
        if (next != null) { 
            if (index+1 == 1) next = next.next;
            else if (next.item != null) next.remove(index-1);
        }
    }

    void remove(E item) {
        if (next != null) { 
            if (item.equals(next.item)) next = next.next;
            else next.remove(item);
        }
    }

    boolean contains(E item) {
        if (this.item.equals(item)) return true; //found
        else if (next == null) return false; //reached the end, not found
        else return next.contains(item); //continue searching
    }

    public E get(int index) {
        assert(index >= -1);
        if (index+1 == 0) return item; //index+1 because the root is not a real item and has no index
        else return (next == null) ? null : next.get(index-1); //index out of range : keep searching
    }

    int size() {
        if (next == null) return (item == null) ? 0 : 1;
        else return ((item == null) ? 0 : 1) + next.size();
    }
}

This post has been edited by Karel-Lodewijk: 03 July 2011 - 08:48 AM

[macosxnerd101]

Interesting recursive implementation.

Quote

I avoid the problem by letting the root not contain an item and actually be sort of a fake node.

I did the same thing with my AVL Tree. It made it easier for rotations without having to write a lot of extra code for the root. It's a fun little trick.

Quote

It does take away some of the elegance of the previous implementation.

[Karel-Lodewijk]

macosxnerd101, on 03 July 2011 - 08:23 AM, said:

Definitely! Imo, iteration is cleaner for Linked Lists b/c they are one-dimensional. With Trees, there can be multiple child paths for a Node, so recursion makes sense for easy backtracking. With Linked Lists, it just adds to the runtime since all the calls are pushed onto the call stack, then have to be popped off. Understanding the recursive definition is great for certain operations like creating a sublist and sorting (namely mergesort). For a lot of levels, it de-optimizes the Linked List.

The performance penalty is not automatic in a linked list all recursive calls are tail recursion subject to tail recursion optimization. A modern version of g++ would have optimized a c++ implementation right to the performance level of an iterative implementation. After looking it up, sun java at this point does not but might one day.

This post has been edited by Karel-Lodewijk: 03 July 2011 - 02:03 PM

[eikkaj]

Very helpful, thanks.

[deprosun]

First of all, great tutorial:
In

public E remove (int index)

will this work:

for (int i = 0; i < index - 1 - 1; i++) {
            temp = temp.next;;
        }
        temp.previous.next = temp.next;

since we can just connect the previous with the next.
besides what you have:

for(int i = 0; i < index-1; i++) temp = temp.next;
   Node<E> two = temp.next;

//set temp.next to point to the Node next to the Node to be removed
   temp.next = two.next; 
   E elem = two.elem; //store the element to return
   two = null; //remove the node
   counter--; //decrement size
   return elem; //return the element at that position