LinkedList是双向链接数据结构,插入和删除快,查询慢,因为他使用了二分查找。
public class ExtLinkedList<E> {
private Node first;
private Node last;
private int size;
public void add(E o) {
Node l = last;
Node node = new Node(o, l, null);
last = node;
if(l == null) {
first = node;
} else {
l.next = node;
}
size++;
}
public Node<E> get(int index) {
if(index < (size >> 1)) {
Node x = first;
for(int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node x = last;
for(int i = size - 1; i > index; i--) {
x = x.pre;
}
return x;
}
}
public Node remove(int index) {
Node node = get(index);
unlink(node);
return node;
}
private void unlink(Node node) {
Node pre = node.pre;
Node next = node.next;
if(pre == null) {
first = next;
} else {
pre.next = next;
node.pre = null;
}
if(next == null) {
last = pre;
} else {
next.pre = pre;
node.next = null;
}
node.item = null;
size--;
}
public static void main(String[] args) {
ExtLinkedList<String> tests = new ExtLinkedList<String>();
tests.add("a");
tests.add("b");
tests.add("c");
Node node = tests.get(0);
System.out.println(node.item);
node = tests.remove(1);
for(int i = 0; i < tests.size; i++) {
System.out.println(tests.get(i).item);
}
}
static class Node<E> {
E item;
Node<E> pre;
Node<E> next;
public Node(E item, Node pre, Node next) {
this.item = item;
this.pre = pre;
this.next = next;
}
}
}
网友评论