Linked List Practice

LinkedList.java

package com.linkedlists;

public class LinkedList {

    Node head;

    // static so main can access the inner class
    static class Node {
        int data;
        Node next;

        // constructor
        Node(int d){
            data = d;
            next = null;
        }
    }

    // insert a node with some data into the list
    public static LinkedList insert(LinkedList list, int data) {
        // create new node with the data
        Node new_node = new Node(data);
        new_node.next = null;

        if (list.head == null) {
            list.head = new_node;
        } else {
            // if list is empty, make the node the head
            // else - insert node at the end of the list
            Node last = list.head;
            // update last if needed
            while (last.next != null) {
                last = last.next;
            }
            // now that you're at the last node, add the new node in front of it
            last.next = new_node;
        }
        return list;
    }

    public static LinkedList deleteLastInList(LinkedList list){
        // if empty just return list
        // otherwise - if the node in front of me has null in front of them
            // change my pointer to null so they go away

        if (list.head == null){
            return list;
        } else {
            // start at front of list
            Node current = list.head;
            // keep going through list
                // until I am one node away from null
            while (current.next.next != null){
                current = current.next;
            }
            // Change my next to null so we lose the last node
            current.next = null;
        }
        return list;
    }

    public static LinkedList addToFrontOfLinkedList(LinkedList list, int data){
        // create a new node
        Node new_node = new Node(10);

        // if list is empty, make new node the head
            // otherwise
            // don't lose your head! Set the new node's next to the head
            // so the prior head still points to the rest of the list
            // update the head to the new node so that's at the front
        if (list.head == null){
            list.head = new_node;
        } else {
            new_node.next = list.head;
            list.head = new_node;
        }
        return list;
    }

    public static void printList(LinkedList list){
        if (list.head == null){
            System.out.println("List is empty");
        } else {
            // iterate through list printing data
            Node current = list.head;
            System.out.println("LinkedList: ");
            while (current != null){
                System.out.println(current.data + " ");
                current = current.next;
            }
        }
    }

    public static LinkedList deleteByKey(LinkedList list, int valueToDelete){
        // if list is empty, return list;
        // if head is the value, update the head
        // iterate through list,
            // if next node's data is the value to be deleted
                // update current node's next to skip over the next item (next.next)
        if (list.head == null){
            return list;
        } else if (list.head.data == valueToDelete){
          // update the head to the next node
          list.head = list.head.next;
        } else {
            Node current = list.head;
            while (current != null){
                if (current.next.data == valueToDelete){
                    current.next = current.next.next;
                }
                current = current.next;
            }
        }
        return list;
    }

    public static boolean isInList(LinkedList list, int valueToFind){
        // if list is empty, return false
        // otherwise - iterate through list
        // if you find the value, return true;
        // if you go through whole list and didn't find it, return false
        if (list.head == null){
            return false;
        } else {
            // start at front of list
            Node current = list.head;
            while (current != null){
                if (current.data == valueToFind){
                    return true;
                } else {
                    current = current.next;
                }
            }
        }
        return false;
    }

    // Driver code
    public static void main(String[] args){
        LinkedList list = new LinkedList();

        // Insert the values
        list = insert(list, 1);
        list = insert(list, 2);
        list = insert(list, 3);
        list = insert(list, 4);
        list = insert(list, 5);
        list = insert(list, 6);
        list = insert(list, 7);
        list = insert(list, 8);
        list = insert(list, 8);


        // Print the LinkedList
        printList(list);
        deleteLastInList(list);
        printList(list);
        addToFrontOfLinkedList(list, 0);
        printList(list);
        System.out.println(isInList(list, 1));
        System.out.println(isInList(list, 999));
        deleteByKey(list, 8);
        System.out.println(isInList(list, 8));
        printList(list);

    }
}

Here are some comments for further improving this code.

• Lines 5, 9 and 10: think about which of these should be private, public or protected. Learn about what the default setting is for member variables of a class in Java.
• Your driver code, i.e. the main method should not be part of the LinkedList class. It should be outside. e.g. consider your linked list holds student records. Then the driver code, which is not part of the student record keeping class will be adding a new student (aka a new node behind the scenes).
• In your driver code: to make your code truly benefit from object-oriented design, don't pass the list as a parameter or return it back as a parameter. The code should look something like:

    LinkedList list = new LinkedList();
    // Insert the values
    list.insert(1);
    list.insert(2);

Accordingly, each method in the LinkedList class should be updating the head which is the member variable of the class.

• deleteLastInList could cause a null dereference on line 53. To avoid this, check if current.next is null before accessing current.next.next.
• Similarly, in deleteByKey on line 108, what if current.next is null? Also, could you condense this code by checking for current.data instead of current.next.data?
• In deleteByKey, if the value to delete is found at head, you delete the head node and return. However, if the value to delete is not found at head, you delete all nodes that have this value. Could you make this method consistent? Either delete all occurences of value found, or delete only the first occurence of the value found and then return (do not continue the loop).