2
\$\begingroup\$

Consider the following piece of code I wrote (a templated Linked List):

package com.data_structures;

public class LinkedList<NodeDataType> {

    public LinkedList() {
        super();
    }

    class LinkedListNode<DataType> {
        private DataType data;
        LinkedListNode<DataType> nextNode;
    
        public LinkedListNode(DataType data) {
            this.data = data;
            this.nextNode = null;
        }
    
        public DataType getData() {
            return data;
        }
    
        public void setData(DataType data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return String.valueOf(data).toString();
        }
    
    }

    private LinkedListNode<NodeDataType> rootNode = null;

    private int nodeCount = 0;

    private void addTail(LinkedList<NodeDataType>.LinkedListNode<NodeDataType> node) {
        LinkedList<NodeDataType>.LinkedListNode<NodeDataType> temp = rootNode;
        while (temp.nextNode != null) {
            temp = temp.nextNode;
        }
        temp.nextNode = node;
    }

    private void changeRoot(LinkedList<NodeDataType>.LinkedListNode<NodeDataType> node) {
        node.nextNode = this.rootNode;
        this.rootNode = node;
    }

    private void addNodeAt(LinkedList<NodeDataType>.LinkedListNode<NodeDataType> node, int position) {
        LinkedListNode<NodeDataType> temp = this.rootNode;
        for (int i = 0; i < position - 1; i++) {
            temp = temp.nextNode;
        }
        node.nextNode = temp.nextNode;
        temp.nextNode = node;
    }

    public LinkedList(NodeDataType data) {
        this.rootNode = new LinkedListNode<>(data);
        this.nodeCount++;
    }

    public int getNodeCount() {
        return nodeCount;
    }

    public void addNode(NodeDataType data, int position) {
        LinkedListNode<NodeDataType> node = new LinkedListNode<>(data);
        if (position <= 1 || this.rootNode == null) {
            changeRoot(node);
        }
        else if (position >= this.nodeCount) {
            addTail(node);
        }
        else {
            addNodeAt(node, position);
        }
        this.nodeCount++;
    }

    private void eraseRoot() {
        this.rootNode = this.rootNode.nextNode;
    }

    private void eraseTail() {
        LinkedList<NodeDataType>.LinkedListNode<NodeDataType> temp = this.rootNode;
        LinkedList<NodeDataType>.LinkedListNode<NodeDataType> temp2 = temp;
        while (temp.nextNode != null) {
            temp2 = temp;
            temp = temp.nextNode;
        }
        temp2.nextNode = null;
    }
    
    private void eraseNodeAt(int position) {
        LinkedList<NodeDataType>.LinkedListNode<NodeDataType> temp = this.rootNode;
        LinkedList<NodeDataType>.LinkedListNode<NodeDataType> temp2 = temp;
        for (int i = 0; i < position - 1; i++) {
            temp2 = temp;
            temp = temp.nextNode;
        }
        temp2.nextNode = temp.nextNode;
    }

    public void deleteNode(int position) {
        if (position <= 1) {
            eraseRoot();
        }
        else if (position >= this.nodeCount) {
            eraseTail();
        }
        else {
            eraseNodeAt(position);
        }
        this.nodeCount--;
    }

    public NodeDataType getNode(int position) {
        if (position <= 1) {
            return this.rootNode.data;
        }
        else {
            LinkedList<NodeDataType>.LinkedListNode<NodeDataType> node = this.rootNode;
            for (int i = 0; i < position - 1 && node.nextNode != null; i++) {
                node = node.nextNode;
            }
            return node.data;
        }
    }


}

If we take a careful look at addNode and deleteNode functions, we see that I essentially had to write separate logic for "ends" and "in-betweeners". I don't usually code in Java, and am not very good at Java. Is there a better logic for these 2 functions?

\$\endgroup\$
2
  • \$\begingroup\$ With the language you are most comfortable with, do you know the way to avoid the separate logic? \$\endgroup\$
    – vnp
    Nov 19 at 6:00
  • \$\begingroup\$ @vnp do you know the way to avoid the separate logic? frankly, that's part of the question 😅 \$\endgroup\$ Nov 19 at 6:10
3
\$\begingroup\$

Template Type Parameter

You've used NodeDataType for your LinkedList template type parameter, and DataType for your LinkedListNode template type parameter. Why are these different?

