界首网站优化公司洛阳便宜网站建设
写在前:
本篇博客主要介绍关于双向链表的一些简答操作实现，其中有有部分代码的实现和前两篇博客中的单向链表是相类似的。例如：查找链表中是否包含关键字key、求链表的长度等。
其余的涉及到prev指向的需要特别注意，区分和单向链表之间的差异。
目录
写在前:
0.首先定义一个结点
1.双向链表-头插法
2.双向链表-尾插法
3.双向链表-任意位置插
4.打印双向链表
5.求双向链表的长度
6.找到双向链表中下标为index的元素
7.查找双向链表中是否包含关键字key
8.删除双向链表中第一个值为key的结点
9.删除双向链表中所有值为key的结点
10.清空双向链表
0.首先定义一个结点
实现双向链表，首先需要自己定义一个结点，结点中包含三个域：val、prev、next;
定义头结点的引用head
定义尾结点的引用last
static class ListNode{public int val;public ListNode prev;//前驱public ListNode next;//后继//提供一个构造方法public ListNode(int val){this.val = val;}}public ListNode head;//代表当前链表头结点的引用public ListNode last;//代表当前链表尾结点的引用1.双向链表-头插法
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;}}2.双向链表-尾插法
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 = node;}}
3.双向链表-任意位置插
public void addIndex(int index,int data){//首先判断插入位置的合法性；if(index < 0 || index >size()){throw new ListIndexOutOfException();}//当下标为0-头插法if(index == 0){addFirst(data);return;}//当下标为size，尾插法if(index == size()){addLast(data);return;}//排除其他情况--正常插入//定义结点cur指向需要插入到的index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);cur.prev.next = node;node.prev = cur.prev;node.next = cur;cur.prev = node;}4.打印双向链表
public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val +" ");cur = cur.next;}System.out.println();}5.求双向链表的长度
public int size(){int len = 0;ListNode cur = head;while(cur != null){len++;cur = cur.next;}return len;}6.找到双向链表中下标为index的元素
private ListNode findIndex(int index){ListNode cur = head;while (index != 0){cur = cur.next;index--;}return cur;}7.查找双向链表中是否包含关键字key
public boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}8.删除双向链表中第一个值为key的结点
public void remove(int key){ListNode cur = head;while (cur != null){//判断cur的值和所要删除的值是否相同//相同if(cur.val == key){//这里需要分多种情况//1.删除的是头结点if(cur == head){head = head.next;//如果链表中有多个结点，则需要将前head.prev置空if(head != null){head.prev = null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next == null){last = last.prev;cur.prev.next = null;}else {//删除的是中间结点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;//不相同}cur = cur.next;}}9.删除双向链表中所有值为key的结点
public void removeAllKey(int key){ListNode cur = head;while (cur != null){//判断cur的值和所要删除的值是否相同//相同if(cur.val == key){//这里需要分多种情况//1.删除的是头结点if(cur == head){head = head.next;//如果链表中有多个结点，则需要将前head.prev置空if(head != null){head.prev = null;}}else {//2.删除的不是头结点//删除的是尾巴结点if(cur.next == null){last = last.prev;cur.prev.next = null;}else {//删除的是中间结点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}//不相同}cur = cur.next;}}10.清空双向链表
public void clear(){ListNode cur = head;while (cur != null){ListNode curNext = cur.next;cur.next = null;cur.prev = null;cur = curNext;}head = null;last = null;}