顺序表、链表（ArrayList、LinkedList）

目录

前言：

顺序表（ArrayList）：

顺序表的原理：

ArrayList源码： 

的含义：​编辑

ArrayList的相关方法：​编辑

向上转型List： 

练习题（杨辉三角）： 

扑克牌游戏：

链表（LinkedList）： 

链表的原理：

自定义链表的实现：

LinkedList源码： 

LinkedList使用注意事项： 

练习题（判断是否是会问链表）： 

迭代器（Iterator）： 

总结： 

前言：

        本篇我们来讲解数据结构中的顺序表和顺序表，因为Java有集合框架，所以可以直接使用类创建对象来完成。

顺序表（ArrayList）：

顺序表的原理：

        顾名思义，就是有顺序的表，类是ArrayList，底层原理是一个数组，当到达最大容量时，会进行扩容。

        当一个数组（顺序表）中存放的基本类型数据时，我们想要全部清除可以直接将有效下标置为0，这样再添加就是覆盖的效果。

        但是如果数组中存放的是引用类型，则不能这样。因为基本类型都会默认初始化，比如整形会默认初始化为0。

        此时引用类型不能直接将有效下标置为0，否则会发生内存泄漏。 因为引用类型开辟的空间没有回收，JVM中，回收算法有很多。最好通过for循环来置空。

for() {
    elem[i] = null;
}

ArrayList源码： 

        接下来我们就来细致观察ArrayList源码： ArrayList底层就是顺序表，继承了AbstractList类，里面重写了toString方法。

        ArrayList底层就是顺序表，继承了AbstractList类，里面重写了toString方法。

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(0,99);
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i) + " ");
    }

    System.out.println(list);
}

        ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。

        我们再来看源码：

        此时就分配了10个空间。 

        所以当使用无参构造器时，第一次添加元素是申请10个空间，之后每次到达上限以后就扩容1.5倍。

<? extends E>的含义：

         因为ArrayList实现了Collection接口。

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);

        ArrayList<Number> list1 = new ArrayList<>(list);

        list1.add(99);
        list1.add(88);
        System.out.println(list1);
    }
}

ArrayList的相关方法：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    System.out.println(list);

    ArrayList<Number> list1 = new ArrayList<>();
    list1.addAll(list);
    list1.remove(new Integer(2));//删除指定对象
    System.out.println(list1);

}

        我们来观察一下代码： 

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    List<Integer> list1 = list.subList(1, 3);//[1,3)
    list1.set(1,99);
    System.out.println(list);
    System.out.println(list1);
}

向上转型List： 

List<List<Integer>> list1 = new ArrayList<>();
list1.add(new ArrayList<>());
list1.add(new ArrayList<>());

        观察这个代码，意思其实是有一个ArrayList类，每一个元素里面是一个ArrayList存放整形的引用类型（List是一个接口）。其实可以理解为二维数组。

练习题（杨辉三角）： 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(1);

        ret.add(list);

        for (int i = 1; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            cur.add(1);

            //获取上一行
            List<Integer> prev = ret.get(i - 1);
            for (int j = 1; j < i; j++) {
                int val = prev.get(j) + prev.get(j - 1);
                cur.add(val);
            }

            //将此行最后一个元素置为1
            cur.add(1);
            ret.add(cur);
        }
        return ret;
    }
}

扑克牌游戏：

public class Test {
    public static void main(String[] args) {
        CardDome cardDome = new CardDome();
        List<Card> cardList = cardDome.buyCard();
        System.out.println("买的牌如下：");
        System.out.println(cardList);

        System.out.println("洗牌");
        cardDome.shuffle(cardList);
        System.out.println(cardList);

        System.out.println("揭牌：");
        cardDome.getCards(cardList);
    }
}
public class CardDome {
    //定义四种花色
    private static final String[] suits = {"♥","♣","♦","♠"};

