无头双向链表（Java语言）
前言
经过对于顺序表和单链表的熟悉我们已经对于数据结构有了简单的认识，这次我们了解无头双向链表的相关知识。
介绍
首先我们先看一下双向链表的结构：
这就是一个非常简单的双向链表，一个节点可以找到它的后继，也可以找到它的前驱，第一个是head节点（不是有头链表的头节点），最后一个是last节点，为什么需要双向链表呢？我们在做题时老遇到需要记住一个节点的前驱，防止节点的next被覆盖，而不能找到这个节点的。因此我们构造双向链表来解决这个问题，同样也提高了效率。
无头双向非循环链表
在无头双向非循环链表中，我们将每个元素叫做节点，因此，我们将节点封装成一个类：
节点类——ListNode
class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
类中有三个成员变量，val（值），next（下一个节点的地址），prev（上一个节点的地址），构造方法是将val值赋值给该对象的val，这就是一个节点，我们将若干个节点连起来就形成了链表。
链表类——MyLinkedList
public class MyLinkedList {
public ListNode head;//指向双向链表的头节点
public ListNode last;//指向的是尾巴节点
}
在链表类中实例化两个节点，head和last，两个分别指向第一个节点和最后一个节点。
打印链表
//打印链表
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
打印双向链表和打印单向链表是一样的，用一个cur节点进行遍历整个数组，然后就行打印。
得到链表的长度
//得到链表的长度
public int size() {
ListNode cur = head;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
return size;
}
同样的和单链表求长度一样，实例化一个节点，遍历的同时用计数器计数遍历过多少个节点。
查找是否包含关键字key
//查找是否包含关键字key
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
查询是否包含关键字也是一样，遍历的同时比较是否与关键字key相等，相等返回true，不相等往下遍历，知道走完整个链表，返回false。
插入一个元素——头插法
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
双链表的头插法要比单链表的复杂一点，原因就在于他需要改动prev的值。我们画图理解一下：
现在有一个node的节点用头插法插进链表，如何才能完成呢？我们发现需要将head赋值给node的next，将head的prev赋值成node并且需要将head移动到node的位置。像这样：
这样就完成了头插法，但是我们需要注意的是，这是链表不为null的情况下，因此，我们要将链表为null的情况考虑在内，当链表为null时，只需要将head和last都指向node就可以完成了。
插入一个元素——尾插法
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = last.next;
}
}
尾插法跟头插法极其类似，这里就不在过多的介绍了，有兴趣的可以对照头插法的方法画一个图自己写一下代码试试看。
插入一个元素——任意位置插入
为了方便，我们将寻找节点的函数单独写成一个方法：
寻找index位置的节点
//寻找index位置的节点
public ListNode searchIndex(int index) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法");
return null;
}
ListNode cur = head;
while (index > 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入，第一个数据节点为下标0
public void addIndex(int index, int data) {
ListNode node = new ListNode(data);
ListNode cur = this.searchIndex(index);
if (index == 0) {
this.addFirst(data);
} else if (index == size()) {
this.addLast(data);
} else {
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
}
任意位置插入，我们可以分为三种情况，第一，index为0，则可以使用头插法；第二，index为size（）（链表的长度），则可以用尾插法；第三，中间位置插入，这是我们需要自己修改的。我们重点看第三种情况。举个例子：
我们先要将node插进index为2的位置也就是将0x888插在0x345前面，那么我们需要改变4个地方，0x888的prev，0x888的next，0x345的prev，0x234的next，也就是说将node的prev赋值为0x234，将node的next赋值为0x345，将0x234赋值为0x888，0x345的prev赋值为0x888，像这样：
这样就完成了中间插入，我们写的searchIndex（）方法就是寻找到指定位置，找到后将返回值赋值给cur，如果index不符合要求，则会报错。
删除第一次出现key的节点
//删除第一次出现key的节点
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else if (cur == last) {
last = last.prev;
last.next = cur.next;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
return;
} else {
cur = cur.next;
}
}
System.out.println("没有你要删除的节点！");
}
同样删除第一个出现的key节点，分为3种情况，第一，头节点时我们要删除的key节点；第二，尾节点是我们要删除的节点；第三，删除的是中间节点。我们先看第一种情况：删除头节点
假设我们要删除12，我们实例化一个节点cur，这个节点用于遍历整个链表，那么当cur.val=12时，进行判断cur是否等于head，当为cur==head节点时，我们将head往后走一个节点到达0x234的位置，并且此时将head.prev置为null。像这样：
那么头节点的删除完成跳出循环，但是这里有一个bug，就是head此时如果为null，那么将head.prev赋值为null就会报出null指针异常，也就是在链表中只有一个节点的时候，因此我们需要再次做出判断，当cur为head时，此时的head是否为null，如果为null，那么将last也赋值为null（只有一个节点时，head和last同时指向这个节点，因此head已经为null，我们只需要将last赋值为null就可以了），否则head.prev赋值为null。像这样：
所以，这样就完成了只有一个节点时的删除，这也进一步体现了数据结构的严谨。我们再看第二种情况：删除尾节点。
这次删除最后一个节点56，此时cur.val为56，并且cur为last，我们将last往前一个节点（last=last.prev），再将last.next赋值成cur.next（null），这样就完成了尾节点的删除。像这样：
我们再看第三种情况：删除中间节点，假如我们要删除34这个节点。
此时cur.val为34，因此我们需要改变cur前驱节点（0x234）的next值，并且改变cur后继节点（0x456）的prev的值。将cur.prev（前驱节点）.next赋值为cur.next，将cur.next（后继节点）.prev赋值为cur.prev。这样就完成了中间节点的删除。像这样：
删除所有key的节点
//删除所有key的节点
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else if (cur == last) {
last = last.prev;
last.next = cur.next;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
//return;
} else {
cur = cur.next;
}
}
}
有了上面的辅助，删除所有的key节点就简单的多了，我们知道删除第一个出现的key节点时，删除后就跳出循环，而删除所有出现的key节点只需要不需要跳出循环，只需要一直往下遍历链表，直到cur为null，跳出循环就可以了。
清空链表
//清空链表
public void clear() {
while (head != null) {
ListNode cur = head.next;
head.prev = null;
head.next = null;
head = cur;
}
last = null;
}
清空链表有两种方法——“暴力”清空和“温柔”清空，我们直到清空链表就是在于没有变量引用它，那么“暴力”清空链表就很简单了，只需要将head和last都置为null就可以解决了，而“温柔”清空就是我们上面的代码，用遍历的方法将所有的节点都置为null，当然最后不能忘记将last也置为null，这样就完成了“温柔”清空链表。
总代码
class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
public ListNode head;//指向双向链表的头节点
public ListNode last;//指向的是尾巴节点
//打印链表
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//得到链表的长度
public int size() {
ListNode cur = head;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
return size;
}
//查找是否包含关键字key
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = last.next;
}
}
//删除第一次出现key的节点
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else if (cur == last) {
last = last.prev;
last.next = cur.next;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
return;
} else {
cur = cur.next;
}
}
System.out.println("没有你要删除的节点！");
}
//删除所有key的节点
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else if (cur == last) {
last = last.prev;
last.next = cur.next;
} else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
//return;
} else {
cur = cur.next;
}
}
}
//寻找index位置的节点
public ListNode searchIndex(int index) {
if (index < 0 || index > size()) {
System.out.println("index位置不合法");
return null;
}
ListNode cur = head;
while (index > 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入，第一个数据节点为下标0
public void addIndex(int index, int data) {
ListNode node = new ListNode(data);
ListNode cur = this.searchIndex(index);
if (index == 0) {
this.addFirst(data);
} else if (index == size()) {
this.addLast(data);
} else {
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
}
//清空链表
public void clear() {
while (head != null) {
ListNode cur = head.next;
head.prev = null;
head.next = null;
head = cur;
}
last = null;
}
}
好了，关于无头双向链表的创建的整个过程就是这么多了，数据结构的知识到这里也告一段落，后面还会介绍其他的数据结构。谢谢各位的点赞，如果有什么问题或者建议，欢迎私信和评论，谢谢大家！