1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...