数组与链表的优缺点十分明显，所以对于不同的问题时需要建立模型计算更适合的数据结构
以下是一些链表的应用：
下压栈的链表结构
import java.util.Iterator; import static java.lang.System.out; public class Stack<Item> { private Node first; private int N; private class Node{ Item item; Node next; } public boolean isEmpty(){ return first==null; } public int size() { return N; } public void push(Item item) { Node Oldfirst = first; first=new Node(); first.item=item; first.next=Oldfirst; N++; } public Item pop() { Item item = first.item; first=first.next; N--; return item; } }队列的链表结构
public class Queue<Item> { private Node first; private Node last; private int N; private class Node { Item item; Node next; } public boolean isEmpty(){ return first==null; } public int size(){ return N; } public void enqueue(Item item) { Node oldlast = last; last = new Node(); last.item=item; last.next=null; if(isEmpty()) first = last; else oldlast.next=last; N++; } public Item dequeue() { Item item= first.item; first = first.next; if(isEmpty()) last= null; N--; return item; } }背包的链表实现
import java.util.ListIterator; import java.util.Iterator; public class Bag <Item>{ private Node first; private class Node{ Item item; Node next; } public void add(Item item) { Node oldfirst = first; first=new Node(); first.item=item; first.next=oldfirst; } public Iterator<Item> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<Item> { private Node current=first; public boolean hasNext() { return current != null; } public void remove() { } public Item next() { Item item = current.item; current=current.next; return item; } } }:)
