《Java初阶数据结构》----3.＜线性表---LinkedList与链表＞

用户11288958

发布于 2024-09-24 15:03:48

680

发布于 2024-09-24 15:03:48

文章被收录于专栏：学习

前言

大家好，我目前在学习java。之前也学了一段时间，但是没有发布博客。时间过的真的很快。我会利用好这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！喜欢我文章的兄弟姐妹们可以点赞，收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦，我会持续更新滴，望支持！！！！！！一起加油呀！！！！

语言只是工具，不能决定你好不好找工作，决定你好不好找工作的是你的能力！！！！！

学历本科及以上就够用了！！！！！！！！！！！！！！！！！！

本篇博客主要讲解Java基础语法中的一、链表的简介 1.1链表的概念 1.2链表的八种结构重点掌握两种结构： 1.3单链表的常见方法三、单链表的模拟实现四、LinkedList的模拟实现（双链表） 4.1 什么是LinkedList 4.2LinkedList的使用（及实现）五、ArrayList和LinkedList的区别

一、链表的简介

1.1链表的概念

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

1.2链表的八种结构

下面三种情况组合起来就有八种2^3。

1. 单向或者双向

2.带头或者不带头

3. 循环或者非循环

重点掌握两种

1.无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.无头双向链表（双链表）：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

1.3单链表的常见方法

 // 1、无头单向非循环链表实现
 public class SingleLinkedList {
    //头插法
    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){
   }
    //删除所有值为key的节点
    public void removeAllKey(int key){
   }
    //得到单链表的长度
    public int size(){
        return -1;
   }
 
    public void clear() {
   }
     
    public void display() {}
 }

三、单链表的模拟实现

用内部类的方式定义链表节点。

    //链表是由每一个节点组成的，每一个节点都是一个对象，
//  如果我们去抽象他，它有两个域，节点是链表的一部分，所以我们把节点定义成内部类
    static class ListNode{
        public int val;//节点的值域，整型
        public ListNode next;//下一个节点的地址，要表示节点的地址，因此是ListNode类型

        //由于new新的节点对象时，值可以知道，但是下一个节点的地址是未知的
        //因此我们创建构造方法时，只初始化val的值，next的值默认为null。
        public ListNode(int val) {
            this.val = val;
        }
    }

再定义一个头结点

    //对于链表本身，还应该有个head，来表示当前链表的头结点，这是我们链表的头结点
    //而不是节点的头结点。因此是链表的属性，切勿放到节点类之中。节点类只有两个属性，值域和下一个节点的地址域
    //要表示节点的地址，因此是ListNode类型
    public ListNode head;

