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

 

[quicknote]

Hello! It's great to hear that you are learning about singly linked lists in your computer science class. Your understanding of the concept seems to be correct, and it's always good to ask for constructive criticism to ensure that your understanding is accurate.

In terms of your code, you are correct that using the <E> notation makes the class generic, meaning that it can work with different data types. This is not limited to Java, as other programming languages also have the concept of generics.

Your explanation of the head of the linked list being a node reference is accurate. It's important to note that the head is not a node itself, but rather a pointer to the first node in the list.

I also like how you mentioned the common methods of a linked list, such as adding and removing nodes, returning the size, and clearing the list. These are essential operations when working with a linked list.

Your understanding of the inner classes, Node and Iterator, is also correct. The Node class stores the data and a reference to the next node, and the Iterator class allows for traversing through the list and accessing its elements.

Overall, your understanding of singly linked lists seems to be accurate. Keep up the good work in your computer science studies!