public without sharing class LinkedList {
private Integer size = 0;
private Node first;
private Node last;
public Integer size() {
return size;
}
//在第一个位置添加元素
public void addFirst(Object obj) {
linkNode(obj, 0);
}
//在最后一个位置添加元素
public void add(Object obj) {
linkNode(obj, size);
}
//在指定位置前添加元素
public void add(Object obj, Integer index) {
linkNode(obj, index);
}
public Object removeFirst() {
return unLinkNode(0);
}
public Object removeLast() {
return unLinkNode(size - 1);
}
public Object remove(Integer index) {
return unLinkNode(index);
}
public Boolean removeAll() {
return (Boolean) unLinkNode(null);
}
public void set(Integer index, Object obj) {
checkPositionIndex(index, 'edit');
Node operateNode = node(index, 'edit');
operateNode.item = obj;
}
public Object[] toArray() {
Object[] results = new Object[size];
Integer i = 0;
for (Node n = first; n != null; n = n.next) {
results[i++] = n.item;
}
return results;
}
public Object get(Integer index) {
checkPositionIndex(index, 'get');
Node result = node(index, 'get');
return result.item;
}
override public String toString() {
Object[] results = toArray();
return String.valueOf(results);
}
private Object unLinkNode(Integer index) {
checkPositionIndex(index, 'delete');
Node leftNode;
Node rightNode;
Node operateNode;
Object result;
if (index != null) {
if (index == 0) { //remove first
operateNode = first;
result = operateNode.item;
rightNode = operateNode.next;
first = rightNode;
//如果只有一个结点,则将last置空
if (rightNode == null) {
last = null;
} else {
rightNode.prev = null;
}
size--;
} else if (index == size - 1) { //remove last
operateNode = last;
result = operateNode.item;
leftNode = operateNode.prev;
last = leftNode;
if (leftNode == null) {
first = null;
} else {
leftNode.next = null;
}
size--;
} else { //remove index node
operateNode = node(index, 'delete');
result = operateNode.item;
leftNode = operateNode.prev;
rightNode = operateNode.next;
if (leftNode != null) {
leftNode.next = rightNode;
}
if (rightNode != null) {
rightNode.prev = leftNode;
} else {
}
size--;
}
} else { //remove all
first = null;
last = null;
size = 0;
result = true;
}
return result;
}
private void linkNode(Object e, Integer index) {
checkPositionIndex(index, 'add');
Node newNode;
Node leftNode;
Node rightNode;
if (index == 0) { //add first
rightNode = first;
newNode = new Node(null, e, rightNode);
first = newNode;
if (rightNode == null) {
last = newNode;
} else {
rightNode.prev = newNode;
}
} else if (index == size) { //add last
leftNode = last;
newNode = new Node(leftNode, e, null);
last = newNode;
if (leftNode == null) {
first = newNode;
} else {
leftNode.next = newNode;
}
} else { //add node to specify index
//get the index node
rightNode = node(index, 'add');
leftNode = rightNode.prev;
newNode = new Node(leftNode, e, rightNode);
rightNode.prev = newNode;
if (leftNode == null) {
first = newNode;
} else {
leftNode.next = newNode;
}
}
size++;
}
//获取指定位置的结点元素,此部分可以进行优化。比如二分法或者其他处理从而减小循环的数量
private Node node(Integer index, String operateType) {
checkPositionIndex(index, operateType);
Node x = first;
for (Integer i = 1; i < size; i++) {
x = x.next;
if (index == i) {
break;
}
}
return x;
}
//判断当前的index是否符合规范,比较其和size的关系以及是否大于0等校验
private void checkPositionIndex(Integer index, String operateType) {
if (index < 0) {
throw new LinkedListException('index必须大于等于0');
}
if ('delete'.equalsIgnorecase(operateType)) {
if (size <= 0) {
throw new LinkedListException('链表长度必须大于0才可以删除');
}
}
if (!'add'.equalsIgnorecase(operateType)) {
if (index >= size) {
throw new LinkedListException('index 越界!');
}
}
}
private class Node {
Object item; // 当前节点所包含的值
Node next; //下一个节点
Node prev; //上一个节点
Node(Node prev, Object element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public class LinkedListException extends Exception {
}
}
来源: http://www.cnblogs.com/zero-zyq/p/7325703.html