Can’t access my linked list methods and can’t iterate trough it

Tags: , ,



So im following along this playlist about data structures and in this video to conclude the linked list part, the professor explain we need an inner class called IteratorHelper.

Video: https://www.youtube.com/watch?v=bx0ebSGUKto&list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk&index=21

This is the code in my github with the linked list implementation and the main class called tester: https://github.com/Ghevi/Algos-DataStructures/tree/master/src/com/ghevi/ads/linkedlists

The problem is that the tester class can’t compile. If I instantiate the linked list as an ListIterator i can’t access its methods. I also can’t iterate trough it regardless of having the IteratorHelper inner class. In the video he writes “implements ListI<>” is just a shorter version for ListIterator<>? Sorry im just a beginner.

package com.ghevi.ads.linkedlists;

import java.util.ListIterator;

public class Tester {

    public static void main(String[] args) {

        ListIterator<Integer> list = new LinkedList<Integer>();
        int n = 10;

        for (int i = 0; i < n; i++)
            list.addFirstWithTail(i);


        int removedFirst = list.removeFirst();
        int removedLast = list.removeLast();

        for(int x : list){
            System.out.println(x);
        }
    }
}

Answer

The video is not very clear, but basically LinkedList should implement Iterable, not ListIterator. IteratorHelper should implement ListIterator (see 4:20 timestamp).

Here’s the fixed code:

package linkedlists;

import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

// Notes at Notes/Singly LinkedList.txt

public class LinkedList<E> implements Iterable<E> {

    @Override
    public Iterator<E> iterator() {
        return new IteratorHelper();
    }

    class IteratorHelper implements ListIterator<E>{

        Node<E> index;

        public IteratorHelper(){
            index = head;
        }

        // Return true if there is an element to return at the pointer
        @Override
        public boolean hasNext() {
            return (index != null);
        }

        // Return the element where the pointer is and mover the pointer to the next element
        @Override
        public E next() {
            if(!hasNext())
                throw new NoSuchElementException();

            E val = index.data;
            index = index.next;

            return val;
        }

        @Override
        public boolean hasPrevious() {
            return false;
        }

        @Override
        public E previous() {
            return null;
        }

        @Override
        public int nextIndex() {
            return 0;
        }

        @Override
        public int previousIndex() {
            return 0;
        }

        @Override
        public void remove() {

        }

        @Override
        public void set(E e) {

        }

        @Override
        public void add(E e) {

        }

        /* For version older than java 1.8
        public void remove(){
            throw new UnsupportedOperationException();
        }

        public void forEachRemaining(){};
        */

    } // inner class (can only be accessed by the outer class)

    class Node<E> {

        E data;
        Node<E> next;

        public Node(E obj){
            data = obj;
            next = null;
        }
    } // inner class (can only be accessed by the outer class)

    private Node<E> head;
    private Node<E> tail;
    private int currentSize;

    public LinkedList(){
        head = null;
        tail = null;
        currentSize = 0;
    }

    public void addFirst(E obj){
        Node<E> node = new Node<E>(obj);

        // The order of these 2 lines is fundamental
        node.next = head;
        head = node;

        currentSize++;
    }

    public void addFirstWithTail(E obj){
        Node<E> node = new Node<E>(obj);

        if(head == null){
            head = tail = node;
            return;
        }

        // The order of these 2 lines is fundamental
        node.next = head;
        head = node;

        currentSize++;
    }

    // O(n)
    public void slowAddLast(E obj){
        Node<E> node = new Node<E>(obj);

        if(head == null){
            head = tail = node;
            currentSize++;
            return;
        }

        Node<E> tmp = head;

        while(tmp.next != null){
            tmp = tmp.next;
        }

        tmp.next = node;
        currentSize++;
    }

    // O(1)
    public void fasterAddLast(E obj){
        Node<E> node = new Node<E>(obj);

        if(head == null){
            head = tail = node;
            currentSize++;
            return;
        }

        tail.next = node;
        tail = node;

        currentSize++;
    }

    public E removeFirst(){

        if(head == null){
            return null;
        }

        E tmp = head.data;

        if(head == tail){
            head = tail = null;
        } else {
            head = head.next;
        }

        currentSize--;
        return tmp;
    }

    public E removeLast(){
        if(head == null){
            return null;
        }

        if(head == tail){
            return removeFirst();
        }

        Node<E> current = head; // Can also write Node<E> current = head, previous = null;
        Node<E> previous = null;

        while(current != tail){
            // The order is crucial
            previous = current;
            current = current.next;
        }

        previous.next = null;
        tail = previous;
        currentSize--;

        return current.data;
    }


    public E findAndRemove(E obj){
        Node<E> current = head, previous = null;

        // In an empty list current = null so we skip to the last line
        while(current != null){
            if(((Comparable<E>)obj).compareTo(current.data) == 0){

                // Beginning or single element
                if(current == head)
                    return removeFirst();

                // Ending of the list
                if(current == tail)
                    return removeLast();

                currentSize--;

                // Removing the reference to the node to delete
                previous.next = current.next;

                return current.data;
            }
            previous = current;
            current = current.next;
        }
        // Node not found
        return null;
    }

    public boolean contains(E obj){
        Node<E> current = head;

        while(current != null) {
            if(((Comparable<E>) obj).compareTo(current.data) == 0)
                return true;

            current = current.next;
        }
        return false;
    }

    public E peekFirst(){
        if(head == null)
            return null;

        return head.data;
    }

    public E peekLast(){
        if(tail == null)
            return null;

        return tail.data;
    }



}

The interface methods hasPrevious, next, etc… have been moved into the IteratorHelper class which implements Iterator. The LinkedList class has an iterator() method because it implements Iterable. Now you can instantiate a LinkedList object and iterate over it in a for-loop:

package linkedlists;

public class Tester {

    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();
        int n = 10;

        for (int i = 0; i < n; i++)
            list.addFirstWithTail(i);


        int removedFirst = list.removeFirst();
        int removedLast = list.removeLast();

        for(int x : list){
            System.out.println(x);
        }
    }
}

Here’s a handy chart to remind you which class should have which functions: enter image description here

More on Iterable vs Iterator



Source: stackoverflow