6
\$\begingroup\$

I have recently made two kinds of linked lists in Java. I know that there is one with generic and one without. However, what I am really concerned about is which style should be used mostly (or which style should be used as the main style to implement the LinkedList structure). When talking about these two styles, could you ignore the singly or doubly type, but mainly concentrate on the structure?

The first one is a singly LinkedList, but most of the functions are coded inside the Node class, and the linked list class only contains some easy functions which is used to call the functions inside the Node class.

package chapter2linkedlist;
import java.util.*;
public class LinkNode {

private Node root;

class Node {
    private String data;
    private Node nextNode;

    public Node() {
    }

    public Node(String data) {
        this();
        this.setData(data);
    }

    public void setData(String data) {
        this.data = data;
    }

    public void add(Node nextNode) {
        if (this.nextNode == null) {
            this.nextNode = nextNode;
        } else {
            this.nextNode.add(nextNode);
        }
    }

    public String getData() {
        return this.data;
    }

    public Node getNext() {
        return this.nextNode;
    }

    public void print() {
        System.out.println(this.data);
        if (this.nextNode != null) {
            this.nextNode.print();
        }
    }

    public boolean search(String data) {
        if (data == this.data) {
            return true;
        } else {
            if (this.nextNode == null) {
                return false;
            } else {
                return this.nextNode.search(data);
            }
        }
    }

    public boolean delete(Node previousNode, String data) {
        boolean isDeleted = false;
        if (this.data.equals(data)) {
            previousNode.nextNode = this.nextNode;
            isDeleted = true;
        } else {
            if (this.nextNode != null) {
                this.nextNode.delete(this, data);
            }
        }
        return isDeleted;
    }
}

public void addNode(String data) {
    Node newNode = new Node(data);
    if (this.root == null) {
        this.root = newNode;
    } else {
        this.root.add(newNode);
    }
}

public void printNode() {
    if (this.root != null) {
        this.root.print();
    }
}

public boolean isContain(String data) {
    return this.root.search(data);
}

public void deleteNode(String data) {
    if (this.root.data.equals(data)) {
        if (this.root.getNext() == null) {
            this.root = new Node();
        } else {
            this.root = this.root.getNext();
        }
    } else {
        this.root.delete(root, data);
    }

}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    LinkNode linkNode = new LinkNode();
    linkNode.addNode("A");
    linkNode.addNode("B");
    linkNode.addNode("C");
    linkNode.addNode("D");
    linkNode.addNode("E");
    linkNode.addNode("F");
    linkNode.addNode("G");

    System.out.println("before delete nodes");
    linkNode.printNode();
    linkNode.deleteNode("A");
    linkNode.deleteNode("E");
    System.out.println("after delete nodes");
    linkNode.printNode();

    LinkedList<String> testList = new LinkedList<String>();
    StringBuffer strBuffer = new StringBuffer();
    for(int i = 0; i < 10; i++){
        strBuffer.append(i);
        testList.add(strBuffer.toString());
    }
    System.out.println(testList);
    System.out.println();
    for(int i = 0; i < testList.size(); i++){
        if(testList.get(i).equals("0123456") || testList.get(i).equals("012345678")){
            testList.remove(i);
            i--;
        }
    }
    System.out.println(testList);


}

}

The second one is a doubly class, but most functions are implemented inside the LinkedList class, the Node class only have some basic functions which is used to operate its own variables.

