图解双链表(Java实现) (2)

2 head节点指向head.next(这样head就指向我们需要的第一个节点了，前面节点就被删除成功，如果有c++等语言第一个被孤立的节点删除释放即可，但Java会自动释放)

尾删除

尾删除需要注意的就是删除不为空时候尾删除只和tail节点有关。记得在普通链表中，我们删除尾节点需要找到尾节点的前驱节点。需要遍历整个表，而双向链表可以直接从尾节点遍历到前面。

尾删除就是删除双向链表中的最后一个节点，也就是尾指针所指向的那个节点，思想和头删除的思想一致，具体步骤为：

tail.pre.next=null尾节点的前一个节点(pre)的后驱节点等于null

tail=tail.pre 尾节点指向它的前驱节点，此时尾节点由于步骤1next已经为null。完成删除

普通删除

普通删除需要重点掌握，普通删除要妥善处理好待删除节点的前后关系，具体流程如下：

1：找打待删除节点node的前驱节点prenode(prenode.next是要删除的节点)

2 : prenode.next.next.pre=prenode.（将待删除node的后驱节点aftnode的pre指针指向prenode，等价于aftnode.pre=prenode）

3: prenode.next=prenode.next.next;此时node被跳过成功删除。

完成删除整个流程的动态图为：

实现与测试

通过上面的思路简单的实现一下双链表，当然有些地方命名不太规范，实现效率有待提升，主要目的还是带着大家理解。

代码：

/* * 不带头节点的 */ public class doubleList<T> { class node<T> { T data; node<T> pre; node<T> next; public node() { } public node(T data) { this.data = data; } } private node<T> head;// 头节点 private node<T> tail;// 尾节点 private int length; public doubleList() { head = null; tail = head; length = 0; } boolean isEmpty() { return length == 0 ? true : false; } void addFirst(T data) { node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } else { teamNode.next = head; head = teamNode; } length++; } void add(T data)// 默认尾节点插入 { node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } else { tail.next = teamNode; teamNode.pre=tail; tail = teamNode; } length++; } int length() { return length; } T getElum(int index)//为了简单统一从头找 { node<T> team=head; for(int i=0;i<index;i++)//不带头节点 遍历次数-1 { team=team.next; } return team.data; } void add(int index, T data)// 编号插入 { if (index == 0) { addFirst(data); } else if (index == length) { add(data); } else {// 重头戏 node teampre = head;// 为插入的前驱 // 无头节点，index-1位置找到前驱节点 for (int i = 0; i < index -1; i++) { teampre = teampre.next; } node<T> team = new node(data);// a c 中插入B 找打a team.next = teampre.next;// B.next=c teampre.next.pre = team;// c.pre=B team.pre = teampre;// 关联a B teampre.next = team; length++; } } void deleteFirst()// 头部删除 { if (length == 1)// 只有一个元素 { head = null; tail = head; length--; } else { head = head.next; length--; } } void deleteLast() { if(length==1) { head=null; tail=head; length--; } else { tail.pre.next=null; tail=tail.pre; length--; } } void delete(int index) { if(index==0)deleteFirst(); else if (index==length-1) { deleteLast(); } else {//删除 为了理解统一从头找那个节点 node<T>team=head; for(int i=0;i<index-1;i++) { team=team.next; } //team 此时为要删除的前节点 a c 插入B a为team team.next.next.pre=team;//c的前驱变成a team.next=team.next.next;//a的后驱变成c length--; } } void set(int index,T data) { node<T>team=head; for(int i=0;i<index-1;i++) { team=team.next; } team.data=data; } @Override public String toString() { node<T> team = head; String vaString = ""; while (team != null) { vaString += team.data + " "; team = team.next; } return vaString; } }

测试：

结语