• (3 Pages)
  • +
  • 1
  • 2
  • 3

Linked List Tutorial Rate Topic: ***** 4 Votes

#16 badjava  Icon User is offline

  • Lux Ex Tenebris
  • member icon

Reputation: 14
  • View blog
  • Posts: 540
  • Joined: 30-October 08

Posted 01 February 2011 - 08:19 PM

View Postmacosxnerd101, 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
Was This Post Helpful? 0
  • +
  • -

#17 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Posted 04 February 2011 - 11:46 AM

Yes- my tutorial has been revised/updated with the fixes in the OP! :)
Was This Post Helpful? 0
  • +
  • -

#18 tjoney  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 14
  • Joined: 11-March 11

Posted 11 March 2011 - 04:55 PM

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.
Was This Post Helpful? 0
  • +
  • -

#19 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Posted 11 March 2011 - 05:35 PM

Glad you found my tutorial helpful! :)
Was This Post Helpful? 0
  • +
  • -

#20 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Posted 03 July 2011 - 07:17 AM

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

Spoiler


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

Was This Post Helpful? 0
  • +
  • -

#21 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Posted 03 July 2011 - 08:08 AM

Quote

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

In other words, treat the Linked List like a Tree. :)
Was This Post Helpful? 0
  • +
  • -

#22 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Posted 03 July 2011 - 08:20 AM

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.

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

#23 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Posted 03 July 2011 - 08:23 AM

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. :)
Was This Post Helpful? 0
  • +
  • -

#24 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Posted 03 July 2011 - 08:38 AM

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

Was This Post Helpful? 1
  • +
  • -

#25 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Posted 03 July 2011 - 08:41 AM

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.

:P
Was This Post Helpful? 0
  • +
  • -

#26 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Posted 03 July 2011 - 01:53 PM

View Postmacosxnerd101, 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

Was This Post Helpful? 0
  • +
  • -

#27 eikkaj  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 119
  • Joined: 20-December 08

Posted 05 March 2012 - 06:13 PM

Very helpful, thanks.
Was This Post Helpful? 0
  • +
  • -

#28 deprosun  Icon User is offline

  • D.I.C Regular

Reputation: 0
  • View blog
  • Posts: 292
  • Joined: 16-November 10

Posted 09 March 2012 - 09:18 AM

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

Was This Post Helpful? 0
  • +
  • -

#29 johnf99  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 20-October 13

Posted 20 October 2013 - 03:57 AM

View Postskaoth, on 23 January 2010 - 09:49 PM, said:

3) public void add(E elem) does not work when adding the first. After adding
the first item to the list, tail should be pointing to head.


Surely this is wrong? macosxnerd101 indicates that a singly-linked list is being created, and that:

View Postmacosxnerd101, on 03 December 2009 - 08:50 AM, said:

Singly-linked lists work by having each node pointing to the next node, with the tail node (or end node) pointing to nothing (or a null reference).

Was This Post Helpful? 0
  • +
  • -

#30 arnavkumartechno  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 25-October 13

Posted 30 October 2013 - 10:52 PM

Does Linked List have any size limit to contain the objects which are carrying by its node??
If yes, what is the maximum size of linked list to have size for a single node?
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3