Double Linked List and Iterator

Question

Does anyone know how to write a generic double singly linked list with an iterator?

Answer 1

coip wrote, "Josh Greig I sent u a private message but Solo doesnt allow me to send the link. I attach my code here: https://repl.it/repls/AgreeableUnwelcomeInversion#Main.java

these methods dont work: retrieveFirstElement(), retrieveLastElement(), and iterator()"

Answer:
I found a few problems with your code. The first problem was that you had the parameter order to the Node constructor inconsistent with the parameter list in the constructor. Below is the fixed version:

private void addBtw(T e, Node<T> preElement, Node<T> nextElement)
{
Node<T> newest = new Node<>(e, nextElement, preElement);
/**** next should be before pre. You had preElement, nextElement originally. ****/
preElement.setNext(newest);
nextElement.setPrev(newest);
size++;
}

I also ran into some problems with your iterator. I removed index and lastNode because they weren't needed. The lastNode, and template symbol from the outer class was accessible so index and some occurences of T weren't needed. I added a constructor so the iterator would start at the first node in the list. The original code had no constructor so it was pointing at just a bunch of nulls which wasn't a good place to start.

{
return new ListIterator();
}

class ListIterator implements Iterator<T>
{
protected Node<T> currentNode;

ListIterator() {
currentNode = head.next;
}

@Override
public boolean hasNext()
{
return currentNode != tail;
}

@Override
public T next()
{
if(!hasNext())
throw new NoSuchElementException();
T item = currentNode.element;
currentNode = currentNode.next;
return item;
}
}

Answer 2

Yes.

Some important details aren't perfectly clear in your question, though.

What do you mean by "generic double singly linked list"? A singly linked list will have a next but not a previous or a back link on every node. Will this "double singly linked list" have a back or previous link?

A doubly linked list would have a back or previous link on each node. Do you mean "double" as in each node holds a double data type value? If each node has a double number in it, what do you mean by "generic"? "generic" usually means you're using templated types.

If you just want a linked list and don't really need to implement it from scratch, check the java.util.LinkedList class: https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/LinkedList.html

Answer 3

coip

You can refer this code if you like.
In that code I have done Double LinkedList.

Note : only Add and Iterate in DoublyLinkedList.

https://code.sololearn.com/c1h675adCP47/?ref=app

Answer 4

Josh Greig like this:

public class BasicDoubleLinkedList <T> implements Iterable<T>

it is Double Linkedlist data structure and stores objects type generic T.

Answer 5

Josh Greig could u help me take a look on my java file? it doesnt work

Answer 6

Josh Greig I sent u a private message but Solo doesnt allow me to send the link.

these methods dont work: retrieveFirstElement(), retrieveLastElement(), and iterator()

Answer 7

coip, I tested your code with the following Tester class. To run with assertions enabled, include the -ea argument in the command like: java -ea Tester

You might be able to further test and refine your code by expanding these tests.

import java.util.*;

public class Tester
{

public static void main(String a[])
{
BasicDoubleLinkedList<Double> l = new BasicDoubleLinkedList<Double>();
assert l.getSize() == 0;
assert l.getFirst() == null;
assert l.getLast() == null;
assert l.toArrayList().size() == 0;

l.addToEnd(1.0);
assert l.getSize() == 1;
assert l.getFirst() == 1.0;
assert l.getLast() == 1.0;
assert l.toArrayList().size() == 1;

l.addToFront(2.0);
assert l.getSize() == 2;
assert l.getFirst() == 2.0;
assert l.getLast() == 1.0;
assert l.toArrayList().size() == 2;

l.addToFront(4.5);
assert l.getSize() == 3;
assert l.getFirst() == 4.5;
assert l.getLast() == 1.0;
assert l.toArrayList().size() == 3;

Iterator<Double> it = l.iterator();
assert it.hasNext();
assert it.next() == 4.5;
assert it.hasNext();
assert it.next() == 2.0;
assert it.hasNext();
assert it.next() == 1.0;
assert !it.hasNext();

Double d = l.retrieveFirstElement();
assert d == 4.5;
assert l.getSize() == 2;
assert l.getFirst() == 2.0;
assert l.getLast() == 1.0;
assert l.toArrayList().size() == 2;

d = l.retrieveLastElement();
assert d == 1.0;
assert l.getSize() == 1;
assert l.toArrayList().size() == 1;

d = l.retrieveLastElement();
assert d == 2.0;
assert l.getSize() == 0;
assert l.toArrayList().size() == 0;
}
}

Answer 8

thank you so much Josh Greig

Answer 9

LinkedList<Double> dq = new LinkedList<Double>();
//creating list with double values...

Iterator i = dq.iterator(); //iterator for list.

For double linkedList add deque instead of linkedList. Is this what you looking?

Answer 10

coip wrote: "Josh Greig like this:
public class BasicDoubleLinkedList <T> implements Iterable<T>
it is Double Linkedlist data structure and stores objects type generic T."

Answer:
coip, java.util.LinkedList implements Iterable<T> so you can use that if there is no requirement to write this from scratch.

Iterable iterates in only one direction, though. It has next() and hasNext() methods but no previous() and hasPrevious() methods. A singly linked list would be sufficient to implement a linked list with the Iteratable interface.

ListIterator( https://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html ) makes use of the extra power of a doubly linked list.

LinkedList also has a listIterator method that gives you that doubly-linked-list-style iterator that can iterate in both directions. https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/LinkedList.html#listIterator(int)

Answer 11

coip, where is your Java file? I don't see anything related to linked lists in your published codes at https://www.sololearn.com/Profile/16953552/.