简单的初始化链表

    public void easyCreateList(){
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

遍历打印链表

    //注意：head必须一直指向第一个节点的位置，从而来找到这个链表
    //因此我们定义一个ListNode类型的cur。
    public void display(){
        ListNode cur = head;
        if (cur == null){
            System.out.print("当前链表为空，无法打印");
        }
        while (cur != null){
            System.out.printf(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

从某节点开始打印链表

    public void display(ListNode listNode){
        ListNode cur = listNode;
        if (cur == null){
            System.out.print("当前链表为空，无法打印");
        }
        while (cur != null){
            System.out.printf(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

求链表的长度

    //求链表的长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

是否链表是否包含关键字key

    //是否链表是否包含关键字key
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if(key == cur.val){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

头插法

    //头插法，就算链表里一个节点都没有，此方法也可以插入新的节点
    //因此创建链表可以用此方法创建
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

尾插法

    //尾插法，在链表最后面插入元素
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (cur == null){
            head = node;
            return;
        }
        //找到链表的尾节点
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

在指定位置插入元素

    //在指定位置插入元素
    public void addIndex(int index, int data){
        if(index < 0|| index > size()){
            System.out.println("index不合法");
            return;
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
//        ListNode node = new ListNode(data);
//        ListNode pre = head;
//        int count = 0;
//        while (true){
//            pre = pre.next;
//            count++;
//            if (index == count+1){
//                node.next = pre.next;
//                pre.next = node;
//                break;
//            }
//        }
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

找到要删除节点的位置的前一个节点

    //找到要删除节点的位置的前一个节点
    private ListNode findIndexSubOne(int index){
        ListNode cur = head;
        for (int i = 0; i<index-1; i++){
            cur = cur.next;
        }
        return cur;

//        while (index-1 != 0){
//            cur = cur.next;
//            index--;
//        }
//        return cur;
    }

删除第一次出现关键字为key的节点

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head == null){
            System.out.println("当前链表为空，您要删除的数据不存在");
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null){
            System.out.println("没有找到你要删除的数字");
            return;
        }
        cur.next = cur.next.next;
    }

找到key的前驱

    //找到key的前驱
    private ListNode searchPrev(int key){
        ListNode cur = head;
        while (cur.next!=null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

删除链表中元素

    public void removeAllKey(int key){
        if(head == null){
            System.out.println("当前链表为空，无法删除！");
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        if (head.val == key){
            head = head.next;
        }
    }

逆置链表

    public ListNode reverseList(ListNode head){
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }

        ListNode cur = head.next;
        head.next = null;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public void reverseList(){
        if(head == null){
            return;
        }
        if(head.next == null){
            return;
        }

        ListNode cur = head.next;
        head.next = null;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
    }

用栈的方式逆序打印链表

    //用栈的方式逆序打印链表
    public void reverseStackList(){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null){
            stack.push(cur);
            cur=cur.next;
        }
        while (!stack.isEmpty()){
            ListNode top = stack.pop();
            System.out.print(top.val+" ");
        }
        System.out.println();
    }

暴力清空链表

    public void clear(){
        this.head = null;
    }

四、LinkedList的模拟实现（双链表）

4.1 什么是LinkedList

LinkedList：的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：

说明

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

5. LinkedList比较适合任意位置插入的场景

4.2LinkedList的使用（及实现）

1. LinkedList的构造

2. LinkedList的其他常用方法介绍

3.方法的具体实现
使用内部类构造双链表的节点，头节点，尾结点

    static class ListNode{
        private int val;//链表值域
        private ListNode prev;//前节点地址
        private ListNode next;//后节点地址

        //构造方法，初始化链表节点值域
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head; //双向链表的头结点
    public ListNode last;//双向链表的尾巴

头插法

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
            last = node;
            return;
        }
        head.prev =node;
        node.next = head;
        head = node;
    }

尾插法

    //尾插法
    public void addLast(int data){
        ListNode node =new ListNode(data);
        if (head == null){
            head = node;
            last = node;
            return;
        }
        last.next =node;
        node.prev = last;
        last = node;
    }

链表长度

    //链表长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }

打印链表

    //打印链表
    public void display(){
        ListNode cur = head;
        if (cur == null){
            System.out.println("该链表为空，无法打印！");
            return;
        }
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();//方便测试看数据
    }

链表是否包含某元素

    //链表是否包含某元素
    public boolean contains(int key){
        ListNode cur = head;
        if (cur == null){
            System.out.println("该链表为空!");
            return false;
        }
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

检查下标是否异常

    //检查下标是否异常
    public void checkIndex(int index){
        if (index<0 || index >size()){//等于size用尾插法
            throw new indexOutOfException("index 不合法！"+index);
        }
    }

在某位置添加元素

    public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
//            while (index !=0){
//                cur = cur.next;
//                index--;
//            }
        ListNode cur = searchIndexNode(index);
        node.prev=cur.prev;
        node.next=cur;
        cur.prev.next = node;
        cur.prev = node;
    }

找到第n个节点的位置

    //双链表，由于知道了前一个节点的位置
    //因此插进第n个元素时直接找到第n个节点的位置就可以
    private ListNode searchIndexNode(int index){
        ListNode cur =head;
        while (index !=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }