ITEEDU

Java Gossip: LinkedList

List类是以对象加入（add）容器的顺序来排列它们，如果您的对象加入之后大都是为了取出，而不会常作移除或插入（Insert）的动作，则使用ArrayList，如果您会经常从容器中作移除或插入对象的动作，则使用LinkedList会获得较好的效能。

LinkedList实作了List接口，并增加了一些移除与插入对象的特定方法，像是addFirst()、addLast()、 getFirst()、getLast()、removeFirst( )、removeLast()等等，由于在插入与移除时有较好的效能，适合拿来实作堆栈（Stack）与队列（Queue）。

以下实作一个简单的FILO（First-In, Last-Out）堆栈，可以存入字符串：

StringStack.java

package onlyfun.caterpillar;
import java.util.*;
public class StringStack {
	private LinkedList linkedList;
	public StringStack() {
		linkedList = new LinkedList();
	}
	public void push(String name) {
		linkedList.addFirst(name);
	}
	public String top() {
		return linkedList.getFirst();
	}
	public String pop() {
		return linkedList.removeFirst();
	}
	public boolean isEmpty() {
		return linkedList.isEmpty();
	}
}

而对于FIFO（First-In, First-Out）的队列，我们也可以使用LinkedList来实作：

StringQueue.java

package onlyfun.caterpillar;
import java.util.*;
public class StringQueue {
	private LinkedList linkedList;
	public StringQueue() {
		linkedList = new LinkedList();
	}
	public void put(String name) {
		linkedList.addFirst(name);
	}
	public String get() {
		return linkedList.removeLast();
	}
	public boolean isEmpty() {
		return linkedList.isEmpty();
	}
}

事实上，如果您要使用队列的功能，您也不用亲自实作，在J2SE 5.0中，LinkedList也实作了新加入的java.util.Queue接口，这个接口有五个必须实作的方法：

要使用队列的功能，您只要类似这样的宣告：

Queue<String> queue = new LinkedList<String>();