Way of implementing LinkedList, Java

Question

I'm reading this book and there is this chapter on liked list and it starts with the implementation of a single linked list, it goes like this:

Creating a Linked List:

class Node {
    Node next = null;
    int data;

    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

My questions:

First: I can't understand how this works. Is this really that complex to understad it or I'm missing something?

Second: Can this "Node" class be considered a linked list? I know it's missing some functionality but is this a linked list on it's own?

Third: I've googled LinkedList implementations in java and glanced at the original class in java api and it's a totally different approach. To what approach should I stick?

Answer 1

Generally, the Node class should be as small as it can be. The main functionality of the Node is;

• Storing the value of Node
• Storing a reference (or a pointer) to the next Node instance

The simplest way to write a Node class should be similiar as above;

public class Node<E> {
    protected E value;
    protected Node<E> next;

    public Node(E value) {
        this.value = value;
    }
}

Then, you can write a custom LinkedList implementation using this generic Node class.

On that particular example code in your question, they have implemented the append method inside the Node class and that's not a good practice in my opinion. Instead, an append should be in the LinkedList class because that method is not in the responsibility of the Node class.

Append Method in LinkedList

Methods implemented on different sources can vary. But the append method itself is seen mostly the same. You have to understand the logic of the append method before implementing it.

When a linked list is empty, the head points to a null value. Head is the field, member of the LinkedList class which stores the starting Node of the Linked List.

As you append values to the Linked List, at first, head is stored with the first appended value, and then, the second value will be a new node, which head's next reference or pointer points to. And so on. You can check the states down below;

// Initial state of the Linked List
// Head is null

HEAD = NULL

// Append 40 to the Linked List 
// Head stores value 40, but next reference is null.

HEAD(40) --> NULL

// Append 10

HEAD(40) --> (10) --> NULL

// Append 20

HEAD(40) --> (10) --> (20) --> NULL

// Append 50

HEAD(40) --> (10) --> (20) --> (50) --> NULL

// Append 100

HEAD(40) --> (10) --> (20) --> (50) --> (100) --> NULL

As it is obvious, Linked List always ends up with a NULL reference, which is very useful when traversing in the list. There have to be a point, a mark that implies "This is the end of the road, terminate traversing this road"

You can also check a minimalistic simple Linked List implementation I've written for this example down below;

Minimalist Implementation Of LinkedList

public class CustomLinkedList<E> {

    private Node<E> head;

    public CustomLinkedList() {
        this.head = null;
    }

    public void appendToList(E value) {
        if(head == null)
            head = new Node<E>(value);
        else {
            Node<E> temp = head;

            // get the end node into the temp
            while(temp.next != null)
                temp = temp.next;

            // temp is the tail now
            // append new Node next to the tail
            temp.next = new Node<E>(value);
        }
    }

    public void printList() {
        if(head == null)
            return;

        System.out.print("List: ");

        Node<E> temp = head;
        while( temp != null ) {
            System.out.print(temp.value.toString() + " ");
            temp = temp.next;
        }

        System.out.println();
    }

}

Demo Code

public class DemoCustomLinkedList {

    public static void main(String[] args) {
        CustomLinkedList<Integer> linkedList = new CustomLinkedList<>();

        linkedList.appendToList(40);
        linkedList.appendToList(10);
        linkedList.appendToList(20);
        linkedList.appendToList(50);
        linkedList.appendToList(100);

        linkedList.printList();
    }

}

Demo Output

List: 40 10 20 50 100 

Answer 2

Next is the link to the next piece of data.

[Data|next->][Data|next->] .... [ ]

The next is like a pointer, it points to the next Node.

appendToTail creates a Node and the links.

Answer 3

The problem with this code is that the Node class is a node and a linked list at the same time, which is confusing. Other than that it should be pretty straightforward.

class Node {
    Node next = null;
    int data;

The next holds the next node in a list. If it is the last node, it holds null. The data is a data associated with this node, which in this case is of type int(BTW it should be final).

public Node(int d) {
    data = d;
}

This is a simple constructor which just copies the argument to its field. It represent the head of the list and a list itself.

void appendToTail(int d) {        
    Node n = this;
    while (n.next != null) {
        n = n.next;
    }

This is where find the meet. I've rearranged the code a bit to make it easier to understand. The appendToTail method adds a node at the and of the list. In the code above it traverses the list (starting with this which is a head of the list) to find the last node (the one with next field set to null).

    Node end = new Node(d);
    n.next = end;
}

Here a new node is created and added as the next node to the current last thus making it the last node of the list.