Java 双向链表

import java.util.*;

public class DoublyLinkedList {
//overview: a list that is doublylinked

private ListNode firstNode;
private ListNode lastNode;

//constructors:

public DoublyLinkedList(){
//EFFECTS: initialize this to be empty
firstNode = null;
lastNode = null;
}

//methods:

public synchronized void insertAtFront(Object o){
//EFFECTS: add o to the front of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
firstNode = new ListNode(o , firstNode , lastNode);
lastNode.nextNode = firstNode;
}
}

public synchronized void insertAtBack(Object o){
//EFFECTS: add o to the back of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
lastNode = lastNode.nextNode = new ListNode(o , lastNode , firstNode);
firstNode.prevNode = lastNode;
}
}

public synchronized Object removeFromFront() throws EmptyListException{
//EFFECTS: remove the first node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
firstNode = firstNode.nextNode;
firstNode.prevNode = lastNode;
firstNode.nextNode = firstNode;
}
}
return o;
}

public synchronized Object removeFromBack() throws EmptyListException{
//EFFECTS: remove the last node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
lastNode = lastNode.prevNode;
lastNode.nextNode = firstNode;
firstNode.prevNode = lastNode;
}
}
return o;
}

public synchronized Set LocalMaximum(){
//EFFECTS: 返回一个Set，其中每个元素为位置信息，在该位置处的链表元素值为极大值
//极大值是指该元素不小于其直接前驱及直接后继元素
ListNode current = firstNode;
Set a = null ;
int n = 0;
while(current.nextNode != firstNode){
if(Integer.parseInt(current.data.toString()) >= Integer.parseInt(current.prevNode.data.toString()) &&
Integer.parseInt(current.data.toString()) >= Integer.parseInt(current.nextNode.data.toString()))
a.add(new Integer(n));
n++;
}
return a;
}

public Iterator iterator(int direction) throws Exception{
//EFFECTS: if direction is 0 return a generator that will produce all elements of this from the first node to the last one
//else if direction is 0 return a generator that will produce all elements of this from the last node to the first one
//REQUIRES: this must not be modified while the generator is in use
if(direction == 0){
return new fl(this);
}
else if(direction == 1){
return new lf(this);
}
else{
throw new Exception("Enter the right direction!");
}
}
//inner class

private static class fl implements Iterator{
//overview: from first to last

private ListNode current;
private DoublyLinkedList y;

//constructors:

public fl(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.firstNode;
}

//methods:

public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.lastNode)
return false;
else
return true;
}

public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.lastNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.nextNode;
return current;
}
}
public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}

//end methods

//end constructors

}//end class

private static class lf implements Iterator{
//overview: from last to first

private ListNode current;
private DoublyLinkedList y;

//constructors:

public lf(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.lastNode;
}

//methods:

public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.firstNode)
return false;
else
return true;
}

public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.firstNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.prevNode;
return current;
}
}

public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}

//end methods

// end constructors

}//end class

public synchronized boolean isEmpty(){
//EFFECTS: if this is not empty retutn true else return false
return firstNode == null;
}
//end methods

//end constructors

}//end class

class ListNode{
//overview: ListNode is the node of a list

Object data;
ListNode nextNode;
ListNode prevNode;

//constructors:

public ListNode(Object o){
//EFFECTS: initialize this to be a node like(o , null)
this( o , null , null);
}

public ListNode(Object o , ListNode node1 , ListNode node2){
//EFFECTS: initialize this to be a node like(node1 , o , node2)
data = o ;
nextNode = node1;
prevNode = node2;
}

//methods:

Object getObject(){
//EFFECTS: return the object of this
return data;
}

ListNode getNext(){
//EFFECTS: return the next node of this
return nextNode;
}

ListNode getPrev(){
//EFFECTS: return the prev node of this
return prevNode;
}

//end methods

//end constructors

}//end class

class EmptyListException extends RuntimeException {

//constructors:
public EmptyListException(){
//EFFECTS: initialize an EmptyListException
super( "The list is empty" );
}

} // end class

曾经自己编过,好像...贴给你了..

实现什么东西?什么要求都不说,这样问问题...