Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Singly Linked Lists

  1. Jan 22, 2008 #1
    Hey Everyone,

    I recently got done learning about Linked Lists (well, actually only singly-linked lists) in my computer science class. It’s still pretty new to me, but I really want to make sure I understand this concept correctly. So I’ll present my knowledge about it, and hopefully, if there is a flaw or something incomplete someone will let me know. Feel free to give constructive criticism.

    Again, my code will be Java-ish, and also I don't know if this is limited to Java, but I guess when you build a generic class, putting the <E> is what makes it generic. I'm not really sure. Thanks again!

    Okay, so really a Linked List is made up of one field, the node reference commonly known as head.

    public class LinkedList<E>
    {
    private Node<E> head; ​
    }

    The head of the linked list is not a node, but only a node reference (note I did not use the keyword new, so no new object has been created).

    LinkedList methods normally include methods to do the following:
    1. Add a node to the front
    2. Add a node to the back
    3. Removing a node
    4. Returning the size of the entire list
    5. Clearing the list

    Now, inside this LinkedList class there are two inner classes, a Node class and an Iterator class. Nodes are what make up a linked list, and they have two fields:

    1. A data type (String, Integer, etc…)
    2. A node reference that points to either the next node in the list, or null (implying that it is the last node in the list).

    private class Node<E>
    {
    public ObjectType objectName;
    public Node<E> next; ​
    }

    Next, we have the Iterator class, which provides a way to go through the list in sequential order, and “grab” items (nodes) out of the list. An Iterator object also contains two fields:

    1. A linked list
    2. A node reference to keep track of iterating through the list.

    public class Iterator
    {
    private LinkedList<E> list;
    private Node<E> currentPosition; ​
    }

    Iterator class methods normally include two methods
    1. A hasNext() method, which returns true if there is another node in the element, and false if there isn’t.
    2. A Next() method, which returns the next object in the list.

    I've provided a visual representation of a singly-linked list.

    head nodeReference --> Node 1 (String, next nodeReference)--> Node 2 (String, next nodeReference)-->null
     
  2. jcsd
  3. Jan 26, 2008 #2
    This all looks exactly correct to me (although I don't know what you mean by "nodeReference" at the very end), but I don't think you understand what the "generics" are.

    The point of "generics" is that the <E> is kind of like an "argument" to the types. For example when you declare a LinkedList variable you would say LinkedList<int> if you wanted a linked list of ints, or LinkedList<Sandwich> if you wanted a linked list of Sandwich objects. So when you say:

    Code (Text):
    private class Node<E>
    {
    public ObjectType objectName;
    public Node<E> next;
    }
    What you OUGHT to be saying is:

    Code (Text):
    private class Node<E>
    {
    public E objectName;
    public Node<E> next;
    }
    The entire point of E is that it designates the type of the object to be stored in the linked list!

    (Generics that work like this are in Java and C#, also C++ has a feature called "templates" which looks and acts exactly the same but behind the scenes is actually completely different.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Singly Linked Lists
  1. Linked List (Replies: 9)

  2. Linked list (Replies: 12)

  3. Java linked list (Replies: 1)

Loading...