那么我们正式踏入了对数据结构的学习
本篇博客教大家学习单链表
以下为代码实现的思维导图

想要理解清楚的小伙伴一定要耐心看完哦

单链表的概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

链式的结构分为一个一个节点，什么是节点呢？

节点：

1. 数值域
2. next域（可以理解为指针域或是引用域）

注意：👇

1. 那么我们在下面的图中可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 现实中的节点一般都是从堆上申请的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续，下图中的0×11，0×12就是连续的特殊情况

这样单向，带头，非循环的，我们称其中的节点为傀儡节点，那么什么是双向呢？



那么什么是不带头的呢？，就是没有数值域为空的节点
那么什么是循环呢？就是最后的next域不指向null,而是指向首节点，构成循环

这些条件排列组合一下会产生许许多多的链表，但我们常用的链表主要是以下两种：

1. 无头单向非循环链表：结构比较简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构。

2. 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

单链表的实现

/**
 * @author Gremmie102
 * @date 2022/4/28 9:24
 * @purpose :单链表的实现
 */publicclassMySingleList{staticclassListNode{publicint val;//数值域publicListNode next;//存储下一个节点的地址publicListNode(int val){this.val= val;}}publicListNode head;//代表单链表的头结点的引用/**
     * 这里只是简单的进行，链表的构造。
     */publicvoidcreateList(){ListNode listNode1=newListNode(12);ListNode listNode2=newListNode(23);ListNode listNode3=newListNode(34);ListNode listNode4=newListNode(45);ListNode listNode5=newListNode(56);

        listNode1.next= listNode2;

        listNode2.next= listNode3;
        listNode3.next= listNode4;
        listNode4.next= listNode5;this.head= listNode1;}publicvoiddisplay(){ListNode cur= head;while(cur!=null){System.out.print(cur.val+" ");
            cur= cur.next;}System.out.println();}/**
     * 头插法
     * O(1)
     */publicvoidaddFirst(int data){ListNode node=newListNode(data);/*if(this.head == null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }*/
        node.next=this.head;this.head= node;}//尾插法 O(n)publicvoidaddLast(int data){ListNode node=newListNode(data);if(head==null){
            head= node;}else{ListNode cur= head;while(cur.next!=null){
                cur= cur.next;}//cur.next == null;
            cur.next= node;}}/**
     * 任意位置插入,第一个数据节点为0号下标
     * 指定位置插入
     */publicvoidaddIndex(int index,int data)throwsMySingleListIndexOutOfException{checkIndexAdd(index);if(index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}ListNode node=newListNode(data);ListNode cur=findIndexSubOne(index);
        node.next= cur.next;
        cur.next= node;}/**
     * 找到index-1位置的节点
     * @param index
     * @return 该节点的地址
     */privateListNodefindIndexSubOne(int index){ListNode cur=this.head;while(index-1!=0){
            cur= cur.next;
            index--;}return cur;}privatevoidcheckIndexAdd(int index){if(index<0|| index>size()){thrownewMySingleListIndexOutOfException("任意位置插入的时候，index不合法！");}}//查找是否包含关键字key是否在单链表当中  314publicbooleancontains(int key){//head == nullListNode cur=this.head;//cur != null 说明 没有遍历完 链表while(cur!=null){if(cur.val== key){returntrue;}
            cur= cur.next;}returnfalse;}//删除第一次出现关键字为key的节点publicvoidremove(int key){if(this.head==null){System.out.println("此时链表为空，不能进行删除！");return;}if(this.head.val== key){//判断 第一个节点是不是等于我要删除的节点this.head=this.head.next;return;}ListNode cur=this.head;while(cur.next!=null){if(cur.next.val== key){//进行删除了ListNode del= cur.next;
                cur.next= del.next;return;}
            cur= cur.next;}}//删除所有值为key的节点publicvoidremoveAllKey(int key){while(true){remove(key);if(this.contains(key)){continue;}elsebreak;}}//得到单链表的长度publicintsize(){int count=0;ListNode cur=this.head;while(cur!=null){
            count++;
            cur= cur.next;}return count;}publicvoidclear(){this.head=null;}}

LinkedList

那么上面的代码是我们自己实现的单链表。
在Java中，已经有大佬帮我们写好了单链表，叫做LinkedList

使用方式

方法

publicstaticvoidmain(String[] args){LinkedList<Integer> list=newLinkedList<>();
    list.add(1);// add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0
    list.add(0,0);// add(index, elem): 在index位置插入元素elemSystem.out.println(list);
    list.remove();// remove(): 删除第一个元素，内部调用的是removeFirst()
    list.removeFirst();// removeFirst(): 删除第一个元素
    list.removeLast();// removeLast(): 删除最后元素
    list.remove(1);// remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif(!list.contains(1)){
        list.add(0,1);}
    list.add(1);System.out.println(list);System.out.println(list.indexOf(1));// indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1));// lastIndexOf(elem): 从后往前找第一个1的位置int elem= list.get(0);// get(index): 获取指定位置元素
    list.set(0,100);// set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy= list.subList(0,3);System.out.println(list);System.out.println(copy);
    list.clear();// 将list中元素清空System.out.println(list.size());}

链表后续还会更新题目，大家拭目以待
最近临近考试，学习任务繁重
如果文章有哪里不足的地方麻烦大佬指出
感谢阅读~