How to write a method to find the Nth to last item in a singly linked list . The

Question

How to write a method to find the Nth to last item in a singly linked list. The list does not know nor provide a method to return its size.

How do I implement a generic linked list that is only singly linked. That is, each node only knows about the next node. Naming it SinglyLinkedList. The linked list will have a head and a tail node which contain no data. It will not keep track of its size. It will implement the Iterable<T> interface, and I will need to write an inner class that implements the Iterator<T> interface. The inner class is named SinglyLinkedListIterator. It is recommended that I also have an inner class Node that defines your node objects.

The linked list must provide the following methods:

public void add(AnyType element)
public void remove(AnyType element)

public void clear()
public AnyType getNthToLast(int n)
public SinglyLinkedListIterator iterator()

The method add() adds the new element to the end of the list. The method remove() removes the first Node from the list that contains element.
clear() removes all elements from the list. getNthToLast() returns the Nth to last element in the list. For example, in the list of numbers 5 4 3 2 1, 2 is the 2nd to last element, 3 is the 3rd to last, and so on. iterator() returns an instance of the SinglyLinkedListIterator.

SinglyLinkedListIterator must implement the following 4 methods.

public boolean hasNext()
public AnyType next()
public void remove()
public void add(AnyType element)

hasNext() returns true if there is a next element in the list, and false otherwise. next() moves the iterator to point to the next Node in the list and returns the element held by that node. If next() is called and there is no next element, next() must throw a NoSuchElementException. The iterator’s remove() removes from the list the node currently pointed to by the Iterator (This is the element last returned by next()). If a call to remove() attempts to remove the tail, remove() must throw an IllegalStateException. Likewise, the iterator’s method add() adds the new element to the list after the node the iterator currently points to.

Explanation / Answer

import java.util.Iterator;

import java.util.NoSuchElementException;

/**
*
* @author Sam
*/
public class SinglyLinkedList<T> implements Iterable<T> {
  
    class SinglyLinkedListIterator implements Iterator<T> {

        Node current, previous;
      
        @Override
        public boolean hasNext() {
            return current.next != null;
        }

        @Override
        public T next() {
            previous = current;
            current = current.next;
            if (current == null)
                throw new NoSuchElementException();
            return current.data;
        }
      
        @Override
        public void remove() {
            previous.next = current.next;
            if (current.next == null)
                throw new IllegalStateException();
        }
      
        public void add(T element) {
           current.next = new Node(element, current.next);
          
        }

    }

    class Node {
        T data;
        Node next;

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

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

        public void setNext(Node next) {
            this.next = next;
        }
      
    }
  
    Node head = new Node(null, null),
            tail = new Node(null, null);
  
    @Override
    public Iterator<T> iterator() {
        SinglyLinkedListIterator iterator = new SinglyLinkedListIterator();
        iterator.current = head;
        iterator.previous = null;
        return iterator;
    }
  
  

    public void add(T element) {
        if (tail == null)
            head = tail = new Node(element, null);
        else
            tail = tail.next = new Node(element, null);
    }
  
    public void remove(T element) {
        if (head == null)
            return;
        if (head.data.equals(element)) {
            head = head.next;
            return;
        }
        Node current = head;
        while (current.next != null) {
            if (current.next.data.equals(element))
                break;
            current = current.next;
        }
      
        if (current.next == null)
            return;
      
        current.next = current.next.next;
    }

    public void clear() {
        head = tail = null;
    }

    public T getNthToLast(int n) {
        T[] arr = (T[])new Object[n];
        int index = 0;
        Node current = head;
      
        while (current != null) {
            if (index == n)
                index = 0;
            arr[index ++] = current.data;
            current = current.next;
        }
      
        return arr[(index + 1) % n];
      
    }
  
}

I have checked the code twice and i felt it safe. If any bug is sppoted, kindly comment below so that I can look into that.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.