1

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?

Improve this question
6
  • What didn't you understand? Commented Nov 27, 2012 at 21:53
  • 1
    You're missing something; it doesn't get much simpler than this. You should stick to an approach you understand: step through it on paper, it's the best way to learn. Commented Nov 27, 2012 at 21:55
  • 2
    What specifically don't you understand? There's almost no code there to understand. Commented Nov 27, 2012 at 21:55
  • 1
    Write, or copy, a program using this class, then step through it with pencil and paper. Draw a new box each time a constructor is called. Use an arrow pointing to the box to represent a reference to the object. Have an eraser handy for when things change. Commented Nov 27, 2012 at 21:56
  • 1
    OMG, @Patricia Shanahan. I remember you and your outstanding posts from the good old days of comp.lang.java.programmer. Good to see you're alive, not like this old usenet group. Commented Nov 27, 2012 at 22:10

3 Answers 3

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

which is confusing -> No it is not. LinkedList is generally implemented in this way only.
@RohitJain Well actually you have a seperate LinkedList and Node classes in standard Java. The Node is a private static inner class of LinkedList, but it is a seperate class.
@RohitJain i think most implementations are a LinkedList class that only contains a single reference to a root node and the LinkedList class operates on the nodes. in OPs example, the node class itself does operations which is weird design.
From a language independent computer science point of view, a node with a next pointer is generally used. The LinkedList is a Java class that implements List. You can still have a conceptual linked list with just the Node class.
@SteveKuo I agree it is a conceptual linked list. At the same time it is not intuitive to have appendToTail method on a Node. It would be more intuitive to name the class List.
1

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.

Improve this answer

Comments

0

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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.