📢 文章前提：👇
本文章讨论的是无头双向非循环链表，由于笔试题，项目中……几乎涉及到的都是无头的双向非循环链表，所以本博客围绕上述双向链表种类展开 👇
📋 文章目录：
1. 双向链表的创建
2. 双向链表的头插法
3. 双向链表的尾插法
4. 双向链表实现任意位置插入
5. 查找是否包含关键字key是否在链表中
6. 删除第一次出现关键字为key的节点
7. 删除所有值为key的节点
8.清空链表
9.总体代码
1??. 双向链表的创建
首先双向链表不同于单链表的方面是：双向链表每一个结点会存储当前结点的前驱和后继，所以可以轻松的得到，该结点的前一个结点和后一个结点，并且双向链表中会多一个引用：last（链表的尾结点），这在实现各种功能时会相对简单一些
双向链表的模式图：👇
? 有了这样的模式图，怎样用代码描述呢
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;
}
?? 以上代码是双向链表结点的创建，以及链表头结点和尾结点的创建，基本搭建了一个双向链表的框架，但是各个结点还没有串联起来
2??. 双向链表的头插法
所谓头插法即是在链表的头结点处插入新元素，需要考虑到是否是第一次插入元素，如果第一次插入元素把 head 和 last 都赋值为 node ，如果不是第一次插入正常实现元素的插入即可，那头插法的代码应该如何实现呢 👇
步骤一、以给定的数值创建一个结点，该结点即是用于头插的结点
ListNode node = new ListNode(data);
步骤二、判断是不是第一次插入，即判断现在链表中有没有结点，如果链表中没有结点 head 指向的是 null，判断成立后把 head 和 last 都指向 node ，首个元素的插入即可完成
if (head == null){
head = node;
last = node;
return;
}
步骤三、如果没有进入到上面的 if 语句中，则证明链表中存在结点，利用正常的结点插入操作即可
node.next = head;
head.prev = node;
head = node;
📖 图解头插法：👇
情况一、当链表中不存在任何结点的时的头插法
情况二、当链表中存在其他结点的时的头插法
3??. 双向链表的尾插法
双向链表的尾插法需要分两种情况，和上面头插法考虑的一致，先看链表中有无其他结点，如果没有其他结点，这时 head 和 last 都是 null ，需要把 head 和 last 都指向尾插的结点，如果链表中有其他的结点，就执行正常的插入操作即可👇
??代码实现：
步骤一、以给定的数值创建一个结点（即是进行尾插的结点）
ListNode node = new ListNode(data);
步骤二、判断是不是第一次插入结点，如果是第一次插入结点，把 head 和 last 都指向 node，第一次插入结点的操作即可结束 return 结束本次方法调用
if (head == null){
head = node;
last = node;
return;
}
步骤三、如果没有进入到上面的 if 语句证明链表中存在其他的结点，执行正常的尾插操作
node.prev = last;
last.next = node;
last = node;
📖 图解尾插法： 👇
情况一、第一次插入结点
情况二、链表中有其他结点时的尾插法
4??. 双向链表实现任意位置插入
给定链表的指定位置把新的结点插入到链表中的指定位置中，人为规定链表的下标，从 0 开始一直到链表的长度 - 1
由于该功能需要用到链表的长度，所以先求链表的长度，遍历链表，只要不是链表尾计数器就增加，最后计数器的数值就是链表的长度 👇
??代码实现：
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
?? 插入新结点的代码实现：
步骤一、先判断 index 是不是 0 ，即是链表的头，在链表的头插入结点，即是头插法，调用头插法的方法即可
if (index == 0){
addFirst(data);
return;
}
步骤二、判断 index 的位置是不是链表尾，如果在链表尾插入结点，即是尾插法，调用尾插法的方法即可
if (index == size()){
addLast(data);
return;
}
步骤三、调用找位置的方法找到 index 在链表中的位置
ListNode cur = findpos(index);
findpos 方法：👇先判断 index 的位置合不合法，不合法返回 null，再让 cur 走到指定位置，最后返回 cur
public ListNode findpos(int index){
if (index > size() || index < 0){
return null;
}
ListNode cur = head;
while(index != 0){
index--;
cur = cur.next;
}
return cur;
}
步骤四、判断返回来的 cur 和合法性
if (cur == null){
System.out.println("位置不合法");
return;
}
步骤五、以给定的数据创建一个结点
ListNode node = new ListNode(data);
步骤六、实现链表中间位置结点的插入
cur.prev.next = node;
node.prev = cur.prev;
node.next = cur;
cur.prev = node;
📖 图解中间位置结点的插入 👇
5??. 查找是否包含关键字key是否在链表中
查找给定的数值是否有结点与其对应，遍历链表查找即可，有返回 true，没有返回：false
??代码实现：（过于简单不多解释）
public boolean contain(int key){
ListNode cur = head;
while(cur != null){
if (cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
6??. 删除第一次出现关键字为key的节点
删除第一次出现该数值的结点，遍历链表去进行查找，删除该结点即可
??代码实现：
步骤一、定义一个 cur 去遍历链表
ListNode cur = head;
步骤二、当目前 cur 的数值等于给定的删除数值，即要删除当前 cur 指向的结点，判断分为很多步，下面进行拆解 👇
先进入循环判断数值的一致性：👇
while(cur != null){
if (cur.val == key){
再判断删除的结点是不是头结点，是头结点把 head 向后移动一个结点👇
if (cur == head){
head = head.next;
head 的 prev 也需要指向前一个结点，但是需要判断，如果链表中就一个结点，head.prev会引发空指针异常，所以需要判断，如果链表中有其他结点，在删除头结点的时候还需要把 head 前驱指向 null 👇
if (head != null){
head.prev = null;
}
如果链表中只有一个结点，这时候的 head 是为空的，把 last 也需要指向 null 👇
else{
last = null;
}
步骤三、如果不满足上面的判断，就执行正常的结点删除操作，这时候需要一步判断如果是删除的是尾结点，只需要一步 cur.prev.next = cur.next; 如果是中间结点还要一步 cur.next.prev = cur.prev;👇
else{
cur.prev.next = cur.next;
if(cur != last){
cur.next.prev = cur.prev;
}
}
步骤四、cur 向后走继续判断直到删除成功，由于该功能是删除第一次出现的关键字结点，所以删除成功一次后直接 return 结束本次方法
cur = cur.next;
return;
步骤五、如果循环没有查找到该数值就证明链表中没有该数值的结点，return 结束本次方法
else{
System.out.println("链表不存在该数值");
return;
}
7??. 删除所有值为key的节点
该功能是删除所有值为：key 的结点，即在上面代码基础删除一行代码即可，当删除一个值为：key 的结点时，上面代码就 return 了，在这个功能里把这里的 return 去掉即可，删除一个值为：key 的结点后向后继续查找，进行删除操作,直到 cur 走到最后一个结点
8??. 清空链表
循环把链表的前驱和后继都指向 null 即可
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
}
9??. 整体代码
实现双向链表：👇
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;
}
}
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
public boolean contain(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;
return;
}
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;
return;
}
node.prev = last;
last.next = node;
last = node;
}
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{
cur.prev.next = cur.next;
if(cur != last){
cur.next.prev = cur.prev;
}
}
cur = cur.next;
return;
}
else{
System.out.println("链表不存在该数值");
return;
}
}
}
public void removeAll(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{
cur.prev.next = cur.next;
if(cur != last){
cur.next.prev = cur.prev;
}
}
cur = cur.next;
}
else{
//System.out.println("链表不存在该数值");
return;
}
}
}
public ListNode findpos(int index){
if (index > size() || index < 0){
return null;
}
ListNode cur = head;
while(index != 0){
index--;
cur = cur.next;
}
return cur;
}
public void addIndex(int data, int index){
if (index == 0){
addFirst(data);
return;
}
if (index == size()){
addLast(data);
return;
}
ListNode cur = findpos(index);
if (cur == null){
System.out.println("位置不合法");
return;
}
ListNode node = new ListNode(data);
cur.prev.next = node;
node.prev = cur.prev;
node.next = cur;
cur.prev = node;
}
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
}
}
调用双向链表实现功能：👇
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
/*myLinkedList.addFirst(12);
myLinkedList.addFirst(23);
myLinkedList.addFirst(34);
myLinkedList.addFirst(45);
myLinkedList.addFirst(56);*/
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addLast(56);
System.out.println();
/*myLinkedList.display();
System.out.println();
int ret = myLinkedList.size();
System.out.println(ret);
System.out.println(myLinkedList.contain(82));*/
//myLinkedList.remove(12);
//myLinkedList.removeAll(12);
myLinkedList.addIndex(99,5);
myLinkedList.display();
}
}