【数据结构与算法】LinkedList与链表(上)

✨hello，进来的小伙伴们，你们好耶！✨

🍊🍊系列专栏：【数据结构与算法】

🌯🌯本篇内容：初始LinkedList与链表，链表的概念，结构，基本实现，详细全面介绍！

🍼🍼作者简介：一名大三在读的科班Java编程小白，我很平凡，学会努力！

🍬🍬码云存放仓库gitee：https://gitee.com/king-zhou-of-java/java-se.git

一、ArrayList的缺陷

通过上篇博客的学习，我们可以通过ArrayList的源码了解到，ArrayList底层使用数组来存储元素。

public class ArrayList extends AbstractList
    implements List, RandomAccess, Cloneable, java.io.Serializable
{
 // ...
 // 默认容量是10
  private static final int DEFAULT_CAPACITY = 10;
  //...
 
  // 数组：用来存储元素
  transient Object[] elementData; // non-private to simplify nested class access
 
  // 有效元素个数
  private int size;
  public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      this.elementData = new Object[initialCapacity];
   } else if (initialCapacity == 0) {
      this.elementData = EMPTY_ELEMENTDATA;
   } else {
      throw new IllegalArgumentException("Illegal Capacity: "+
                       initialCapacity);
   }
 }

因为其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低。因此：java集合中又引入了LinkedList，即链表结构。

二、链表

1、链表的概念及结构

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

即我们可以通俗的理解为比如火车的车厢，没有给这些车厢连接起来，他们只是普通的车厢，互相之间没有任何联系，通过任意一节车厢我们无法确定下一节车厢，那么给他们连接起来组成一列火车的车厢，那么就可以是看做一种链表的结构。

那么在实际的应用中，链表的结构也是多样的。

1.带头或者不带头。

2.单向或双向。

3.循环或非循环。

那么这些组合起来就有8种链表结构，那么我们需要重点掌握的就2种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

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

2、链表的实现

接下来我将模拟链表的功能实现，借助我们的idea工具来演示！

具体的实现细节都在我的代码注释中标明，大家有不懂的可以评论区或者私信我都可以的！

1.首先我们新建一个包LinkedList。

 2.然后我们定义我们的实现类MySingleList，在这个类当中定义一个节点内部类ListNode，当然这个类也可以是静态的都没有什么问题，在这个类当中呢，我们定义成员变量val，和节点next。

    static class ListNode {
        public int val;
        public ListNode next;
 
        public ListNode(int val) {
            this.val = val;
 
        }
    }

3、OK那么接下来我们先创建我们的链表。

    public ListNode head;//不初始化了 默认就是null
 
    public void createList() {//最简单的方式 穷举
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        listNode1.next = listNode2;//当前节点存储下一个元素的地址
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }

看一下结果：说明我们链表创建成功了！

 4.接下来我们打印这个单链表。

    public void display() {
        ListNode cur = this.head;//head不变 让我们的头结点不变 cur去变
        while (cur != null) {
            /**
             为什么是判断cur不等于空 而不是判断cur.next不为空
            我们可以打印出最后一个元素 否则提前判断 不能遍历到最后一个元素
            */
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

运行结果：

 5.计算单链表的长度。

    public int size(){
        ListNode cur = this.head;
        int count =0;
        while(cur!=null){//可不敢写成cur.next！=null 如果链表为空的话 那么cur.next就会发生空指针异常 报错
            count++;
            cur = cur.next;
        }
        return count;
    }

运行结果：

6、查找是否包含关键字key是否在单链表当中

    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

运行结果：这里我给的测试用例是12，所以返回TRUE。

接下来这是三个功能我放在一起演示：

 7.头插法

    public void addFirst(int data){
        //当你在链表当中插入一个数据的时候 一点要记住 先去绑定后面的节点
        //比起顺序表的好处就是 1：插入数的时候不用挪动元素 2：只需要修改指向即可。时间复杂度是O(1)
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

主函数代码：

        mySingleList.addFirst(12);//头插法
        mySingleList.addFirst(23);
        mySingleList.addFirst(34);
        mySingleList.addFirst(45);
        mySingleList.addFirst(56);
        mySingleList.display();

运行结果：注意头插法输出结果是倒序的！

8.尾插法

 public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null){
            this.head = node;
        }else{
            while(cur.next!= null){
                cur = cur.next;
            }
            //走到这个时候已经找到尾巴了
            cur.next = node;
        }
    }

主函数代码：

          mySingleList.addLast(12);
          mySingleList.addLast(23);
          mySingleList.addLast(34);
          mySingleList.addLast(45);
          mySingleList.addLast(56);
          mySingleList.display()

运行结果：尾插法输出结果是正序的！

9.任意位置插入

 public void addIndex(int index,int data){
        if(index<0 || index>size()){
            System.out.println("index位置不合法！");
            throw new IndexWrongFulException("index位置不合法！");
        }
        if(index == 0){//相当于头插法
            addFirst(data);
            return;
        }
        if(index == size()) {//相当于尾插法
            addLast(data);
            return;
        }
        //1.先走index-1步 找到cur
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //2.修改指向
        node.next = cur.next;
        cur.next = node;
    }
    private ListNode findIndexSubOne(int index){
        //定义成private本来就是想只提供给我这个任意位置的插入的函数使用
        // 不想让类外的函数等访问
        ListNode cur = this.head;
        while(index-1!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

主函数代码：

        mySingleList.addIndex(3,666);//在任意位置插入数据
        System.out.println("任意位置插入数据：");
        mySingleList.display();
        mySingleList.remove(34);
        System.out.println("任意位置插入数据后：");
        mySingleList.display();
        System.out.println();

好了，那么由于演示的功能较多，我们一篇博客就不长篇大段的去阐述了，为了我们阅读的体验感和掌握知识的程度，我们下篇博客继续学习LinkedList，期待你的关注与三连！