Considering your code is littered with LinkedList<NodeDataType>.LinkedListNode<NodeDataType> types, it seems you want the same type used for both classes.

But if you want the same type, why are you specifying it twice?

Nested Types

What is the type name for the list's internal nodes? It is not LinkedListNode; it is LinkedList::LinkedListNode. Somewhat verbose? A little too redundant? Perhaps Node is sufficient.

Organization

Put like thing together. Inside LinkedList, you have a constructor, then a type definition, then data members, then methods, then another constructor, then more methods.

Better would be a type definition, data members, constructors, and methods.

Access restriction

Why is data private, but nextNode isn't?

Does anything external to LinkedList need access to the internal node structure at all? Internal nodes are never returned by a public method, so the entire class could be private.

super

Why is does the LinkedList() constructor calling super() when there is no parent class defined?

Why doesn't the LinkedList(NodeDataType data) constructor call super()?

First Rework

Applying the above points, you're code can look more like:

class LinkedList<DataType> {

   private class Node {           // No need for an additional template parameter type!
      private DataType data;
      Node next;

      /* constructors & methods */
   }
   
   private Node rootNode = null;
   private int nodeCount = 0;
   
   public LinkedList() {
   }
   
   public LinkedList(DataType data) {
       addNode(data, 1);
   }
   
   /* methods */
}

Notice the second constructor isn't creating a node, setting it to root, and incrementing the node count; it is just using a routine which will already do this for you.

Redundant code

You've written the following code a few times:

        for (int i = 0; i < position - 1; i++) {
            temp = temp.nextNode;
        }

It is in addNodeAt, getNode. Very similar code is in eraseNodeAt. Even addTail, and eraseTail, are close to this code, if you consider the tail is at position nodeCount.

Let's write the code once:

    private Node findNode(int position) {
        if (position < 1 || position > nodeCount)
            raise IndexOutOfBoundsException("Position is not within linked list");

        Node node = rootNode;
        for(int i = 1; i < position; i++) {
            node = node.nextNode;
        }

        return node;
    }

Note: I've made indexes outside the range 1 <= position <= nodeCount an error, as opposed to silently treating those as the head or tail nodes.

Now we can easily use this helper function in other functions:

    public DataType getNode(int position) {
        Node node = findNode(position);
        return node.getData();
    }

Adding and removing nodes can use this too. But we need to be a little careful. To add or remove a node at position, we need to access the node at position - 1 and manipulate that node's nextNode. To add/remove the node at the root, there is no node before it, so that will remain a special case. Eg)

    public void addNode(DataType data, int position) {
        Node new_node = new Node(data);
        if (position == 1) {
            new_node.nextNode = rootNode;
            rootNode = new_node;
        } else {
            Node prev_node = findNode(position - 1);
            new_node.nextNode = prev_node.nextNode;
            prev_node.nextNode = new_node;
        }
        nodeCount++;
    }

Note that adding at the tail is not a special case, since prev.nextNode will contain null before the addition, and that null value is simply copied to the new node's nextNode.

Similar code for deleteNode left to student.

\$\endgroup\$
4
  • \$\begingroup\$ You've used NodeDataType for your LinkedList template type parameter, and DataType for your LinkedListNode template type parameter. Why are these different? When I used DataType as the type parameter for both the outer class and the inner class, Visual Studio Code gave me a "mask" warning. That is why I'd to do it like that, but I think the way you've suggested is better because it'll reduce the redundancy in the code, for the use case where NodeDataType and DataType have different values is practically and logically impossible :) \$\endgroup\$ Nov 20 at 5:30
  • \$\begingroup\$ Considering your code is littered with LinkedList<NodeDataType>.LinkedListNode<NodeDataType> types, it seems you want the same type used for both classes. Um... I didn't quite understand this. Please you please explain this part? Do you mean, I can do LinkedList.LinkedListNode<NodeDataType> and it will still logically be the same? \$\endgroup\$ Nov 20 at 5:33
  • \$\begingroup\$ I've made indexes outside the range 1 <= position <= nodeCount an error, as opposed to silently treating those as the head or tail nodes That is what I would have done normally, but that was a part of the assignment. That is why I had to do it like that :) \$\endgroup\$ Nov 20 at 5:34
  • \$\begingroup\$ Why is does the LinkedList() constructor calling super() when there is no parent class defined? Isn't the parent class Object by default? \$\endgroup\$ Nov 20 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.