1. 前言
前文我们用java语言实现了无哨兵的单向链表.稍作修改即可实现有哨兵的单向链表.有哨兵的单向链表相较与无哨兵的而言，其对链表的头结点的增删操作更为方便.而在此我们实现了带有头节点和尾节点的双向链表(该头节点和尾节点都不存储有效的数据).
2. 带有头节点和尾节点的双向链表
例 :
public class BinaryLinkedList implements Iterable<Integer> {
//头指针指向头节点
static Node prev = new Node(null, 0, null);
//尾指针指向尾节点
static Node tail = new Node(null, 0, null);
public BinaryLinkedList() {
//将头节点的next指针指向尾节点
//将尾节点的prev指针指向头节点
prev.next = tail;
tail.prev = prev;
}
private static class Node {
int value;
Node prev;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
//头插法
public void addHead(int value) {
Node p = new Node(prev, value, prev.next);
prev.next.prev = p;
prev.next = p;
}
//从头开始遍历
public void Traverse1Head() {
Node p;
for (p = prev.next; p != tail; p = p.next) {
//空链表时, p==null
if (p == null) {
return;
}
System.out.println("该节点的值为" + p.value);
}
}
//从尾开始遍历
public void Traverse1Tail() {
Node p;
for (p = tail.prev; p != prev; p = p.prev) {
if (p == null) {
return;
}
System.out.println("该节点的值为" + p.value);
}
}
//获取指定位置的值
public static int get(int index) {
Node p = findIndex(index);
return p.value;
}
//从头指针开始找指定索引的节点的值
private static Node findIndex(int index) {
int count = -1;
Node p = prev;
//这里允许index==-1的原因是此时返回的是头节点
//有实际意义, 因为此时insert函数就无需对插入位置为0时做出分析
if (index < -1) {
throw new RuntimeException("index输入不合法");
}
while (count < index) {
p = p.next;
//此时p可能为null, 所以需要判断
if (p == null) {
throw new RuntimeException("输入无效的index");
}
count++;
}
//如果p是尾节点, 将抛出异常
if (p == tail) {
throw new RuntimeException("尾节点不可操作");
}
return p;
}
//尾插法
public static void addLast(int value) {
Node p = new Node(tail.prev, value, tail);
tail.prev.next = p;
tail.prev = p;
}
public void Insert(int index, int value) {
//如果index==0, 则p是头节点
Node p = findIndex(index - 1);
Node insert = new Node(p, value, p.next);
p.next.prev = insert;
p.next = insert;
}
public int remove(int index) {
//找到要删除的节点
Node p = findIndex(index);
int value = p.value;
p.next.prev = p.prev;
p.prev.next = p.next;
return value;
}
//迭代器迭代的数据类型是整形, 又由于泛型不能是基本数据类型, 所以用到包装类
@Override
public Iterator<Integer> iterator() {
//使用到了匿名内部类
return new Iterator<Integer>() {
//成员变量p(实例变量)
Node p = prev.next;
@Override
public boolean hasNext() {
if (p != null && p != tail) {
return true;
}
return false;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
public void Traverse2(Consumer<Integer> consumer) {
Node p;
for (p = prev.next; p != tail; p = p.next) {
if (p == null) {
return;
}
consumer.accept(p.value);
}
}
}
3. 单元测试(测试案例)
测试案例供参考 :
@Test
public void test1() {
BinaryLinkedList b = new BinaryLinkedList();
b.addHead(12);
b.addHead(23);
b.addHead(34);
b.addHead(45);
b.addHead(56);
b.addHead(67);
b.addHead(78);
// b.Traverse1Head();
// b.Traverse1Tail();
// System.out.println(b.get(0));
}
@Test
public void test2() {
BinaryLinkedList b = new BinaryLinkedList();
b.addLast(12);
b.addLast(23);
b.addLast(34);
b.addLast(45);
b.addLast(56);
b.addLast(67);
b.addLast(78);
//只有实现了Intrable接口的类才能使用foreach循环,
//因为foreach底层就是使用迭代器不断调用hasNext(), next()方法
//迭代出值赋值给临时变量element
for (Integer element : b) {
System.out.println("该节点的数据域是" + element);
}
}
@Test
public void test3() {
BinaryLinkedList b = new BinaryLinkedList();
b.addLast(12);
b.addLast(23);
b.addLast(34);
b.addLast(45);
b.addLast(56);
b.addLast(67);
b.addLast(78);
//使用lambda表达式
b.Traverse2(value -> System.out.println("该节点的数据域的值是" + value));
System.out.println("*******************");
//还可以使用方法引用
b.Traverse2(System.out :: println);
}