    //52张
    //J - 11  Q - 12  K - 13
    //买一副牌
    public List<Card> buyCard() {
        List<Card> cardList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 13; j++) {
                Card card = new Card(suits[i], j);
                cardList.add(card);
            }
        }

        return cardList;
    }

    //洗牌
    public void shuffle(List<Card> cardList) {
        //生成随机数
        Random random = new Random();
        //从后向前打乱
        for (int i = cardList.size() - 1; i > 0; i--) {
            //有52张牌
            //第一次生成的就是 0 - 50 的随机数
            int index = random.nextInt(i);

            //index i 交换
            swap(cardList, i, index);
        }
    }

    private void swap(List<Card> cardList, int e1,int e2) {
        Card tmp = cardList.get(e1);
        cardList.set(e1,cardList.get(e2));
        cardList.set(e2,tmp);
    }

    //揭牌
    public void getCards (List<Card> cardList) {
        //3个人
        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();

        List<List<Card>> hand = new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);

        //3个人轮流抓牌5张牌
        for (int i = 0; i < 5; i++) {
            //j 代表人
            for (int j = 0; j < 3; j++) {
                Card card = cardList.remove(0);
                hand.get(j).add(card);
            }
        }

        System.out.println("第一个人揭牌如下：");
        System.out.println(hand1);
        System.out.println("第二个人揭牌如下：");
        System.out.println(hand2);
        System.out.println("第三个人揭牌如下：");
        System.out.println(hand3);

        System.out.println("剩下的牌：");
        System.out.println(cardList);
    }
}
public class Card {
    private String suit;//花色
    private int rank;//数字

    public Card(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public int getRank() {
        return rank;
    }

    public void setRank(int rank) {
        this.rank = rank;
    }

    @Override
    public String toString() {
        return suit + ":" + rank + " ";
    }
}

链表（LinkedList）： 

链表的原理：

        顺序表还是有缺点的，因为每次都是1.5倍扩容，所以有时量大时就会浪费内存，所以就衍生出了链表，不是连续内存，如果了解C语言中的链表，那么将是易如反掌。

自定义链表的实现：

        我们定义head成员，是为了保存头结点。

public class MySingleList {
    //节点使用内部类来写
    static class ListNode {
        public int val;
        public ListNode next;

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

    //定义一个链表的成员的头结点
    public ListNode head;

    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(33);
        ListNode node3 = new ListNode(99);
        ListNode node4 = new ListNode(67);
        ListNode node5 = new ListNode(88);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }
}

LinkedList源码： 

        LinkedList的底层代码，可以发现这就是一个双向循环链表。 LinkedList的任意位置插入和删除元素师效率比较高，时间复杂度为O(1)，比较适合任意位置插入的场景。

        还有很多方法无法注意介绍，大家可以看Structure里面的所有相关方法、属性和内部类。因为效率高，所以底层只使用了双向链表，没有使用单向链表。

LinkedList使用注意事项： 

        当我们使用的是自定义链表时（就是没用Java框架），清空链表，可以直接将头尾置空，也可以逐个将其置空。因为Java有回收算法。

        这里我们使用迭代器进行遍历，我们也可以反向遍历： 

public class Test2 {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        System.out.println(linkedList);

        //通过迭代器遍历链表
        ListIterator<Integer> it1 = linkedList.listIterator();
        while (it1.hasNext()) {
            System.out.print(it1.next() + " ");
        }
        System.out.println();

        System.out.println("===反向===");
        ListIterator<Integer> it2 = linkedList.listIterator(linkedList.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() + " ");
        }
    }
}

 

练习题（判断是否是会问链表）： 

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // write code here
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //翻转slow以后的链表
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode nextPos = cur.next;
            //翻转(利用指针翻转)
            cur.next = slow;
            slow = cur;
            cur = nextPos;
        }

        //从前向后 从后向前
        while(head != slow) {
            if (slow.val != head.val) {
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;

    }
}

迭代器（Iterator）： 

        我们可以利用迭代器进行遍历：

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);

    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        System.out.print(it.next() + " ");
    }
}

总结： 

        这里我还是默认各位都有基础，希望可以对有基础的人有些帮助（更多的是记笔记），感谢各位支持。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/387633.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数模.传染病模型plus

数模.传染病模型plus

