😽个人主页： tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主
🌈梦的目标：努力学习，向Java进发，拼搏一切，让自己的未来不会有遗憾。
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨
本章讲解内容：链表 的讲解
使用编译器：IDEA
一.链表概念
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
逻辑结构：
注：1、如上图，相当于火车车厢，每一节都相连在一起。
2、各个结点连接的方式：通过地址连接，在内存当中，相邻结点在内存中不一定相邻。
3、所有结点都在 堆 中申请出来。
4、 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
二.链表的分类
1.单向、双向链表
注：无论单向还是双向，都是一个结点存储着下（上）一个结点。
2.带头、不带头结点 链表
注：无头和带头结点的主要区别：有一个起始结点。
3.循环、非循环链表
循环链表，就是指：头、尾结点有联系。
在链表结构中，这是主要的链表，但是这些链表种类还可以结合，如：带头双向循环链表、双向循环链表等等。
链表的种类很多，但都大同小异，我们主要学习两种链表：
1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2、无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
三.无头单向非循环链表的实现
3.1创建简单链表
重点：每个结点存储着下一个结点的地址。
创建链表代码实现：
public class SingleLinkedList { static class List{ int item; // 存储数据 List next; // 指向下一个结点 public List(int item) { this.item = item; } public List() {}; } //各种链表实现方法 //头插法 public void addFirst(int data){ } //尾插法 public void addLast(int data){ } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ return false; } //删除第一次出现关键字为key的节点 public void remove(int key){ } //得到单链表的长度 public int size(){ return -1; } //链表的清空 public void clear() { } //展示链表 public void display() {}
3.2 链表基本方法实现
1.遍历链表元素
public void show() { //这里不是定义了一个节点 这里只是一个引用 ListNode cur = head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
2.获取链表长度
public int size(){ int count = 0; ListNode cur = head; while (cur != null) { count++; cur = cur.next; } return count; }
3.查询数据
public boolean contains(int key){ ListNode cur = head; while (cur != null) { //如果val值 是引用类型 那么这里得用equals来进行比较！！！ if(cur.val == key) { return true; } cur = cur.next; } return false; }
4.链表的清空
public void clear() { //将所有结点都置空，更为安全 while (head != null) { ListNode headNext = head.next; head.next = null; head = headNext; } }
3.3四大基本功能
3.3.1 、增加元素结点
1.头插法：将新增结点放在链表的头部。
public void addFirst(int data){ ListNode node = new ListNode(data); node.next = head; head = node; }
2.尾插法：将新增结点直接连接在链表的尾部
public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { head = node; return; } ListNode cur = head; while (cur.next != null) { cur = cur.next; } //cur 指向的节点就是尾巴节点 cur.next = node; }
3.选择下标值，添加结点
public void addIndex(int index,int data){ int len = size(); //0、判断index位置的合法性 if(index < 0 || index > len) { throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index); } if(index == 0) { addFirst(data); return; } if(index == len) { addLast(data); return; } //1、先找到index-1位置的节点 ListNode cur = findIndex(index); //2、进行插入 ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; }
3.3.2.查找元素结点
查找一个元素，返回对应的下标值。
public ListNode findIndex(int index) { ListNode cur = head; while (index - 1 != 0) { cur = cur.next; index--; } return cur;//index-1位置的节点 }
3.3.3.删除元素结点
先找到对应的下标值，然后进行删除。删除方法，前一个结点连接到删除结点的后一个结点。
如图，先断开d2与d3的连接，然后d2直接连接d4
代码实现：
//删除第一次出现关键字为key的节点 public void remove(int key){ if(head == null) { return; } //当删除结点为头结点 if(head.val == key) { head = head.next; return; } ListNode prev = searchPrev(key); //返回待删除结点的前一个结点 if(prev == null) { System.out.println("没有这个数据！"); return; } ListNode del = prev.next; prev.next = del.next; } private ListNode searchPrev(int key) { ListNode prev = head; while (prev.next != null) { if(prev.next.val == key) { return prev; }else { prev = prev.next; } } return null; }
3.3.4.结点信息修改
修改指定下标值的结点元素
public void searchPrev(int num,int date) { ListNode prev = head; for(int i=0;i<num-1;i++) { prev = prev.next; } prev.val=date; }
四.LinkedList是什么？
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
如图所示：1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问。 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
五.LinkedList使用方法
方法 |
解释 | |
| 构造方法 | LinkedList() | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器中元素构造List |
| 常用方法 | boolean add(E e) | 尾插e |
| void add(int index,E element) | 将e插入到index位置 | |
| boolean addAII(Collection<? extends E> c) | 尾插c中的元素 | |
E remove(int index) |
删除index位置元素 |
|
boolean remove(Object o) |
删除遇到的第一个o | |
| E get( int index) | 获取下标index位置元素 | |
| void clear() | 清空 |
总结
链表入门很简单，但是却有很多很难的题目，而我们只有将这些题目全部掌握了，对之后的栈、堆等题有更加深刻的知识。
题目推荐：1、移除链表元素 2、反转单链表 3、返回链表中间节点
4、 合并两个有序链表 5、 合并两个有序链表 6. 相交链表 7、回文链表
