链表简单例子

package test;

import java.util.*;

public class Tiger9 {
static class LinkedList {
private Node header;
private int size;
public LinkedList() {
header = new Node(null, null);
size = 0;
}
public void add(Object o) {
Node n = new Node(o, header); //关键步骤。创建一个新的Node对象，它的next变量将指向添加它之前的header对象。
header = n; //使新创建的Node对象成为新的header对象。
size++;
}
public Object remove() {
Object o = header.object;
header = header.next;
size--;
return o;
}
public Object get(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException("index = " + index);
}
Node n = header;
for (int i = 0; i < index; i++) {
n = n.next;
}
return n.object;
}
public Object[] toArray() {
Object[] os = new Object[size];
int i = 0;
for (Node n = header; n.next != null; n = n.next) {
os[i++] = n.object;
}
return os;
}
public int size() {
return size;
}
public String toString() {
return Arrays.toString(toArray());
}
private class Node {
Object object;
Node next;
public Node(Object object, Node next) {
this.object = object;
this.next = next;
}
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add("aaaa");
list.add("bbbb");
list.add("cccc");
list.add("dddd");
System.out.println(list + " " + list.size());
for (int i = 0; i < list.size(); i++) {
System.out.println("i=" + i + ", object=" + list.get(i));
}
for (int i = 0; i < 4; i++) {
System.out.println("remove:" + list.remove() + ", " + list);
}
}
}

结果：

[dddd, cccc, bbbb, aaaa] 4
i=0, object=dddd
i=1, object=cccc
i=2, object=bbbb
i=3, object=aaaa
remove:dddd, [cccc, bbbb, aaaa]
remove:cccc, [bbbb, aaaa]
remove:bbbb, [aaaa]
remove:aaaa, []

结论：

一、对于链表来说，添加和删除元素是非常容易的。相比而言，在线性表中每添加或删除一个元素，就得创建一个新size的数组，并将原有元素拷贝到新数组中来。

二、另一方面，在线性表中，由于使用数组作为存取元素的仓库，按索引查找是非常容易实现的。相对而言，在链表中必须经历低效率的频繁遍历才能索引到相应位置的元素。

三、应当根据具体情况分别选用相应的数据结构。比如：

如果只需要快速添加元素并通过遍历方式依次访问元素，并不涉及到索引操作，推荐使用链表。

如果需要频繁地根据索引随机访问元素，则虽然在添加和删除操作上先天不足，但线性表的性能仍会优于链表。