一、SIS模型 二、SIR模型 三、SIRS模型 四、SEIR模型
阅读更多...
C++类和对象-C++运算符重载-＞加号运算符重载、左移运算符重载、递增运算符重载、赋值运算符重载、关系运算符重载、函数调用运算符重载

C++类和对象-C++运算符重载-＞加号运算符重载、左移运算符重载、递增运算符重载、赋值运算符重载、关系运算符重载、函数调用运算符重载

#include<iostream> using namespace std; //加号运算符重载 class Person { public: Person() {}; Person(int a, int b) { this->m_A a; this->m_B b; } //1.成员函数实现 号运算符重载 Person operator(const Per…
阅读更多...
【有哪些值得计算机专业学生加入的国企？】

【有哪些值得计算机专业学生加入的国企？】

&#x1f680; 编辑&#xff1a;“码上有前” &#x1f680;作者丨重庆搬砖喵知乎 &#x1f680; 文章简介 &#xff1a;计算机专业未来出路 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; &#x1f680;来源&#xff1a;https://www.zhihu.com/qu…
阅读更多...
PHP+vue+mysql校园学生社团管理系统574cc

PHP+vue+mysql校园学生社团管理系统574cc

运行环境:phpstudy/wamp/xammp等 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat/phpmyadmin 前台功能&#xff1a; 首页&#xff1a;展示社团信息和活动…
阅读更多...
相机图像质量研究(18)常见问题总结：CMOS期间对成像的影响--CFA

相机图像质量研究(18)常见问题总结：CMOS期间对成像的影响--CFA

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…
阅读更多...
MySQL主从环境，主库改端口后，从库如何操作？

MySQL主从环境，主库改端口后，从库如何操作？

主库&#xff1a;mysql-111 从库&#xff1a;mysql-112 主库由3306端口修改成3307后&#xff0c; 从库执行如下命令 mysql> stop slave; mysql> change master to master_port3307; mysql> CHANGE MASTER TO MASTER_HOST192.168.10.111,MASTER_USERbeifen,MASTER_PA…
阅读更多...
Hive on Spark配置

Hive on Spark配置

前提条件 1、安装好Hive&#xff0c;参考&#xff1a;Hive安装部署-CSDN博客 2、下载好Spark安装包&#xff0c;链接&#xff1a;https://pan.baidu.com/s/1plIBKPUAv79WJxBSbdPODw?pwd6666 3、将Spark安装包通过xftp上传到/opt/software 安装部署Spark 1、解压spark-3.3…
阅读更多...
【教程】Kotlin语言学习笔记（二）——数据类型（持续更新）

【教程】Kotlin语言学习笔记（二）——数据类型（持续更新）

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【Kotlin语言学习】系列文章 第一章 《认识Kotlin》 第二章 《数据类型》 文章目录 【Kotlin语言学习】系列文章一、基本数据…
阅读更多...
从零开始做题：逆向 ret2libc jarvisoj level1

从零开始做题：逆向 ret2libc jarvisoj level1

1.题目信息 BUUCTF在线评测 2.原理 篡改栈帧上的返回地址为攻击者手动传入的shellcode所在缓冲区地址&#xff0c;并且该区域有执行权限。 3.解题步骤 3.1 首先使用checksec工具查看它开了啥保护措施 基本全关&#xff0c;栈可执行。 rootpwn_test1604:/ctf/work/9# chec…
阅读更多...
【双指针】【C++算法】1537. 最大得分

【双指针】【C++算法】1537. 最大得分

作者推荐 【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目 本文涉及知识点 双指针 LeetCoce 1537. 最大得分 你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。 一条 合法路径 定义如下&#xff1a; 选择数组 nums1 或者 nums2 开始遍历&…
阅读更多...
极其抽象的SpringSecurity理解

极其抽象的SpringSecurity理解

原始&#xff1a;A → B Security&#xff1a;A → S → B 太抽象了&#xff0c;看不懂啊T_T 抽象故事 故事大概&#xff1a;C是一个大区&#xff0c;拥有巨大的火力&#xff08;C准备联合B吞并掉A&#xff09;&#xff0c;A得到了这个消息&#xff0c;…
阅读更多...
解决‘vue‘ 不是内部或外部命令，也不是可运行的程序（设置全局变量）

