良辰当五日，“双向链表”还 (Java篇)
本篇会加入个人的所谓鱼式疯言
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 ！！！
前言
小伙伴是不是在此之前学习过单向链表，什么是单向链表呢
用我们的专业术语就是： 单向不带头不循环链表
如果还不熟悉的小伙伴们可以点击下方链接进行学习哦 💖 💖 💖
单链表详解链接
而今天的主角是我们的双向链表，什么是双向链表呢，请听下文分解 💥 💥 💥
目录
- LinkedList
- 双向链表的实现
- LinedList 和 ArrayList 的异同
一. LinkedList
1. LinkedList 的简介
LinkedList 的底层是 双向链表结构
由于链表没有将元素存储在连续的空间 中，元素存储在单独的 节点 中，然后通过引用将 节点 连接起来了，因此在在任意位置 插入 或者 删除 元素时，不需要 搬移元素 ，效率比较 高 。
并且在我们Java的集合框架中，LinkedList 也实现了 List 接口
鱼式疯言
LinkedList 这个类有以下五个特点
- LinkedList 实现了 List 接口
- LinkedList 的底层使用了 双向链表
- LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问
- LinkedList 的任意位置 插入 和 删除 元素时效率比较高，时间复杂度为 O(1)
- LinkedList 比较适合任意位置插入的场景
了解了什么是 LinkedList 之后
宝子们是不是和小编一样对这个链表很感兴趣呢
下面来详细说明下他怎么使用吧 💕 💕 💕
1. 尾插数据
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add("杰哥哥");
}
}
这里利用 add() 对 链表 直接进行 尾插 数据
2.指定 index 插入数据
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add(1,"杰哥哥");
}
}
用 Java 重载 的特性,形成了 两个参数列表不同 的 add（）,但方法名同名的方法,从而指定 index 插入数据
鱼式疯言
LinkedList 的 add（） 方法是返回值类型是 boolean 类型
当插入 成功 时返回的是 true
插入 失败 返回是 false
3.删除 index 的数据
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add(1,"杰哥哥");
System.out.println(list.remove(3)); // 删除 "刘富帅"
System.out.println(list.remove(0)); // 删除 "钟少爷"
}
}
利用 List类 中 remove() 可以 删除数据 并带出该数据的 返回值
4.得到 index 数据
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add(1,"杰哥哥");
System.out.println("====== 删除数据 ========");
System.out.println(list.remove(3)); // 删除 "刘富帅"
System.out.println(list.remove(0)); // 删除 "钟少爷"
System.out.println("======= 获取数据 ========");
System.out.println(list.get(0)); // "郭男神"
System.out.println(list.get(1)); // "刘富帅"
}
}
我们可以利用 get（） 根据我们输入的 index 得到我们需要的 数据 💥 💥 💥
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add("吴富婆");
list.add(1,"杰哥哥");
System.out.println("====== 删除数据 ========");
System.out.println(list.remove(3)); // 删除 "刘富帅"
System.out.println(list.remove(0)); // 删除 "钟少爷"
System.out.println("======= 获取数据 ========");
System.out.println(list.get(0)); // "郭男神"
System.out.println(list.get(1)); // "刘富帅"
System.out.println("========= 修改数据 =========");
System.out.println(list.set(0, "彭于晏"));
System.out.println(list.get(0));
}
}
在此处我们可以通过 set（） 修改 index 位置的值 , 并返回修改前 index 的值
5. 查找数据
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add("吴富婆");
list.add(1,"杰哥哥");
System.out.println("====== 删除数据 ========");
System.out.println(list.remove(3)); // 删除 "刘富帅"
System.out.println(list.remove(0)); // 删除 "钟少爷"
System.out.println("======= 获取数据 ========");
System.out.println(list.get(0)); // "郭男神"
System.out.println(list.get(1)); // "刘富帅"
System.out.println("========= 修改数据 =========");
System.out.println(list.set(0, "彭于晏"));
System.out.println(list.get(0));
System.out.println("=========查找数据=========");
String s=new String("郭男神");
if (list.contains(s)) {
System.out.println("该数据的下标为："+ list.indexOf(s));
} else {
System.out.println("未找到该数据,查找失败！");
}
}
}
在这段代码块中
我们通过 contains() 方法搜寻 LinkedList 是否含有该数据
如果存在就返回其 下标 值
不存在就打印 提示信息
鱼式疯言
contains 返回类型： Boolean ,
如果存在就返回 true
不存在就返回 false
说完了LinkedList 的主要方法，我们就不妨动手实现这个双向链表吧 💖 💖 💖
二.双向链表的实现
1. 基本框架
我们首先定义一个 内部类 ,我们可以通过 内部类 来实现我们的一个个 节点 的窗帘
package linklist;
public class MyLinkedList extends AbLinkList{
public static class LinkedNode {
public LinkedNode prev;
public int val;
public LinkedNode next;
public LinkedNode(int val) {
this.val = val;
}
}
}
并在 内部类 的前提下，我们有了前驱节点 prev 数据val 以及后驱节点 next
2.插入数据
. 头插数据
public void addFirst(int data) {
LinkedNode node=new LinkedNode(data);
if (isEmpty()) {
head=last=node;
return;
}
head.prev=node;
node.next=head;
head=node;
}
. 尾插数据
// 尾插数据
@Override
public void addLast(int data) {
LinkedNode node=new LinkedNode(data);
if (isEmpty()) {
head=last=node;
return;
}
last.next=node;
node.prev=last;
last=node;
}
. index 插入数据
public void checkIndex(int index) throws IndexOutOfBoundsException{
if (index size()) {
throw new IndexOutOfBoundsException("下标异常！");
}
}
// 增加某位置的数据
@Override
public boolean addIndex(int index, int data) {
try {
checkIndex(index);
} catch (IndexOutOfBoundsException e) {
e.printStackTrace();
return false;
}
if (index==0) {
addFirst(data);
return true;
}
if (index==size()) {
addLast(data);
return true;
}
LinkedNode cur=head;
LinkedNode node=new LinkedNode(data);
for (int i = 0; i
3. 查找数据
// 坚持是否包含 key
@Override
public boolean contains(int key) {
LinkedNode cur=head;
for (int i = 0; i
4. 删除数据
. 移除 key 一个数据
// 移除一个 key 数据
@Override
public boolean remove(int key) {
if (isEmpty()) {
return false;
}
if (head.val==key) {
// head.val=null;
head=head.next;
head.prev=null;
return true;
}
if (last.val==key) {
// last.val=null;
last=last.prev;
last.next=null;
return true;
}
LinkedNode cur= head;
while (cur !=null) {
if (cur.val==key) {
// cur.val=null;
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
return true;
}
cur=cur.next;
}
return false;
}
. 移除所有 key 的数据
// 移除所以 key 的数据
@Override
public void removeAllKey(int key) {
LinkedNode cur= head.next;
while (cur.next !=null) {
if (cur.val==key) {
// cur.val=null;
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}
cur=cur.next;
}
if (head.val==key) {
// head.val=null;
head=head.next;
head.prev=null;
}
if (last.val==key) {
// last.val=null;
last=last.prev;
last.next=null;
}
}
5. 其他处理
. 获取链表大小
// 双链表长度
@Override
public int size() {
int count=0;
LinkedNode cur=head;
while (cur !=null) {
count++;
cur=cur.next;
}
return count;
}
这里只需要遍历链表 N 次 得到链表大小
. 释放链表
// 释放双链表
@Override
public void clear() {
LinkedNode cur=head;
while (cur !=null) {
LinkedNode tmp=cur.next;
// cur.val=null;
cur=null;
cur=tmp;
}
head=null;
}
逻辑代码展示
. main 函数代码
package Testdmo4.one;
import java.util.LinkedList;
import java.util.List;
public class TestLinked {
public static void main(String[] args) {
List list=new LinkedList();
list.add("钟少爷");
list.add("郭男神");
list.add("刘富帅");
list.add("吴富婆");
list.add(1,"杰哥哥");
System.out.println(list);
System.out.println("====== 删除数据 ========");
System.out.println(list.remove(3)); // 删除 "刘富帅"
System.out.println(list.remove(0)); // 删除 "钟少爷"
System.out.println("======= 获取数据 ========");
System.out.println(list.get(0)); // "郭男神"
System.out.println(list.get(1)); // "刘富帅"
System.out.println("========= 修改数据 =========");
System.out.println(list.set(0, "彭于晏"));
System.out.println(list.get(0));
System.out.println("=========查找数据=========");
String s=new String("郭男神");
if (list.contains(s)) {
System.out.println("该数据的下标为："+ list.indexOf(s));
} else {
System.out.println("未找到该数据,查找失败！");
}
}
}
. 接口代码
package linklist;
public abstract class AbLinkList {
//头插法
public abstract void addFirst(int data);
//尾插法
public abstract void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public abstract boolean addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public abstract boolean contains(int key);
//删除第一次出现关键字为key的节点
public abstract boolean remove(int key);
//删除所有值为key的节点
public abstract void removeAllKey(int key);
//得到双链表的长度
public abstract int size();
// 打印双链表
public abstract void display();
// 释放双链表
public abstract void clear();
}
三. LinedList 和 ArrayList 的异同
鱼式疯言
总之一句话：
顺序表啥都 连续 ，链表只是 物理空间不连续。
顺序表适合访问 和 尾插 和 尾删 ，链表适合 任意插入 和 删除
若有感兴趣的小伙伴可以优化我们的数据类型哦 💖 💖 💖
总结
- LinkedList ： 理解LinkedList 的底层就是我们的双向链表
- 双向链表的实现： 我们用前后引用和内部类的实现了我们的链表
- LinedList 和 ArrayList 的异同： 清楚了 LinkedList 和 ArrayList 的各自的优势和使用场景
可谓收获颇丰啊 💖 💖 💖 💖
如果觉得小编写的还不错的咱可支持 三连 下 ==(定有回访哦) == , 不妥当的咱请评论区 指正
希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编 创作 的最大 动力 💖 💖 💖
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
