目录上一篇文章介绍了单向链表的基本使用，这篇文章将介绍双向链表的基础操作实现。
一、双向不带头非循环链表
链表的创建
二、双向不带头非循环链表方法的实现
打印链表
获取链表的长度
判断关键字key是否在链表中
头插法
尾插法
删除第一次出现关键字为key的节点
删除所有值为key的节点
在任意位置插入结点,第一个节点的下标为0
清空链表
三、顺序表和链表的区别与联系
顺序表：一白遮百丑
链表：一(胖黑)毁所有
区别总结：
一、双向不带头非循环链表 链表的创建
定义一个 MylinkedList 类实现链表的基本操作定义一个ListNode类生成结点定义一个 Test 类调用 MylinkedList 类中所实现的方法。
class ListNode{
public int val;
//prev 存放前一个结点的地址
public ListNode prev;
//next 存放后一个结点的地址
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public class MylinkedList {
public ListNode head; //指向双向链表的头结点
public ListNode last; //指向双向链表的尾巴结点
}
二、双向不带头非循环链表方法的实现
打印链表
定义一个引用 cur 遍历链表，当cur == null 时链表遍历结束，打印每个结点的数据。
//打印链表
public void display(){
//与单链表的打印方式一样
ListNode cur = this.head;
while (cur!=null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
获取链表的长度
定义计数器count，遍历链表，count自增，最后返回count。
//得到单链表的长度
public int size(){
ListNode cur = this.head;
int count = 0;
while (cur!=null){
count ++;
cur = cur.next;
}
return count;
}
判断关键字key是否在链表中
遍历链表，如果有数据与关键字key相等就表示找到了，返回true，否则返回false。
//判断关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = this.head;
while (cur!=null){
if(cur.val==key){
return true;
}
cur = cur.next;
}
return false;
}
头插法
插入有两种情况，在没有结点的链表中插入，在有结点的链表插入。没有结点的链表插入：head 与 last 就指向插入的结点node；有结点的链表插入：node的next域保存当前链表的head的地址，head的prev域保存待插入结点node的地址，head指向待插入的结点node。
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(this.head==null){
this.head = node;
this.last = node;
}else {
node.next = this.head;
head.prev = node;
this.head = node;
}
}
尾插法
插入有两种情况，在没有结点的链表中插入，在有结点的链表插入。没有结点的链表插入：head 与 last 就指向插入的结点node；有结点的链表插入：last的next域保存待插入结点node的地址，node的prev域保存当前链表中last的地址，last指向待插入的结点node。
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head==null){
this.head = node;
this.last = node;
}else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
删除第一次出现关键字为key的节点
遍历链表，当第一次cur所指结点的数据与key相同时，则删除该结点，删除结点后直接return。删除结点考虑三种情况：
- 删除头结点：使head指向下一个结点，head移动后，当前结点的prev域置为null。删除中间结点：待删除结点的前一个结点的 next 域保存待删除结点的后一个结点的地址（即待删除结点的next域中的地址），待删除结点的后一个结点的prev域保存待删除结点的前一个结点的地址。删除尾巴结点：待删除结点的前一个结点的next域保存待删除结点的后一个结点的地址（null），使last指向待删除结点的前一个结点。
如果待删除结点的链表只有一个结点，那么删除结点后就要出现空指针异常。只有一个结点时，head向后走一步（head = head.next），head = null；此时也要将 last 置为空（如果只有一个结点，last就指向待删除的结点。last是成员变量，如果将结点删除后，last并不会销毁，所以要将last置为空）。只有当head != null;（有多个结点）时，将head.prev = null; 才不会出错。
//删除第一次出现关键字为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){
cur.prev.next = cur.next;
last = last.prev;
//删除中间结点
}else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
return;
}
cur = cur.next;
}
System.out.println("没有要删除的结点");
}
删除所有值为key的节点
删除第一次出现关键字为key的节点，删除该结点后直接rerun返回，要删除所有值为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){
cur.prev.next = cur.next;
last = last.prev;
//删除中间结点
}else {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
在任意位置插入结点,第一个节点的下标为0
在链表的中间位置插入结点，首先要找到待插入结点的位置，写一个searchIndex 方法查找 index 的位置（因为返回的是地址，所以方法的返回类型是ListNode）写一个方法插入节点，判断传入的参数，如果index<0 或者大于链表的长度位置不合法（判断链表的长度可以直接调用前面所写的返回链表长度的方法）。如果插入的位置为0，就相当于头插，直接调用头插法。如果插入的位置是最后一个结点的后面（因为是从0位置开始，最后一个结点后面的位置就是等于链表的长度），就相当于尾插，就直接调用尾插法。
//找到 index 的位置
public ListNode searchIndex(int index){
ListNode cur = head;
while (index!=0){
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if(index<0||index>size()){
System.out.println("插入位置不合法");
return;
}
//头插
if(index==0){
addFirst(data);
return;
}
//尾插
if(index==size()){
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = searchIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
清空链表
暴力的方法：将head 与 last 直接置为null。
//清空链表
public void clear(){
this.head = null;
this.last = null;
}
温柔的方法：遍历链表，将每个结点的 next 与 prev 都置为null。
//清空链表
public void clear(){
while (head!=null){
ListNode curNext = head.next;
head.prev = null;
head.next = null;
head = curNext;
}
last = null;
}
三、顺序表和链表的区别与联系
顺序表：一白遮百丑
白：空间连续、支持随机访问丑：1.中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。 链表：一(胖黑)毁所有
胖黑：以节点为单位存储，不支持随机访问所有：1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。
联系：
对数据的组织方法和描述方法一样。 区别总结：
组织：
- 顺序表底层是一个数组，顺序表在逻辑上与物理【内存】上都是连续的。链表是由若干结点组成的一个数据结构，逻辑上是连续的，但在物理【内存】上是不一定连续的。
操作：
- 顺序表适合查找相关的操作。因为可以直接使用下标获取某个位置的元素。链表适合频繁插入和删除操作。链表的插入和删除不需要像顺序表那样移动元素。链表的插入只需要修改指向即可。顺序表还有一个不好的地方，在插入数据时要判断满不满，如果满了要进行扩容，扩容之后不一定都能放完。所以顺序表空间上的利用率不高。