package chapter2linkedlist;
public class SelfLinkedList<T> {

private Node<T> root;
private int countSize;

public SelfLinkedList() {
    root = null;
    countSize = 0;
}
public boolean isEmpty() {
    return this.countSize == 0;
}

public int size() {
    return this.countSize;
}

private Node<T> getRootNode() {
    if (null != this.root) {
        return this.root;
    }
    return null;
}

private Node<T> getLastNode() {
    if (null != root) {
        Node<T> currentNode = root;
        while (currentNode.getNextNode() != null) {
            currentNode = currentNode.getNextNode();
        }
        return currentNode;
    }
    return null;
}

public boolean append(T var) {
    Node<T> newNode = new Node<T>(var);
    if (null == this.root || countSize == 0) {
        this.root = newNode;
        countSize++;
        return true;
    }

    Node<T> currentNode = root;
    while (currentNode.getNextNode() != null) {
        currentNode = currentNode.getNextNode();
    }
    currentNode.setNextNode(newNode);
    newNode.setPreviousNode(currentNode);
    countSize++;
    return true;
}

public boolean removeFirst() {
    if (null == this.root) {
        return false;
    }
    if (this.root != null || this.root.getNextNode() == null) {
        this.root = null;
        countSize--;
        return true;
    }
    this.root = this.root.getNextNode();
    this.root.prevNode = null;
    countSize--;
    return true;
}

public boolean removeLast() {
    if (null == this.root) {
        return false;
    }
    if (null != this.root || null == this.root.getNextNode()) {
        this.root = null;
        countSize--;
        return true;
    }
    Node<T> currentNode = root;
    while (currentNode.getNextNode() != null) {
        currentNode = currentNode.getNextNode();
    }
    currentNode.getPreviousNode().nextNode = null;
    countSize--;
    return true;
}

public boolean removeNodeByIndex(int index) {
    if (index > countSize - 1) {
        return false;
    }
    if (index == 0) {
        return this.removeFirst();
    } else if (index == countSize - 1) {
        return this.removeLast();
    } else {
        Node<T> currentNode = this.searchNodeByIndex(index);
        currentNode.getPreviousNode()
                .setNextNode(currentNode.getNextNode());
        currentNode.getNextNode().setPreviousNode(
                currentNode.getPreviousNode());
        countSize--;
        return true;
    }

}

public boolean removeNodeByData(T var) {
    if (this.isEmpty()) {
        return false;
    }
    Node<T> currentNode = searchNodeByData(var);
    if (null == currentNode) {
        return false;
    }
    if (currentNode.getNextNode() != null
            && currentNode.getPreviousNode() != null) {
        currentNode.getNextNode().setPreviousNode(
                currentNode.getPreviousNode());
        currentNode.getPreviousNode()
                .setNextNode(currentNode.getNextNode());
        countSize--;
    } else if (currentNode.getNextNode() != null
            && currentNode.getPreviousNode() == null) {
        currentNode.getNextNode().prevNode = null;
        countSize--;
    } else {
        currentNode.getPreviousNode().nextNode = null;
        countSize--;
    }

    return true;
}

public Node<T> searchNodeByData(T var) {
    if (this.isEmpty()) {
        return null;
    }
    if (var == root.getData()) {
        return root;
    }
    Node<T> currentNode = root;
    while (currentNode.getNextNode() != null) {
        currentNode = currentNode.getNextNode();
        if (var == currentNode.getData()) {
            return currentNode;
        }
    }
    return null;
}

public Node<T> searchNodeByIndex(int index) {
    if (this.isEmpty() || index > countSize - 1) {
        return null;
    }
    int count = 0;
    Node<T> currentNode = root;
    while (currentNode.getNextNode() != null) {
        if (count == index) {
            break;
        }
        currentNode = currentNode.getNextNode();
        count++;
    }
    return currentNode;
}

class Node<T> {
    private Node<T> prevNode;
    private Node<T> nextNode;
    T data;

    public Node() {
    }

    public Node(T var) {
        this.data = var;
    }

    public boolean setData(T var) {
        this.data = var;
        return true;
    }

    public T getData() {
        return this.data;
    }

    private void setNextNode(Node<T> n) {
        if (null != this.nextNode) {
            this.nextNode.prevNode = n;
            n.nextNode = this.nextNode;
        }
        this.nextNode = n;
        n.prevNode = this;
    }