解决‘vue‘ 不是内部或外部命令，也不是可运行的程序（设置全局变量）

发现是没有执行&#xff1a; npm install -g vue/cli 但是发现还是不行 此时&#xff0c;我们安装了 Vue CLI&#xff0c;但是在运行 vue ui 命令时出现了问题。这通常是因为全局安装的 Vue CLI 的路径没有被正确地添加到系统的环境变量中。 可以尝试以下几种方法来解决这个问…
阅读更多...
视觉slam十四讲学习笔记（四）相机与图像

视觉slam十四讲学习笔记（四）相机与图像

理解理解针孔相机的模型、内参与径向畸变参数。理解一个空间点是如何投影到相机成像平面的。掌握OpenCV的图像存储与表达方式。学会基本的摄像头标定方法。 目录 前言 一、相机模型 1 针孔相机模型 2 畸变 单目相机的成像过程 3 双目相机模型 4 RGB-D 相机模型 二、图像…
阅读更多...
LEETCODE 315. 计算右侧小于当前元素的个数(归并)

LEETCODE 315. 计算右侧小于当前元素的个数(归并)

class Solution { public: // 将count声明为publicvector<int> count; vector<int> indexs,tmp;public:vector<int> countSmaller(vector<int>& nums) {//归并int left0;int rightnums.size()-1;//计数// vector<int> count(nums.size()); …
阅读更多...
【MATLAB】PSO_BP神经网络回归预测（多输入多输出）算法原理

【MATLAB】PSO_BP神经网络回归预测（多输入多输出）算法原理

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 PSO-BP神经网络回归预测&#xff08;多输入多输出&#xff09;算法是一种结合粒子群优化算法&#xff08;PSO&#xff09;和反向传播&#xff08;BP&#xff09;神经网络的混合算法。该算…
阅读更多...
CSS之选择器、优先级、继承

CSS之选择器、优先级、继承

1.CSS选择器 常用的选择器 <body><div class"parent"><div id"one" style"background: blue" class"child">1<div class"one_one">11</div><div style"background-color: blueviole…
阅读更多...
vue3 Element Plus 基于webstorm练习

vue3 Element Plus 基于webstorm练习

提要 vue是前端框架&#xff0c;Elemen是组件库。前端框架和组件库的区别与联系 nodejs 脚本语言需要一个解析器才能运行&#xff0c;JavaScript是脚本语言&#xff0c;在不同的位置有不一样的解析器&#xff0c;如写入html的js语言&#xff0c;浏览器是它的解析器角色。而对…
阅读更多...
浅谈业务场景中缓存的使用

浅谈业务场景中缓存的使用

业务场景中缓存的使用 一、背景二、缓存分类1.本地缓存2.分布式缓存 三、缓存读写模式1.读请求2.写请求 四、缓存穿透1.缓存空对象2.请求校验3.请求来源限制4.布隆过滤器 五、缓存击穿1.改变过期时间2.串行访问数据库 六、缓存雪崩1.避免集中过期2.提前更新缓存 七、缓存与数据…
阅读更多...
TMGM公司官网介绍

TMGM公司官网介绍

TMGM主要提供外汇、贵金属、原油、股指等CFD产品&#xff0c;客户可以根据个人的交易习惯选择其中一种或多种进行投资。具体来说&#xff0c;TMGM的金融产品包括但不限于货币对、黄金、原油、股票指数等。此外&#xff0c;TMGM还提供多种账户类型以满足不同客户的交易需求。 请…
阅读更多...
error MSB8008: 指定的平台工具集(v143)未安装或无效。请确保选择受支持的 PlatformToolset 值解决办法

error MSB8008: 指定的平台工具集(v143)未安装或无效。请确保选择受支持的 PlatformToolset 值解决办法

右击解决方案&#xff0c;选择属性 将工具集为143的修改为其他&#xff0c;如图 重新编译即可运行
阅读更多...
最新文章

Copyright @ 2022~2023