Java Using Nodes with LinkedList

Question

I've been working through some standard coding interview questions from a book I recently bought, and I came across the following question and answer:

Implement an algorithm to find the nth to last element in a linked list.

Here's the provided answer:

public static LinkedListNode findNtoLast(LinkedListNode head, int n) { //changing LinkedListNode to ListNode<String>
        if(head == null || n < 1) {
            return null;
        }
        LinkedListNode p1 = head;
        LinkedListNode p2 = head;
        for(int j = 0; j < n-1; ++j) {
            if(p2 == null) {
                return null;
            }
            p2 = p2.next;
        }
        if(p2 == null) {
            return null;
        }
        while(p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

I understand the algorithm, how it works, and why the book lists this as its answer, but I'm confused about how to access the LinkedListNodes to send as an argument to the method. I know that I'd have to create a LinkedListNode class (since Java doesn't already have one), but I can't seem to figure out how to do that. It's frustrating because I feel like I should know how to do this. Here's something that I've been working on. I'd greatly appreciate any clarification. You can expand/comment on my code or offer your own alternatives. Thanks.

class ListNode<E> {
    ListNode<E> next;
    E data;

    public ListNode(E value) {
        data = value;
        next = null;
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

public class MyLinkedList<E> extends LinkedList {
    LinkedList<ListNode<E>> list;
    ListNode<E> head;
    ListNode<E> tail;
    ListNode<E> current;
    ListNode<E> prev;

    public MyLinkedList() {
        list = null;
        head = null;
        tail = null;
        current = null;
        prev = null;
    }

    public MyLinkedList(LinkedList<E> paramList) {
        list = (LinkedList<ListNode<E>>) paramList; //or maybe create a loop assigning each ListNode a value and next ptr
        head = list.getFirst();
        tail = list.getLast(); //will need to update tail every time add new node
        current = null;
        prev = null;
    }

    public void addNode(E value) {
        super.add(value);
        //ListNode<E> temp = tail;
        current = new ListNode<E>(value);
        tail.setNext(current);
        tail = current;
    }

    public LinkedList<ListNode<E>> getList() {
        return list;
    }

    public ListNode<E> getHead() {
        return head;
    }

    public ListNode<E> getTail() {
        return tail;
    }

    public ListNode<E> getCurrent() {
        return current;
    }

    public ListNode<E> getPrev() {
        return prev;
    }


}

How can the LinkedListNode head from a LinkedList?

Update: I think part of my confusion comes from what to put in the main method. Do I need to create a LinkedList of ListNode? If I do that, how would I connect the ListNodes to each other? How would I connect them without using a LinkedList collection object? If someone could show me how they would code the main method, I think that would put things into enough perspective for me to solve my issues. Here's my latest attempt at the main method:

public static void main(String args[]) {
        LinkedList<ListNode<String>> list = new LinkedList<ListNode<String>>();
        //MyLinkedList<ListNode<String>> list = new MyLinkedList(linkedList);
        list.add(new ListNode<String>("Jeff"));
        list.add(new ListNode<String>("Brian"));
        list.add(new ListNode<String>("Negin"));
        list.add(new ListNode<String>("Alex"));
        list.add(new ListNode<String>("Alaina"));
        int n = 3;
        //ListIterator<String> itr1 = list.listIterator();
        //ListIterator<String> itr2 = list.listIterator();
        LinkedListNode<String> head = new LinkedListNode(list.getFirst(), null);
        //String result = findNtoLast(itr1, itr2, n);
        //System.out.println("The " + n + "th to the last value: " + result);
        //LinkedListNode<String> nth = findNtoLast(list.getFirst(), n);
        ListNode<String> nth = findNtoLast(list.getFirst(), n);
        System.out.println("The " + n + "th to the last value: " + nth);
    }

In an attempt to connect the nodes without using a custom linked list class, I have edited my ListNode class to the following:

class ListNode<E> {
    ListNode<E> next;
    ListNode<E> prev; //only used for linking nodes in singly linked list
    ListNode<E> current; //also only used for linking nodes in singly linked list
    E data;
    private static int size = 0;

    public ListNode() {
        data = null;
        next = null;
        current = null;
        if(size > 0) { //changed from prev != null because no code to make prev not null
            prev.setNext(this);
        }
        size++;
    }
    public ListNode(E value) {
        data = value;
        next = null;
        current = this;
        System.out.println("current is " + current);
        if(size > 0) {
            prev.setNext(current);//this line causing npe
        }
        else
        {
            prev = current;
            System.out.println("prev now set to " + prev);
        }
        size++;
        System.out.println("after constructor, size is " + size);
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
        current = this;
        if(size > 0) {
            prev.setNext(this);
        }
        size++;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

As is right now, the program will run until it reaches prev.setNext(current); in the single argument constructor for ListNode. Neither current nor prev are null at the time this line is reached. Any advice would be greatly appreciated. Thanks.

If the method wasn't static, it seems, that it is part of a LinkedList class. Then it would be able to access the (assumed private) field head. — Markus Patt
– Markus Patt, Commented Dec 30, 2014 at 0:22
I see that you have subclassed java.util.LinkedList. It does not make a lot of sense to subclass and then implement your own node class. LinkedList already has a private class called Entry which is used for this purpose. As you mention you don't have access to it so you can't implement the algorithm you've shown using a LinkedList subclass. You've got to create your own as I've indicated in my answer. — sprinter
– sprinter, Commented Dec 31, 2014 at 4:32
You can see the source code for LinkedList at developer.classpath.org/doc/java/util/LinkedList-source.html if you are interested in seeing how it works. You'll see that it is actually a double linked list (next and prev references). This is necessary to allow items to be removed from the middle. — sprinter
– sprinter, Commented Dec 31, 2014 at 4:32

sprinter · Accepted Answer · 2014-12-31 04:02:10Z

2

You don't actually need a separate LinkedList class; the ListNode class is a linked list. Or, to state it differently, a reference to the head of the list is a reference to the list.

The use of head, tail, current, prev in the sample code you posted has come from a double-linked list which is a data type that has links in both directions. This is more efficient for certain types of applications (such as finding the nth last item).

So I would recommend renaming your ListNode class to LinkedList and renaming next to tail.

To add a new item to the list you need a method that creates a new list with the new item at it's head. Here is an example:

class LinkedList<E> {
    ...

    private LinkedList(E value, LinkedList<E> tail) {
        this.data = value;
        this.tail = tail;
    }

    public LinkedList<E> prependItem(E item) {
        return new LinkedList(item, this);
    }
}

Then to add a new item i to list you use list = list.prependItem(i);

If for some reason you need to always add the items to the end, then:

private LinkedList(E value) {
    this.data = value;
    this.tail = null;
}

public void appendItem(E item) {
    LinkedList<E> list = this;
    while (list.tail != null)
        list = list.tail;
    list.tail = new LinkedList<>(item);
}

However this is obviously pretty inefficient for long lists. If you need to do this then either use a different data structure or just reverse the list when you have finished adding to it.

Incidentally, an interesting side effect of this is that a reference to any item in the list is a reference to a linked list. This makes recursion very easy. For example, here's a recursive solution for finding the length of a list:

public int getLength(LinkedList list) {
    if (list == null) {
        return 0;
    } else {
        return 1 + getLength(list.getTail());
    }
}

And using this a simple (but very inefficient!) solution to the problem you provided - I've renamed the method to make its function more obvious:

public LinkedList getTailOfListOfLengthN(LinkedList list, int n) {
    int length = getLength(list);
    if (length < n) {
        return null;
    } else if (length == n) {
        return list;
    } else {
        return getTailOfLengthN(list.getTail(), n);
    }
}

And to reverse the list:

public LinkedList<E> reverse() {
    if (tail == null) {
        return this;
    } else {
        LinkedList<E> list = reverse(tail);
        tail.tail = this;
        tail = null;
        return list;
    }
}

As I hope you can see this makes the methods a lot more elegant than separating the node list classes.

edited Dec 31, 2014 at 4:02

answered Dec 30, 2014 at 0:46

sprinter

28.1k8 gold badges51 silver badges81 bronze badges

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

3 Comments

jeffkempf Over a year ago

Ok, so you're saying that my ListNode class is already a linked list. In that case, how would I connect the nodes together to form the list? Would I need to create a method in ListNode that connects current and tail, like I did in the addNode method of MyLinkedList? Also, what would your main method look like?

sprinter Over a year ago

I'll add a method to my answer for adding a new node to a list.

sprinter Over a year ago

Note that you don't need a reference to the tail unless you make a double linked list. For standard linked lists new items are pushed on the top (which is what makes them good candidates for implementing stacks).

Nicola Ferraro · Accepted Answer · 2014-12-30 00:24:09Z

0

Actually you have created a linked list with you class ListNode.

A linked list is made of a node and a reference to another linked list (see the recursion?).

answered Dec 30, 2014 at 0:24

Nicola Ferraro

4,2196 gold badges32 silver badges61 bronze badges

2 Comments

jeffkempf Over a year ago

if I were to use my ListNode class above, how would I be able to link the nodes together? Would I have to create a LinkedList of ListNode<E> elements? Do I need to create a tail node and a size int and run a for loop to link a node to its next node like so?:

jeffkempf Over a year ago

for(int i = 0; i < size-1; i++) { prev = prev.next; } prev.setNext(this);

Collectives™ on Stack Overflow

Java Using Nodes with LinkedList

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related