    private void setPreviousNode(Node<T> n) {
        if (null != this.prevNode) {
            n.prevNode = this.prevNode;
            this.prevNode.nextNode = n;
        }
        this.prevNode = n;
        n.nextNode = this;

    }

    private Node<T> getNextNode() {
        if (null != this.nextNode) {
            return this.nextNode;
        }
        return null;

    }

    private Node<T> getPreviousNode() {
        if (null != this.prevNode) {
            return this.prevNode;
        }
        return null;
    }

}
}

Could someone help me out about which style should be used with? I am not so professional in Java, so I cannot distinguish the main difference between these two styles. Should I choose the one with the most functions inside the Node class or the other one?

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Singly link or doubly link?

The choice of implementing a linked list as singly-linked or doubly-linked is not a matter of "style", it's a matter of requirements. A doubly-linked list is useful when you need to manipulate both ends of the list.

And yes, you should use a generic node so that you can store any kind of object in the list.

Cleaning up LinkNode.Node

The class Node nested in LinkNode should be private static. Private, to hide this implementation detail from the outside, and static, because the class doesn't need to access data in the enclosing class.

Since Node.data never changes, it can be final. To make that work, you'll need to rework the constructors:

public Node() {
    this.data = null;
}

public Node(String data) {
    this.data = data;
}

The originals were very badly written:

public Node() {
}

public Node(String data) {
    this();
    this.setData(data);
}

public void setData(String data) {
    this.data = data;
}

This is bad because:

  • A method with an empty body is always a bad sign
  • Calling this() from the other constructor is pointless
  • A constructor should not call methods that can be overridden in children
  • setData is not used anywhere else, and certainly it should not be public. The way I rewrote the constructors above makes this method completely unnecessary.

This method is bad in many ways:

public boolean search(String data) {
    if (data == this.data) {
        return true;
    } else {
        if (this.nextNode == null) {
            return false;
        } else {
            return this.nextNode.search(data);
        }
    }
}

Normally you should not compare objects using ==. This expression will only be true of the instances on the left and the right side are the same instance. You should use .equals() instead.

The else branch can be simplified to this:

return this.nextNode != null && this.nextNode.search(data);

Also, since the method returns a boolean, the name "contains" would be more natural instead of "search". Later I noticed the "isContain" method, which is completely unnecessary, since it simply delegates to "search".

Avoid random access of elements in a linked list

Do not iterate over a linked list like this:

for(int i = 0; i < testList.size(); i++){
    if(testList.get(i).equals("...")) {
        // ...
    }
}

Random access of list elements like this (with .get(i)) is inefficient with lists. Use a ListIterator instead, like this:

ListIterator<String> iter = testList.listIterator();
while (iter.hasNext()) {
    String item = iter.next();
    if (item.equals("0123456") || item.equals("012345678")) {
        iter.remove();
    }
}

Possible simplifications

Instead of this:

private Node<T> getRootNode() {
    if (null != this.root) {
        return this.root;
    }
    return null;
}

This is exactly the same but much shorter and clearer:

private Node<T> getRootNode() {
    return this.root;
}

Instead of this:

boolean isDeleted = false;
if (this.data.equals(data)) {
    previousNode.nextNode = this.nextNode;
    isDeleted = true;
} else {
    if (this.nextNode != null) {
        this.nextNode.delete(this, data);
    }
}
return isDeleted;

You can simplify by using an early return:

if (this.data.equals(data)) {
    previousNode.nextNode = this.nextNode;
    return true;
}
if (this.nextNode != null) {
    this.nextNode.delete(this, data);
}
return false;

Naming

The method name printNode is misleading: it suggests printing a single node, but it prints the entire linked list.

StringBuilder is recommended instead of StringBuffer

Unless you have a specific requirement to use StringBuffer, use StringBuilder instead.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for helping me out of this confusion, really appreciate it. \$\endgroup\$
    – TerryZ
    Jan 27, 2015 at 1:47

Your Answer

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

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