给你个以前练习的代码参考class ListNode{ // friendly data so class list can access it directly Object data; ListNode next;
ListNode(Object o) { data=o; next=null; }
// Constructor: Create a ListNode that refers to Object o and to the // next ListNode in the List. ListNode(Object o,ListNode nextNode) { data=o; next=nextNode; }
// Return the Object in this node Object getObject() { return data; }
ListNode getnext() { return next; } } // Class List definition class List{ private ListNode firstNode; private ListNode lastNode; private String name; // String like "list" used in printing
public List(String s) { name=s; firstNode=lastNode=null; }
//Constructor: Constructor an empty List with "List" as the name public List(){ this("list"); }
//Insert an Object at the front of the List If List is empty, firstNode //and lastNode refer to same Object. Otherwise,firstNode refers to new node. public void insertAtFront(Object insertItem) { if(isEmpty())//如果链表为空,返回true,否则返回false. firstNode=lastNode=new ListNode(insertItem); else firstNode=new ListNode(insertItem,firstNode); }
//Insert an Object at the end of the List If List is empty, firstNode and //lastNode refer to same Object. Otherwise, lastNode's next instance variable refers to new node. public void insertAtBack(Object insertItem) { if(isEmpty()) firstNode=lastNode=new ListNode(insertItem); else lastNode=lastNode.next=new ListNode(insertItem); }
// Remove the first node from the List. public Object removeFromFront() throws EmptyListException { Object removeItem=null; if(isEmpty()) throw new EmptyListException(name);
removeItem=firstNode.data; //retrieve the data reset the firstNode and lastNode references
//Remove the last node from the List public Object removeFromBack() throws EmptyListException { Object removeItem=null;
if(isEmpty()) throw new EmptyListException(name);
removeItem=lastNode.data; //retrieve the data reset the firstNode and lastNode references if(firstNode.equals(lastNode)) firstNode=lastNode=null; else { ListNode current=firstNode;
//Return true if the List is empty. public boolean isEmpty(){ return firstNode==null; }
//Output the List contents public void print() { if(isEmpty()){ System.out.println("Empty " + name); return; } System.out.print("The " + name + " is: "); ListNode current=firstNode;
// Class EmptyListException definition class EmptyListException extends RuntimeException{ public EmptyListException(String name) { super("The " + name + " is empty"); } }// Class ListTestpublic class ListTest{ public static void main(String[] args){ List objList=new List();
//Create object to store in the List Boolean b=new Boolean( true ); Character c=new Character( '$' ); Integer i=new Integer( 34567 ); String s=new String( "hello" );
//Use the List insert methods objList.insertAtFront( b ); objList.print(); objList.insertAtFront( c ); objList.print(); objList.insertAtBack( i ); objList.print(); objList.insertAtBack( s ); objList.print();
public void set(T item) { if (lastReturned == header) throw new IllegalStateException();
lastReturned.nodeValue = item; }
public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } }
//************************************************************** public Iterator<T> iterator() { return new MyIterator(); } //************************************************************** public ListIterator<T> listIterator(int index) { return new MyListIterator(index); } //************************************************************** public static void main(String[] args) { MyLinkedList<String> t = new MyLinkedList<String>(); t.add("A"); t.add("B"); t.add("C"); t.add("D"); //t.remove("B"); //t.addFirst("AA"); //t.addLast("BB"); //t.printList(); /* Iterator<String> it = t.iterator(); while(it.hasNext()) System.out.println(it.next()); // A B C D */
ListIterator<String> it = t.listIterator(t.size());
while(it.hasPrevious()) { System.out.println(it.previous()); // D C B A } }}// MyLinkedList end~
// friendly data so class list can access it directly
Object data;
ListNode next;
ListNode(Object o)
{
data=o;
next=null;
}
// Constructor: Create a ListNode that refers to Object o and to the
// next ListNode in the List.
ListNode(Object o,ListNode nextNode)
{
data=o;
next=nextNode;
}
// Return the Object in this node
Object getObject()
{
return data;
}
ListNode getnext()
{
return next;
}
}
// Class List definition
class List{
private ListNode firstNode;
private ListNode lastNode;
private String name; // String like "list" used in printing
public List(String s)
{
name=s;
firstNode=lastNode=null;
}
//Constructor: Constructor an empty List with "List" as the name
public List(){
this("list");
}
//Insert an Object at the front of the List If List is empty, firstNode
//and lastNode refer to same Object. Otherwise,firstNode refers to new node.
public void insertAtFront(Object insertItem)
{
if(isEmpty())//如果链表为空,返回true,否则返回false.
firstNode=lastNode=new ListNode(insertItem);
else
firstNode=new ListNode(insertItem,firstNode);
}
//Insert an Object at the end of the List If List is empty, firstNode and
//lastNode refer to same Object. Otherwise, lastNode's next instance variable refers to new node.
public void insertAtBack(Object insertItem)
{
if(isEmpty())
firstNode=lastNode=new ListNode(insertItem);
else
lastNode=lastNode.next=new ListNode(insertItem);
}
// Remove the first node from the List.
public Object removeFromFront() throws EmptyListException
{
Object removeItem=null;
if(isEmpty())
throw new EmptyListException(name);
removeItem=firstNode.data; //retrieve the data reset the firstNode and lastNode references
if(firstNode.equals(lastNode))
firstNode=lastNode=null;
else
firstNode=firstNode.next;
return removeItem;
}
//Remove the last node from the List
public Object removeFromBack() throws EmptyListException
{
Object removeItem=null;
if(isEmpty())
throw new EmptyListException(name);
removeItem=lastNode.data; //retrieve the data reset the firstNode and lastNode references
if(firstNode.equals(lastNode))
firstNode=lastNode=null;
else
{
ListNode current=firstNode;
while(current.next !=lastNode){
current=current.next;
}
lastNode=current;
current.next=null;
}
return removeItem;
}
//Return true if the List is empty.
public boolean isEmpty(){
return firstNode==null;
}
//Output the List contents
public void print()
{
if(isEmpty()){
System.out.println("Empty " + name);
return;
}
System.out.print("The " + name + " is: ");
ListNode current=firstNode;
while(current !=null){
System.out.print(current.data.toString() + " ");
current=current.next;
}
System.out.println();
System.out.println();
}
}
// Class EmptyListException definition
class EmptyListException extends RuntimeException{
public EmptyListException(String name)
{
super("The " + name + " is empty");
}
}// Class ListTestpublic class ListTest{
public static void main(String[] args){
List objList=new List();
//Create object to store in the List
Boolean b=new Boolean( true );
Character c=new Character( '$' );
Integer i=new Integer( 34567 );
String s=new String( "hello" );
//Use the List insert methods
objList.insertAtFront( b );
objList.print();
objList.insertAtFront( c );
objList.print();
objList.insertAtBack( i );
objList.print();
objList.insertAtBack( s );
objList.print();
//Use the List remove methods
Object removedObj;
try{
removedObj=objList.removeFromFront();
System.out.println(removedObj.toString() + " removed");
objList.print();
removedObj=objList.removeFromFront();
System.out.println(removedObj.toString() + " removed");
objList.print();
removedObj=objList.removeFromBack();
System.out.println(removedObj.toString() + " removed");
objList.print();
removedObj=objList.removeFromBack();
System.out.println(removedObj.toString() + " removed");
objList.print();
}
catch(EmptyListException e){
System.err.println("\n" + e.toString());
}
}
}
很多方法都与它俩有关系!!
下面的代码是个双向循环链表,我在LinkedList里抄的...
package LinkedList;import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;public class MyLinkedList<T> {
//*************************************************************
private DNode<T> header;
private int listSize;
//*************************************************************
public MyLinkedList() {
header = new DNode<T>();
listSize = 0;
}
//*************************************************************
private static class DNode<T> {
T nodeValue;
DNode<T> prev;
DNode<T> next; public DNode() { // for header
nodeValue = null;
prev = this; // left
next = this; // right
} public DNode(T item) {
nodeValue = item;
prev = this;
next = this;
}
}
//**************************************************************
public boolean isEmpty() {
return (header.prev == header || header.next == header);
}
public int size() {
return listSize;
}
//**************************************************************
private DNode<T> addBefore(DNode<T> curr, T item) {
DNode<T> newNode, prevNode; newNode = new DNode<T>(item);
prevNode = curr.prev;
newNode.prev = prevNode;
newNode.next = curr;
prevNode.next = newNode;
curr.prev = newNode; return newNode;
} public boolean add(T item) {
addBefore(header, item);
listSize++;
return true;
}
public void addFirst(T item) {
addBefore(header.next, item);
listSize++;
}
public void addLast(T item) {
addBefore(header, item);
listSize++;
}
//**************************************************************
private void remove(DNode<T> curr) {
if(curr.next == curr) return;
DNode<T> prevNode = curr.prev, nextNode = curr.next;
prevNode.next = nextNode;
nextNode.prev= prevNode;
}
public boolean remove(Object o) {
for(DNode<T> p = header.next; p != header; p = p.next) {
if(o.equals(p.nodeValue)) {
remove(p);
listSize--;
return true;
}
}
return false;
}
//**************************************************************
public void printList() {
for(DNode<T> p = header.next; p != header; p = p.next)
System.out.println(p.nodeValue);
}
//**************************************************************
private class MyIterator implements Iterator<T> {
public DNode<T> nextNode = header.next;
public DNode<T> lastReturned = header;
public boolean hasNext() {
return nextNode != header;
}
public T next() {
if(nextNode == header)
throw new NoSuchElementException("");
lastReturned = nextNode;
nextNode = nextNode.next;
return lastReturned.nodeValue;
} public void remove() {
if(lastReturned == header)
throw new IllegalStateException("");
MyLinkedList.this.remove(lastReturned);
lastReturned = header;
listSize--;
}
}
//**************************************************************
private class MyListIterator extends MyIterator implements ListIterator<T> {
private int nextIndex;
MyListIterator(int index) {
if(index < 0 || index > listSize)
throw new IndexOutOfBoundsException("");
//如果index小于listSize/2,就从表头开始查找定位,否则就从表尾开始查找定位
if(index < (listSize >> 1)) {
nextNode = header.next;
for(nextIndex = 0; nextIndex < index; nextIndex++)
nextNode = nextNode.next;
}else {
nextNode = header;
for(nextIndex = listSize; nextIndex > index; nextIndex--)
nextNode = nextNode.prev;
}
} public boolean hasPrevious() {
return nextIndex != 0;
//return nextNode.prev != header;
}
public T previous() {
if (nextIndex == 0)
throw new NoSuchElementException("no");
lastReturned = nextNode = nextNode.prev;
nextIndex--;
return lastReturned.nodeValue;
}
public void remove() {
if(lastReturned == header)
throw new IllegalStateException("");
MyLinkedList.this.remove(lastReturned);
nextIndex--;
listSize--;
if(lastReturned == nextNode)
nextNode = nextNode.next;
lastReturned = header;
}
public void add(T item) {
MyLinkedList.this.addBefore(nextNode, item);
nextIndex++;
listSize++;
lastReturned = header;
}
public void set(T item) {
if (lastReturned == header)
throw new IllegalStateException();
lastReturned.nodeValue = item;
}
public int nextIndex() {
return nextIndex;
} public int previousIndex() {
return nextIndex - 1;
}
}
//**************************************************************
public Iterator<T> iterator() {
return new MyIterator();
}
//**************************************************************
public ListIterator<T> listIterator(int index) {
return new MyListIterator(index);
}
//**************************************************************
public static void main(String[] args) {
MyLinkedList<String> t = new MyLinkedList<String>();
t.add("A");
t.add("B");
t.add("C");
t.add("D");
//t.remove("B");
//t.addFirst("AA");
//t.addLast("BB");
//t.printList();
/*
Iterator<String> it = t.iterator();
while(it.hasNext()) System.out.println(it.next()); // A B C D
*/
ListIterator<String> it = t.listIterator(t.size());
while(it.hasPrevious()) {
System.out.println(it.previous()); // D C B A
}
}}// MyLinkedList end~
所以对元素的随即访问较快,而增加删除操作慢
LinkedList 底层实现是一个双向链表,没一个结点都包含了前一个元素的引用和后一个元素的引用和结点值
所以对元素的随即访问很慢,而增删较快
所以对元素的随即访问较快,而增加删除操作慢
LinkedList 底层实现是一个双向链表,没一个结点都包含了前一个元素的引用和后一个元素的引用和结点值
所以对元素的随即访问很慢,而增删较快
就是指针变成了引用。