Learn Singly Linked Lists | Computer Science Tutorial

[Chromium]

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

 

[Coin]

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:

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

What you OUGHT to be saying is:

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.)