Java双向链表的实现，帮忙看下有没有什么bug。

Question

/**
 * 
 */
package com.handy.ds;/**
 * @author handy
 *2012-03-14
 * 
 */
public class DoubleLinkedList {
class Node {
Node prev;
Node next;
Object data; public Node(Object data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
} public Node(Node prev, Node next) { this.prev = prev;
this.next = next;
} public Node() { }
} private Node head;
private int size; /**
 * @return the size
 */
public int getSize() {
return size;
} /**
 * @param size
 *            the size to set
 */
public void setSize(int size) {
this.size = size;
} private Node getNode(int index) {
checkIndex(index);
Node curr = this.head;
int revIndex = this.size - index;
if (index <= revIndex) {
for (int i = 0; i <= index; i++)
curr = curr.next;
} else {
for (int i = 0; i < revIndex; i++)
curr = curr.prev;
}
return curr;
} public DoubleLinkedList() {
// 第一个元素存值
head = new Node();
// 头指针不存值，可以这样初始化
head.prev = head.next = head;
} public boolean isEmpty() {
return size == 0;
} public boolean contains(Object o) {
Node curr = this.head.next;
Node last = head.prev;
while ((curr != null || last != null)) {
if (curr.data.equals(o))
return true;
if (last.data.equals(o))
return true;
Node temp = last;
curr = curr.next;
last = last.prev;
if (curr.next == temp)
break; // 指针相碰
}
return false;
// 或者使用以下更简单的方法
// if(indexOf(o)!=-1)
// return true;
// return false; } // 移除链表的第一个元素,由于head不保存信息，第一个元素为head.next,故移去head.next
public Object removeFirst() {
if (this.size == 0)
return null;
else { Node first = head.next;
first.next.prev = head;
head.next = first.next;
this.size--;
return first; }
} // 移除最后一个元素
public Object removeLast() {
if (this.size == 0)
return null;
else {
Node last = head.prev;
Node lastSecond = last.prev;
lastSecond.next = head;
head.prev = lastSecond;
this.size--;
return last; }
} // 移除第i个元素
public Object remove(int index) throws IndexOutOfBoundsException {
checkIndex(index);
int size = this.size;
Node curr = getNode(index);
Node p = curr.prev;
Node n = curr.next;
p.next = n;
n.prev = p;
this.size--;
return curr;
} // 移除第一次出现的o元素
public Object removeFist(Object o) {
if (this.size == 0)
return null;
else {
Node curr = this.head.next;
boolean isFind = false;
int size = this.size;
int i = 0; while (i < size) {
if (curr.data.equals(o)) {
isFind = true;
break;
}
curr = curr.next;
i++;
}
if (isFind) { // 找到就重构链表
Node p = curr.prev;
Node n = curr.next;
p.next = n;
n.prev = p;
this.size--;
return curr;
}
return null; } } // 移除最后一次出现的o元素
public Object removeLastOccurrence(Object o) {
if (this.size == 0)
return null;
else {
Node curr = this.head.next;
Node lastOccurrenceNode = null;
int i = 0;
int size = this.size;
while (i < size) {
if (curr.data.equals(o))
lastOccurrenceNode = curr;
curr = curr.next;
i++;
}
if (lastOccurrenceNode != null) { // 找到最后一次出现的元素就重构链表
Node p = lastOccurrenceNode.prev;
Node n = lastOccurrenceNode.next;
p.next = n;
n.prev = p;
this.size--;
return lastOccurrenceNode;
}
return null;
}
} // 检查是否越界
public boolean checkIndex(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= this.size) { throw new IndexOutOfBoundsException("边界不合法：" + index);
}
return true; } // 加到尾部
public boolean addLast(Object o) { Node last = head.prev;
Node lastSecond = last.prev;
Node newNode = new Node(o, last, head);
last.next = newNode;
head.prev = newNode;
this.size++;
return true; } // 加到指定位置index之前
public boolean add(int index, Object o) {
Node curr = getNode(index);
Node p = curr.prev;
// Node n=curr.next;
Node newNode = new Node(o, p, curr);
curr.prev = newNode;
p.next = newNode;
this.size++;
return true;
} // 加到前面
public boolean addFirst(Object o) {
Node curr = head.next;
Node newNode = new Node(o, head, curr);
head.next = newNode;
curr.prev = newNode;
this.size++;
return true;
} // 获取第一个元素
public Object getFist() {
return head.next;
} // 获取最后一个元素
public Object getLast() {
return head.prev;
} // 获取指定位置的元素的值
public Object get(int index) {
checkIndex(index);
Node curr = getNode(index);
return curr.data;
} // 返还元素在链表中位置的索引(从0开始),若元素不在链表中，则返回-1
public int indexOf(Object o) {
int index = 0;
int size = this.size; Node curr = head.next;
while (index < size) {
if (curr.data.equals(o))
return index;
curr = curr.next;
index++; } return -1;
} // 替换指定索引处的节点
public boolean set(int index, Object o) {
Node curr = getNode(index);
curr.data = o;
return true;
} // 返回该元素最后一次出现的索引值,元素不存在返回-1
public int lastIndexOf(Object o) {
int index = -1;
Node curr = head.next;
Node node = null;
int size = this.size;
int i = 0;// 循环变量
while (i < size) {
if (curr.data.equals(o)) {
node = curr;
index = i;
}
curr = curr.next;
i++; }
return index;
} // 返回该链表的数组表示
public Object[] toArray() {
Object[] array = new Object[this.size];
Node curr = head.next;
for (int i = 0; i < size; i++, curr = curr.next) {
array[i] = curr.data;
}
return array;
} // 将指定链表追加到当前链表中
public boolean addAll(DoubleLinkedList dll) {
if (dll == null)
throw new NullPointerException("链表不能为空!" + dll);
Node last = head.prev;
Node dllLast = dll.head.prev;
dllLast.next = head;
dll.head.prev = last;
head.prev = dllLast;
last.next = dll.head.next; this.size = this.size + dll.size;
return true; } public void clear() {
this.head.next = head.prev = null;
this.size = 0;
} // 比较两个链表是否相等
public boolean equals(Object o) {
if (o == this)
return true;
else {
if (o instanceof DoubleLinkedList) {
int size = this.size;
DoubleLinkedList dll = (DoubleLinkedList) o;
if (size != dll.size)
return false;
else {
int i;
Node p, q;
for (p = this.head.next, q = dll.head.next, i = 0; i < size; i++, p = p.next, q = q.next) {
if (p.data == null && q.data != null)
return false;
else
// 这里是递归吗？还是调用Object类的equals方法?
if (!p.data.equals(q.data))
return false; }
return true;
}
} else
return false;
} } // 返回链表的字符串表示
public String toString() {
StringBuffer sb = new StringBuffer("[");
Node curr = head.next;
for (int i = 0; i < this.size; i++, curr = curr.next) {
if (i == size - 1)
sb.append(curr.data);
else
sb.append(curr.data + ","); }
sb.append("]");
return new String(sb);
} public static void main(String[] args) {
DoubleLinkedList dll = new DoubleLinkedList();
dll.addFirst(5);
System.out.println(dll.toString());// [5]
dll.removeFirst();
System.out.println(dll.isEmpty());// true
dll.removeFirst();
System.out.println(dll.toString());// []
dll.removeFist(5);
System.out.println(dll.toString());// []
dll.removeLast();
System.out.println(dll.toString());// []
dll.removeLastOccurrence(5);
System.out.println(dll.toString());// []
dll.addLast(10);
System.out.println(dll.toString());// [10]
dll.addFirst(30);
System.out.println(dll.toString());// [30,10]
System.out.println(dll.get(0));
System.out.println(dll.get(1));
dll.addFirst(40);
dll.addLast(20);
dll.addLast(50);
System.out.println(dll.toString());// [40,30,10,20,50]
System.out.println(dll.get(4));
System.out.println(dll.get(3));
dll.add(3, 100);
System.out.println(dll.toString());// [40,30,10,100,20,50]
dll.removeFirst();
System.out.println(dll.toString());// [30,10,100,20,50]
dll.removeLast();
System.out.println(dll.toString());// [30,10,100,20]
dll.addFirst(30);
dll.addFirst(40);
dll.addFirst(30);
System.out.println(dll.toString());// [30,40,30,30,10,100,20]
System.out.println(dll.getSize());// [30,40,30,30,10,100,20]
dll.removeFist(30);
System.out.println(dll.toString());// [40,30,30,10,100,20]
dll.addLast(10);
System.out.println(dll.toString());// [40,30,30,10,100,20,10]
dll.removeLastOccurrence(10);
System.out.println(dll.toString());// [40,30,30,10,100,20]
System.out.println(((Node) dll.getFist()).data);// 40
System.out.println(dll.get(3));// 10
System.out.println(((Node) dll.getLast()).data);// 10
dll.set(1, 70);
System.out.println(dll.toString());// [40,70,30,10,100,20]
dll.addFirst(10);
System.out.println(dll.toString());// [10,40,70,30,10,100,20]
System.out.println(dll.indexOf(10));// 0
System.out.println(dll.lastIndexOf(10));// 3
System.out.println(dll.contains(100));// true
System.out.println(dll.contains(50));// true
DoubleLinkedList dll2 = new DoubleLinkedList();
dll2.addLast(200);
dll2.addFirst(400);
System.out.println(dll2.toString());// [400,200]
dll.addAll(dll2);
System.out.println(dll.toString());// [40,70,30,10,100,20,400,200]
Object[] o = dll.toArray();
// [40,70,30,10,100,20,400,200]
System.out.print("[");
for (int i = 0; i < o.length; i++) {
if (i != o.length - 1)
System.out.print(o[i] + ",");
else
System.out.print(o[i]);
}
System.out.println("]");

}}

Answer 1

其实java中有双向链表，就是LinkedList，用那个简单，当然如果自己写的话，对编程思想的提升还是有很大的帮助的。

Answer 2

Java语言程序设计有一章也是叫你自己实现双向链表. 

Answer 3

让人肉眼帮你查有无Bug，不如自己写单元测试进行验证。链表容易出问题的无非是表头表尾位置，可以多测试些插入、删除、移动，最后就是最简单的遍历。