🚆上一篇文章介绍了单向链表的基本使用，这篇文章将介绍双向链表的基础操作实现。
目录
一、双向不带头非循环链表
🍎链表的创建
- 定义一个 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.没有增容问题，插入一个开辟一个空间。
🍎联系：
- 对数据的组织方法和描述方法一样。
🍓区别总结：
🍎组织：
- 顺序表底层是一个数组，顺序表在逻辑上与物理【内存】上都是连续的。
- 链表是由若干结点组成的一个数据结构，逻辑上是连续的，但在物理【内存】上是不一定连续的。
🍎操作：
- 顺序表适合查找相关的操作。因为可以直接使用下标获取某个位置的元素。
- 链表适合频繁插入和删除操作。链表的插入和删除不需要像顺序表那样移动元素。链表的插入只需要修改指向即可。
- 顺序表还有一个不好的地方，在插入数据时要判断满不满，如果满了要进行扩容，扩容之后不一定都能放完。所以顺序表空间上的利用率不高。
?
?