双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点
下图是双向链表的逻辑结构图,和单链表不同的是,双向链表中每个节点包含两个节点的指针引用,和一个数据域,这两个节点分别指向前一个节点和后一个节点;
双向链表的这种结构比起单链表,其改进之处正在于此,通过对前后节点的引用可以使得在整个链表中,通过给定的值,可以从前或者向后遍历,大大提升了遍历查询的效率,一定程度上解决了单链表的性能问题,但与此同时,链表的存储开销也增大了,我们熟悉的linkedList,其底层就是这个原理实现的.
废话不多说,相信通过上面的解释大家已经很明白了,下面直接上代码,可以结合代码和图结构理解双向链表,
public class DoubleLinkTest<T> {
private class Node<T> {
private T data;
private Node next; // 指向下一个节点的引用
private Node prev; // 指向前一个节点的引用
public Node(T data) {
this.data = data;
}
}
private Node<T> head; // 模拟头结点
private Node<T> last; // 模拟尾部节点
private Node<T> other; // 暂定一个临时节点,用作指针节点
private int length;
public void DoubleLinkTest() {
head = new Node<T>(null);
last = head;
length = 0;
}
public void DoubleLinkTest(T data) {
head = new Node<T>(data);
last = head;
length = 0;
}
public boolean isEmpty() {
return length == 0;
}
public void add(T data) {
if (isEmpty()) { // 链表为空,新创建一个链表
head = new Node<T>(data);
last = head;
length++;
} else {
other = new Node<T>(data);
other.prev = last;
last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联
last = other; // other将成为最后一个节点
length++;
}
}
public void addAfter(T data, T insertData) {
other = head;
while (other != null) { // 我们假定这个head是不为空的。
if (other.data.equals(data)) {
Node<T> t = new Node<T>(insertData);
t.prev = other;
t.next = other.next;// 对新插入的数据进行一个指向的定义
other.next = t;
if (t.next == null) {
last = t;
}
length++;
}
other = other.next;
}
}
public void remove(T data) {
other = head;// 我们假定这个head是不为空的。
while (other != null) {
if (other.data.equals(data)) {
other.prev.next = other.next;
length--;
}
other = other.next;
}
}
public void printList() {
other = head;
for (int i = 0; i < length; i++) {
System.out.println(other.data + " ");
other = other.next;
}
}
public static void main(String[] args) {
DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
link.add(1);
link.add(2);
link.add(3);
link.add(5);
link.add(6);
link.add(7);
link.printList();
System.out.println(" ============== ");
System.out.println(" ==== 在3后面添加一个数据开始========== ");
link.addAfter(3, 99);
link.printList();
System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");
System.out.println(" ==== 移除一个数据开始========== ");
link.remove(99);
link.printList();
System.out.println(" \r\n");
}
}
运行main函数,可以看到控制台的打印输出:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程网。