Implementing a Linked List in Java

Question

I am studying computer science and decided to implement a linked list from scratch for extra practice. To do so, I created a Node class which simply holds an integer, and wrapped the Nodes in a LinkedList class which adds, removes, and returns Nodes. I am wondering how I did, what I can add, and what I can do better.

package LinkedList;

public class Node {

    private int data;
    private Node next;
    private Node previous;

    public Node(int d, Node previous) {
        this.data = d;
        this.next = null;
        this.previous = previous;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node getPrevious() {
        return previous;
    }

    public void setPrevious(Node previous) {
        this.previous = previous;
    }

    public int getData() {
        return data;
    }

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

}

package LinkedList;

public class LinkedList {

    private Node head;
    private Node last;
    private int numNodes;

    public LinkedList(Node head) {
        this.head = head;
        this.last = head;
        numNodes = 1;
    }

    public int getNumNodes() {
        return numNodes;
    }

    public void addNodeToEnd(Node toAdd) {
        Node n = head;
        while(n.getNext() != null) {
            n = n.getNext();
        }
        n.setNext(toAdd);
        toAdd.setPrevious(n);
        this.last = toAdd;
        numNodes++;
    }

    public void addNodeToEnd(int data) {
        Node toAdd = new Node(data, null);
        addNodeToEnd(toAdd);
    }

    public void addNodeToFront(Node node) {
        head.setPrevious(node);
        node.setNext(head);
        this.head = node;
        numNodes++;
    }

    public void addNodeToFront(int data) {
        Node toAdd = new Node(data, null);
        addNodeToFront(toAdd);
    }

    public boolean addNodeAfterData(Node toAdd, int data) {
        Node n = head;
        while(n.getNext() != null) {
            if(n.getData() == data) {
                toAdd.setPrevious(n);
                toAdd.setNext(n.getNext());
                n.setNext(toAdd);
                numNodes++;
                return true;
            }
            n = n.getNext();
        }
        return false;
    }

    public boolean addNodeAfterData(int data, int dataSearch) {
        Node toAdd = new Node(data, null);
        return addNodeAfterData(toAdd, dataSearch);
    }

    public boolean addNodeAtIndex(int index, Node toAdd) {
        if(((index - numNodes) > 1) || index < 0) {
            return false;
        }
        if(index == 0) {
            addNodeToFront(toAdd);
            return true;
        }
        int counter = 0;
        Node n = head;
        while(n.getNext() != null) {
            n = n.getNext();
            counter++;
            if(counter == index) {
                toAdd.setPrevious(n.getPrevious());
                toAdd.setNext(n);
                n.getPrevious().setNext(toAdd);
                numNodes++;
                return true;
            }
        }
        return false;
    }

    public boolean addNodeAtIndex(int data, int index) {
        Node toAdd = new Node(data, null);
        return addNodeAtIndex(index, toAdd);
    }

    public void printList() {
        Node n = head;
        System.out.println("");
        while(n.getNext() != null) {
            System.out.print(n.getData());
            System.out.print(", ");
            n = n.getNext();
        }
        System.out.print(n.getData());
    }

    public boolean removeByData(int data) {
        Node n = head;
        if(head.getData() == data) {
            this.head = head.getNext();
            this.head.setPrevious(null);
            numNodes--;
            return true;
        }
        while(n.getNext() != null) {
            if(n.getData() == data) {
                n.getPrevious().setNext(n.getNext());
                n.getNext().setPrevious(n.getPrevious());
                numNodes--;
                return true;
            }
            n = n.getNext();
        }
        return false;
    }

    public boolean removeByIndex(int index) {
        if(index < 0 || index > numNodes) {
            return false;
        }
        if(index == 0) {
            if(this.head.getNext() != null) {
                this.head = head.getNext();
                this.head.setPrevious(null);
                numNodes--;
                return true;
            } else {
                return false;
            }
        }
        int counter = 0;
        Node n = head;
        while(n.getNext() != null) {
            if(counter == index) {
                n.getPrevious().setNext(n.getNext());
                n.getNext().setPrevious(n.getPrevious());
                numNodes--;
                return true;
            }
            counter++;
            n = n.getNext();
        }
        return false;
    }

}

One thing I would like to implement but am unsure how is a good way for the user to access the data indexed within the list. I am not sure how linked lists are typically used to lookup information.

Answer 1

Just a few bugs you might encounter:

Constructor and get num nodes

For the constructor of the LinkedList, you assume that the node given as an arguement is a single node; but the user could have taken the head from another linked list and passed it to this new linkedlist in it's constructor and you will still return the size of the new linked list as 1

Adding nodes to the end

Why do you use a while loop here? You already have the end and it's called tail, so why not just use that?

Adding node after data

You didn't account for when the linked list contains only one node and the head contains the data you are trying to add

Add node at index and remove by Index

You have this condition if(((index - numNodes) > 1) { return false; }, but you also allow this if(index == 0). If your linked list has size 2, and you decide that the allowed indexes start at 0, then if the user supplies 2 as the index, your function will not catch this and end up accessing invalid memory

One thing I would like to implement but am unsure how is a good way for the user to access the data indexed within the list. I am not sure how linked lists are typically used to lookup information. Any help is much appreciated! Thanks.

There is no fast way to do this, the typical way to find information within linked lists is usually to step through each node one by one and look at the data it contains, if it is what you are looking for you give that to the user, otherwise you keep stepping until the end of the list is reached and in which case you say tell the user that the information is not contained within the list.

Another way is to implement the linked list using arrays, then if the user supplies an index to you, you can simply look it up in the array and return that value

Answer 2

Hide the Node class

Users shouldn't be thinking about Nodes. They should just be thinking about lists and the items in them. The node is an implementation detail. I would move the Node class inside LinkedList and mark it private, and remove (or make private) all of the methods that operate on that type. You already had the foresight to add overloaded versions that operate on the data directly, so this is easy.

With Node private and internal, you can get rid of the getters/setters and have LinkedList operate on the fields directly. Node should just be a dumb container for the data and pointers.

Make it generic

There's nothing specific about ints in this code. You're not doing arithmetic with them, passing them to other code, or anything at all really. All you're doing is storing them. So make LinkedList and Node generic over any type T.

Unfortunately, Java treats primitives and objects differently so you won't be able to make a LinkedList<int>, but if you don't mind autoboxing you can make a LinkedList<Integer> and it'll work mostly the same.

Implement List

This is just a "nice to have", but you can implement the java.util.List interface so you can pass your class to other code. You're already doing the bulk of it, the only nontrivial thing will be the iterator.