节点类
public class BidirectionalNode<Item> {
private BidirectionalNode<Item> previous;
private Item item;
private BidirectionalNode<Item> next;
public BidirectionalNode() {
super();
// TODO Auto-generated constructor stub
}
public BidirectionalNode(BidirectionalNode<Item> previous, Item item, BidirectionalNode<Item> next) {
super();
this.previous = previous;
this.item = item;
this.next = next;
}
public BidirectionalNode<Item> getPrevious() {
return previous;
}
public void setPrevious(BidirectionalNode<Item> previous) {
this.previous = previous;
}
public Item getItem() {
return item;
}
public void setItem(Item item) {
this.item = item;
}
public BidirectionalNode<Item> getNext() {
return next;
}
public void setNext(BidirectionalNode<Item> next) {
this.next = next;
}
@Override
public String toString() {
return "BidirectionalNode [previous=" + previous + ", item=" + item + ", next=" + next + "]";
}
}
双链表类
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* @author
*
* @param <Item>
*/
public class DoubleLinkedList<Item> implements Iterable<Item> {
private BidirectionalNode<Item> first, last;
private int n;
public DoubleLinkedList() {
super();
first = null;
last = null;
n = 0;
}
public boolean isHadNode(BidirectionalNode node) {
BidirectionalNode<Item> nowNode = first;
for (int i = 1; i < n; i++) {
if (nowNode.equals(node)) {
return true;
} else {
nowNode = nowNode.getNext();
}
}
throw new NoSuchElementException("can't find this node!");
}
/**
* 在表头插入结点
*
* @param item
*/
public void insterAtFirst(BidirectionalNode<Item> newNode) {
// 插入需要判断两种情况，一种链表不为空，一种链表为空
if (first != null) {
// 不为空，则原first放置到新first的后面
// change operater
BidirectionalNode<Item> oldFirst = first;
// init to firstNode
first = newNode;
first.setPrevious(null);
first.setNext(oldFirst);
oldFirst.setPrevious(first);
n++;
} else if (first == null) {
// 如果链表为空。那么它就是唯一的结点——首结点是它，尾结点也是它。
first = newNode;
last = newNode;
n++;
}
}
/**
* 在表尾插入结点
*
* @param item
*/
public void insertAtLast(BidirectionalNode<Item> newNode) {
// 还是要考虑两个情况，链表是否为空
if (last != null) {
// TODO 这里还要判断一个元素的情况下...
BidirectionalNode<Item> oldLast = last;
last = newNode;
last.setPrevious(oldLast);
last.setNext(null);
oldLast.setNext(last);
n++;
} else if (first == null) {
// 如果链表为空。那么它就是唯一的结点——首结点是它，尾结点也是它。
first = newNode;
last = newNode;
n++;
}
}
/**
* 从表头删除结点
*/
public void deleteAtFirst() {
// 如果为空，则不能正常删除，抛出异常
if (first == null) {
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
if (n == 1) {
first = null;
last = null;
} else {
BidirectionalNode<Item> oldFirst = first;
first = oldFirst.getNext();
first.setPrevious(null);
// 释放掉oldFirst
oldFirst = null;
n--;
}
}
/**
* 从表尾删除结点
*/
public void deleteAtLast() {
if (first == null) {
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
if (n == 1) {
first = null;
last = null;
} else {
BidirectionalNode<Item> oldLast = last;
last = oldLast.getPrevious();
last.setNext(null);
// 释放掉oldLast
oldLast = null;
n--;
}
}
/**
* 在指定结点前插入
*
* @param node
* @param newNode
*/
public void insertBefore(BidirectionalNode<Item> node, BidirectionalNode<Item> newNode) {
if (first == null) {
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
// 判断是否有这个节点
isHadNode(node);
// 判断：只有一个结点
if (n == 1) {
first.setPrevious(newNode);
newNode.setNext(first);
n++;
} else {
// 处理前面的指向
newNode.setPrevious(node.getPrevious());
node.getPrevious().setNext(newNode);
// 处理后面的指向
newNode.setNext(node);
node.setPrevious(newNode);
n++;
}
}
/**
* 在指定结点后插入
*
* @param node
* @param newNode
*/
public void insertAfter(BidirectionalNode<Item> node, BidirectionalNode<Item> newNode) {
if (first == null) {
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
isHadNode(node);
// 判断：只有一个结点
if (n == 1) {
newNode.setPrevious(first);
first.setNext(newNode);
n++;
} else {
// 处理后面的指向
newNode.setNext(node.getNext());
node.getNext().setPrevious(newNode);
// 处理前面的指向
newNode.setPrevious(node);
node.setNext(newNode);
n++;
}
}
/**
* 删除指定结点
*
* @param node
*/
public void deleteNode(BidirectionalNode<Item> node) {
if (first == null) {
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
isHadNode(node);
if (n == 1) {
first = null;
last = null;
n--;
} else {
if (!first.equals(node)) {
node.getPrevious().setNext(node.getNext());
}
if (!last.equals(node)) {
node.getNext().setPrevious(node.getPrevious());
}
BidirectionalNode<Item> nowNode = first;
for (int i = 1; i < n; i++) {
if (nowNode.equals(node)) {
nowNode = null;
break;
} else {
nowNode = nowNode.getNext();
}
}
n--;
}
}
public boolean isEmpty() {
return first == null;
}
//忽略一些没用的代码...
}
测试代码
DoubleLinkedList<String> dll = new DoubleLinkedList<String>();
BidirectionalNode<String > nb1 = new BidirectionalNode<String>(null,"a",null);
BidirectionalNode<String > nb2 = new BidirectionalNode<String>(null,"b",null);
BidirectionalNode<String > nb3 = new BidirectionalNode<String>(null,"c",null);
BidirectionalNode<String > nb4 = new BidirectionalNode<String>(null,"d",null);
BidirectionalNode<String > nb11 = new BidirectionalNode<String>(null,"aa",null);
BidirectionalNode<String > nb22 = new BidirectionalNode<String>(null,"bb",null);
dll.insterAtFirst(nb1);
dll.insertAtLast(nb2);
dll.insterAtFirst(nb3);
dll.insertAtLast(nb4);
dll.insertBefore(nb1, nb11);
dll.insertAfter(nb2, nb22);
dll.deleteNode(nb3);一直没搞搞懂 deleteNode为什么删除不成功，里面的元素还是没有被删减，n倒是减了。感觉是基础语法的问题。。
public void deleteNode(BidirectionalNode<Item> node)
{
if (first == null){
throw new NoSuchElementException("DoubleLinkedList is Empty");
}
isHadNode(node);
if (n == 1){
first = null;
last = null;
}
else{
if (first == node){
first = first.getNext();
first.setPrevious(null);
}
else if (last == node){
last = last.getPrevious();
last.setNext(null);
}
else{
node.getPrevious().setNext(node.getNext());
node.getNext().setPrevious(node.getPrevious());
}
}
n--;
}for (int i = 1; i < n; i++) {
if (nowNode.equals(node)) {
nowNode = null;
break;
} else {
nowNode = nowNode.getNext();
}
}
n--;你把n--写到break前面你就知道了。由于函数引用参数传递时，引用本身是复制的，所以nowNode.equals(node)永远不会为true。java我不太熟悉，应该有种类似叫out或ref的参数传递方式。
另外，你这里只是把node指向null的删除方式根本不对，因为这样的话，你的链表就断掉了。