java在DoublyLinkedList上实现迭代器
这个问题已经被问过好几次了，但大多数都是不同的或ArrayList。这有点管用。迭代器iterate（）部分的递归调用失败了，但我不知道该怎么做
import java.util.*;
public class KWLinkedList<E> extends AbstractSequentialList<E> {
// Data Fields
/** A reference to the head of the list. */
private Node<E> head = null;
/** A reference to the end of the list. */
private Node<E> tail = null;
/** The size of the list. */
private int size = 0;
/** Next node link. */
private Node<E> nextNode = null;
private static KWLinkedList myList = new KWLinkedList();
//Methods
// Insert solution to programming exercise 4, section 8, chapter 2 here
public void addFirst(E obj){
if (head == null) {
head = new Node(obj);
tail = head;
tail.next = head;
size++;
} else {
head.prev = new Node(obj);
tail.next = head;
size++;
}
}
public Node<E> getFirst(){
if ( head == null) {
throw new NoSuchElementException("\n ERROR: List Is Empty! \n");
}
else {
return head;
}
}
public void addLast(E obj){
if (head == null){
addFirst(obj);
} else {
}
}
public Node<E> getLast(){
if (head == null){
throw new NoSuchElementException("\n ERROR: List Is Empty! \n");
}
return tail;
}
// Insert solution to programming exercise 3, section 8, chapter 2 here
// Return ListIterator that begins just before the first list element.
You can probably tell this was homework, why a teacher is making us write the whole iterator instead of using them in some effective way is not my idea of training. But there must be a reason. Anyway, that pretty much did do the trick, THANKS Thomas! @Override
public Iterator<E> iterator(){
Iterator<E> iter = new KWListIter(0);
return iter;
}
///////////// CORRECTED PART !!! //////////////////////////////
// Return ListIterator that begins just before the position index.
@Override
public ListIterator<E> listIterator(int index){
ListIterator<E> iter = new KWListIter(0);
return iter;
}
/**
* Add an item at the specified index.
* @param index The index at which the object is to be
* inserted
* @param obj The object to be inserted
* @throws IndexOutOfBoundsException if the index is out
* of range (i < 0 || i > size())
*/
@Override
public void add(int index, E obj) {
KWListIter iterator = new KWListIter(index);
iterator.add(obj);
}
/**
* Get the element at position index.
* @param index Position of item to be retrieved
* @return The item at index
*/
@Override
public E get(int index) {
return listIterator(index).next();
}
/**
* Return the size of the list
* @return the size of the list
*/
@Override
public int size() {
return size;
}
// Inner Classes
/**
* A Node is the building block for a double-linked list.
*/
private static class Node<E> {
/** The data value. */
private E data;
/** The link to the next node. */
private Node<E> next = null;
/** The link to the previous node. */
private Node<E> prev = null;
/**
* Construct a node with the given data value.
* @param dataItem The data value
*/
private Node(E dataItem) {
data = dataItem;
}
public String toString(){
return " Data: " + data;
}
} //end class Node
/** Inner class to implement the ListIterator interface. */
private class KWListIter implements ListIterator<E> {
/** A reference to the next item. */
private Node<E> nextItem;
/** A reference to the last item returned. */
private Node<E> lastItemReturned;
/** The index of the current item. */
private int index = 0;
/**
* Construct a KWListIter that will reference the ith item.
* @param i The index of the item to be referenced
*/
public KWListIter(int i) {
// Validate i parameter.
if (i < 0 || i > size) {
throw new IndexOutOfBoundsException(
"Invalid index " + i);
}
lastItemReturned = null; // No item returned yet.
// Special case of last item.
if (i == size) {
index = size;
nextItem = null;
} else { // Start at the beginning
nextItem = head;
for (index = 0; index < i; index++) {
nextItem = nextItem.next;
}
}
}
/**
* Construct a KWListIter that is a copy of another KWListIter
* @param other The other KWListIter
*/
public KWListIter (KWListIter other) {
KWListIter itr = new KWListIter(0);
itr.index = other.index;
itr.lastItemReturned = other.lastItemReturned;
itr.nextItem = other.nextItem;
}
/**
* Indicate whether movement forward is defined.
* @return true if call to next will not throw an exception
*/
@Override
public boolean hasNext() {
return nextItem != null;
}
/** Move the iterator forward and return the next item.
@return The next item in the list
@throws NoSuchElementException if there is no such object
*/
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
lastItemReturned = nextItem;
nextItem = nextItem.next;
index++;
return lastItemReturned.data;
}
/**
* Indicate whether movement backward is defined.
* @return true if call to previous will not throw an exception
*/
@Override
public boolean hasPrevious() {
return (nextItem == null && size != 0)
|| nextItem.prev != null;
}
/**
* Return the index of the next item to be returned by next
* @return the index of the next item to be returned by next
*/
@Override
public int nextIndex() {
return index;
}
/**
* Return the index of the next item to be returned by previous
* @return the index of the next item to be returned by previous
*/
@Override
public int previousIndex() {
return index - 1;
}
/**
* Move the iterator backward and return the previous item.
* @return The previous item in the list
* @throws NoSuchElementException if there is no such object
*/
@Override
public E previous() {
if (!hasPrevious()) {
throw new NoSuchElementException();
}
if (nextItem == null) { // Iterator past the last element
nextItem = tail;
} else {
nextItem = nextItem.prev;
}
lastItemReturned = nextItem;
index--;
return lastItemReturned.data;
}
/**
* Add a new item between the item that will be returned
* by next and the item that will be returned by previous.
* If previous is called after add, the element added is
* returned.
* @param obj The item to be inserted
*/
@Override
public void add(E obj) {
if (head == null) { // Add to an empty list.
head = new Node<E>(obj);
tail = head;
} else if (nextItem == head) { // Insert at head.
// Create a new node.
Node<E> newNode = new Node<E>(obj);
// Link it to the nextItem.
newNode.next = nextItem; // Step 1
// Link nextItem to the new node.
nextItem.prev = newNode; // Step 2
// The new node is now the head.
head = newNode; // Step 3
} else if (nextItem == null) { // Insert at tail.
// Create a new node.
Node<E> newNode = new Node<E>(obj);
// Link the tail to the new node.
tail.next = newNode; // Step 1
// Link the new node to the tail.
newNode.prev = tail; // Step 2
// The new node is the new tail.
tail = newNode; // Step 3
} else { // Insert into the middle.
// Create a new node.
Node<E> newNode = new Node<E>(obj);
// Link it to nextItem.prev.
newNode.prev = nextItem.prev; // Step 1
nextItem.prev.next = newNode; // Step 2
// Link it to the nextItem.
newNode.next = nextItem; // Step 3
nextItem.prev = newNode; // Step 4
}
// Increase size and index and set lastItemReturned.
size++;
index++;
lastItemReturned = null;
} // End of method add.
// Insert solution to programming exercise 1, section 8, chapter 2 here
@Override
public void remove(){
if (lastItemReturned == null) {
throw new IllegalStateException();
}
else if ( lastItemReturned.prev == null){
head = head.next;
lastItemReturned = head;
}
else if (lastItemReturned.next == null){
lastItemReturned.prev.next = null;
lastItemReturned = null;
}
else {
lastItemReturned.prev.next = lastItemReturned.next;
lastItemReturned.next.prev = lastItemReturned.prev;
lastItemReturned = lastItemReturned.next;
}
size--;
index--;
lastItemReturned = null;
}
// Insert solution to programming exercise 2, section 8, chapter 2 here
@Override
public void set(E newData){
if (lastItemReturned == null && head != null){
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node<E> (newData);
}
else if ( head == null || lastItemReturned.prev == null){
KWLinkedList.this.addFirst(newData);
}
else {
Node<E> temp = new Node<E>(newData);
lastItemReturned.prev.next = temp;
lastItemReturned.prev = temp;
}
}
} //end class KWListIter
// Insert solution to programming exercise 1, section 7, chapter 2 here
public int indexOf(KWLinkedList list, E target){
ListIterator<E> myIter = list.listIterator();
while (myIter.hasNext()) {
if(target.equals(myIter.next())) {
break;
}
}
return indexOf(myIter);
}
// Insert solution to programming exercise 2, section 7, chapter 2 here
public int lastIndexOf(KWLinkedList list, ListIterator<E> target){
ListIterator<E> myIter = list.listIterator();
int hold = -1;
while (myIter.hasNext()) {
if(target.equals(myIter.next())) {
hold = indexOf(myIter);
}
}
return hold;
}
// Insert solution to programming exercise 3, section 7, chapter 2 here
public ArrayList<Integer> indexOfMin(KWLinkedList list, ListIterator target){
ListIterator<E> myIter = list.listIterator();
ArrayList<Integer> indexArray = new ArrayList<>();
while (myIter.hasNext()) {
if(target.equals(myIter.next())) {
indexArray.add(indexOf(myIter));
}
}
return indexArray;
}
// Insert solution to programming exercise 1, section 6, chapter 2 here
// 1.a.
public void chapter2Sec6Exer1a(KWLinkedList linkedList){
String bill = "Bill";
linkedList.addFirst(bill);
}
//1.b.
public void chapter2Sec6Exer1b(KWLinkedList linkedList){
String sam = "Sam";
String sue = "Sue";
int holdIndex = linkedList.indexOf(linkedList, sam);
linkedList.add(holdIndex, sue);
}
//1.c.
public void chapter2Sec6Exer1c (KWLinkedList linkedList){
linkedList.remove("Bill");
}
//1d.
public void chapter2Sec6Exer1d (KWLinkedList linkedList){
String sam = "Sam";
boolean check = false;
check = linkedList.remove(sam);
if (check){
System.out.println( sam + " was removed from list.");
}
}
public static void main (String[] args){
myList.add("Tom");
myList.add("Dick");
myList.add("Harry");
myList.add("Sam");
displayList(myList);
}
public static void displayList(KWLinkedList myList){
Iterator i = myList.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
}
}
共 (0) 个答案