日期:2014-05-20  浏览次数:20826 次

Java双向链表的实现,帮忙看下有没有什么bug。
/**
 * 
 */
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;