java：

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < groupSizes.length; i++) {
            int x = groupSizes[i];
            if (map.get(x) == null) map.put(x, new ArrayList<>()); // 初始化
            map.get(x).add(i);
            if (map.get(x).size() == x) {  //获取长度： 数组length属性    ArrayList size()方法
                res.add(map.get(x));
                map.put(x, null);
            }
        }
        return res;
    }
}

MapReduce

提交job：job.writForCompletion(true)    submit
执行job

一：
InputFormat ：切片  +  按行读数据     可以获取元数据(nn)处理信息

抽象方法：
    getSplits    -->  FileInputFormat
        1. ignoreDirs = false （默认情况下不忽略文件夹）       获取真实数据
        2. if (  isSplitable(job, path) )  判断当前文件是否可切    主要考虑压缩文件
        3. 计算切片 
        Math.max(minSize，Math.min(maxSize, blockSize))   minSize:1    maxSize:L  blockSize:128
        4. 判断剩余大小是否需要继续切分     避免产生过多的小文件
        while( 剩余大小/ 切片大小 > 1.1)
    createRecordReader
切片128m： 数据块存在dn上以128为单位，切片不合适需要跨机架(dn在不同机架上)读取，影响吞吐量
每个split切片对应一个MT，默认切片大小=BlockSize
Inputsplit：切片对象大小，切片路径

二：
CombineTextInputFormat切片：适用于小文件的处理场景   
     CombineTextInputFormat.setMaxInputSplitSize（）  虚拟存储过程
     job.setinputFormatClass(CombineTextInputFormat.class)

三：
Shuffle流程      人为可干预 分区 排序
Map  -->  写入<k,v>到环形缓冲区(元数据：分区编号，kv索引)80%反向  --> 对分区中的数据按照key快排  -->           落盘：溢出合并分区(Combiner) -->  按照分区进行分区内归并排序   -->  写磁盘：一个MT对应一个文件
MT对应文件   -->   拷贝到内存缓冲区(内存不够溢写到磁盘)   -->   分区内将每个Map来的数据进行归并排序   -->   
按照key分组   -->   调用Reduce方法

四：
Partitioner 分区   
NewOutputCollector  -->  partitioner.getPartition(key,value,partitions)  partitions为ReduceTask的数量 --> 
partitions = jobContext.getNumReduceTasks()  -->  if (partitions > 1)  分区 key.hashCode() % numReduceTasks
优先有自定的Partitioner的实现( 通过job.partitioner.class 获取实现类的class )
    job.setNumReduceTasks()     多有少个分区                                                                                  
    job.setPartitionerClass(MyPartitioner .class)    (MyPartitioner extends Partitioner)        分区规则的选取

五：
WriteableComparable 排序         只有 key 支持排序
MT 和 RT 都会按照key排序是hadoop的默认行为
MT：将处理结果放入环形缓冲区当到达阈值时，对缓冲区中的数据进行一次快排后溢写到磁盘，当数据处理完毕后，对磁盘上的所有文件进行归并排序
RT：从MT上拷贝相应数据文件，文件大小超过阈值溢写到磁盘上，磁盘上文件的数目达到阈值进行一次归并排序生成一个更大的文件，当所有数据拷贝完毕后，RT统一对内存和磁盘上的所有数据进行一次归并排序

    implements WritableComparable<> ：序列化和比较器同时实现    
        Override:  compareTo() 
    MyWritableComparator extends WritableComparator ：
        1. public MyWritableComparator( ) { super(FlowBena.class, ture) } ：声明无参构造 指定当前比较器对象为谁提供
        2. Override： compare(WritableComparable a, WritableComparable, b)
            FlowBena abena = (FlowBean) a;
            FlowBean bbena = (FlowBean) b;
            return -abean.getSumFlow().conpareTo(bben.getSumFlow())   属性比较倒序
        3. FlowBean implements WritableComparable<FlowBean>
        4. job.setSortComparatorClass(MyWritableComparator.class)

       1. comparator = job.getOutputKeyComparator( );  --> if ( theClass != null )     
     return 反射获取当前实现类  / 默认为null，自己实现comparator并set则为自己的实现类
       2. if ( theClass == null )   return getMapOutputKeyClass( )  ->  Map端输出的Key，需要实现WritableComparable接口
    job.setMapOutputKeyClass( )
       3. WritableComparator comparator = comparartors.get(key)    根据key获取比较器对象
    ConcurrentHashMap：并行hashmap<k,v>
    static { define(LongWritable.class, new Comparator()) }  --> comparators.put(key, comparator)
        在静态代码块中 实例化比较器对象，并且放入Map中做value        默认生成
    if (comparator == null )  comparator = new WritableComparator(key, conf, true)   
        自定义的才能走到这一步，拿到key的实例化对象  return
    able：需要验证程序的数据类型是不是hadoop默认的数据类型，是在类加载的时候将比较器加载到HashMap中，
从HashMap中按key取值进行比较，没拿到强制加载一遍( 考虑jvm的GC操作 )，如果强制加载还没拿到说明是你自己的数据类型不是hadoop默认的数据类型，直接 new WritableComparator(key, conf, true) 比较器

六：
hadoop自身的数据类型如何获得的：
无参构造绑定 -->  static{ } 静态代码块注册  -->  向HashMap中 put<k,v>
结论： 当Text类加载时，会将Text.class 作为 Key ；它的比较器对象作为Value 放入到一个Comparators Map容器中

Combiner：合并文件   减轻IO压力，RT压力       ( 看对业务需求是否有影响  )
    第一次从内存溢写到磁盘时用Combiner 第二次发生归并排序时也进行Combiner   
    可以减小Reduce端的压力，相当于提前进行了一次Reduce操作

    extends Reducer<>      重写reduce方法
    job.setCombinerClass(MyCombiner.class)

OutputFormat
    getReaordWriter( )    按行写数据  return new LineRecordWriter<>( )
    checkOutputSpecs    检查路径

七：

    ReduceJoin的思想：
           ①：分析文件之间的关系，然后定位关联字段
           ②：在Map阶段对多个文件进行数据整合，并且让关联字段作为输出数据的key，整合过程中要标记数据来源 
           ③：当一组相同key的values进入Reduce阶段的reduce方法中第一步：先把两个文件
              数据分离出来，分别放到各自的对象中维护。
           ④：把当前一组维护好的数据进行关联操作，得到想要的数据结果。

八：

    提交job阶段
           ①：检查输入输出路径的合法性
           ②：计算切片
           ③：加载分布式缓存的信息(看是否需要)
           ④：拷贝job需要的资源到指定路径 HDFS下
                1.jar包
                2.切片信息
                3.配置信息
           ⑤：submit job  执行job，并且监控它

网络编程

网络编程三要素：
    (1) IP地址
    (2) 端口号
    (3) 网络协议(TCP UDP)

TCP建立连接需要三次握手  断开连接需要四次挥手
例如：MySQL数据库连接，连接一旦获得是非常宝贵的所以用到数据库连接池
    (1) 控制连接的数量     (连接数量上限， 等待)
    (2) 重复使用同一个连接

TCP：数据丢包需要进行重传

端口号
Socket相关类
作用：让Java程序和网卡驱动进行交互，只要是网络通信一方，都要有Socket对象

施工中ing。。。

IO流

• FileInputStream 和 FileReader ，对应文件必须存在，否则报FileNotFoundException异常

• FileOutputStream 和 FileWriter，对应文件不存在会自动创建，若存在会覆盖 参数：true为追加模式

文件IO流程序编写步骤：
    (1) 创建IO流对象
        new File()
        FileSystem.get()
    (2) 读/写操作
        调用read() / write() 方法   读写
        FileInputStream: 借助byte[]进行读
        FileReader: 借助char[] 进行读
            FileInputStream：一定要存在
            FileOutputStream：一定不存在，会帮你创建
    (3) 关闭 close
        "hello" --> bw --> fw --> "test/io.txt"
        bw.close()  // 需要刷数据出去
        fw.close()

        如果使用 try-catch-finally 处理异常则需要在finally中close()
        如果是在 try 小括号内new的连接对象和操作  则会自动关闭流资源

缓冲IO流类型：   提高读写效率
BufferoutputStream：字节输入缓冲流
BufferReader：字符输入缓冲流    默认按行读取
    BufferReader br = new BufferReader(new InputStreamReader(System.in))
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
    bw.close() /  bw.flush()    

转化(编码/解码)IO流类型：   必须依赖于字节流使用
目的： ① 设计编码解码
       ② 单纯为了流类型转换 (BufferReader有按行读的功能，InputStreamReader(System.in) 这样合作转化可以按行读取)
    InputStreamReader
        解码： 字节  -->  字符                (数据)
            字节输入流  包装为  字符输入流    (流)
    OutputStreamWriter
        编码： 字符  -->  字节                (数据)
            字节输出流  包装为  字符输出流    (流)

对象IO流类型：   不能单独使用
    JAVA 的各种数据类型
ObjectInputStream                         int /  readint()
ObjectOutputStream

使用ObjectOutputStream输出的内容要用ObjectInputStream读取，且读写顺序一致

自定义类用对象IO流读写需要  implements Serializable

对象的序列化：把对象转化为字节序列
    1.内存--> 磁盘(对象序列化为字节，对象持久化)     2.网络传输

对象的反序列化：把字节序列重新构建为一个Java对象

MapReduce

• WordCountMapper

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Mapper;

import java.io.IOException;
/*
    参数：                                  数据类型：
    KEYIN: 表示当前行数在文件中的偏移量         LongWritable
    VALUEIN：表示一行数据                    Text
    KEYOUT： 表示一个单词                    Text
    VALUEOUT：针对当前单词的标记              IntWritable
 */
public class WordCountMapper extends Mapper<LongWritable, Text,Text, IntWritable> {

    private Text outk = new Text();
    private IntWritable outv = new IntWritable(1);

    // 重写map方法写业务逻辑
    @Override
    protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        // 获取当前行数据
        String lineData = value.toString(); // value 没有split方法,字符串有
        // 按业务要求切割字符串
        String[] datas = lineData.split(" ");
        // 输出 key value  context.write()   数据类型准话-->封装对象
        for (String data : datas) {
            outk.set(data);
            context.write(outk,outv);
        }
    }
}

• WordCountReduce

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Reducer;

import java.io.IOException;

public class WordCountReduce extends Reducer<Text, IntWritable,Text,IntWritable> {
    private IntWritable outv = new IntWritable();

    @Override
    protected void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
        int sum = 0;
        // 遍历相同key的一组values 进行累加
        for (IntWritable value : values) {
            // 注意数据类型的匹配   用  .get()  方法可以获取当前对象的int值
            sum += value.get();
        }
        outv.set(sum);
        context.write(key,outv);
    }
}

• WordCountDriver

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

import java.io.IOException;

// 提交job set基本环境
public class WordCountDriver {
    // 程序的入口
    public static void main(String[] args) throws IOException, InterruptedException, ClassNotFoundException {
        Configuration conf = new Configuration();
        // 声明job对象
        Job job = Job.getInstance(conf);
        // 针对job做内容的配置
        // 1.指定当前job的mapper和reducer
        job.setMapperClass(WordCountMapper.class); // 通过反射获取实例对象
        job.setReducerClass(WordCountReduce.class);
        // 2.指定当前job的map阶段输出的key 和 value 类型
        job.setMapOutputKeyClass(Text.class);
        job.setMapOutputValueClass(IntWritable.class);
        // 3.指定当前job的最终输出的key 和 value的类型
        job.setOutputValueClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        // 4.指定job的输入输出路径
        FileInputFormat.addInputPath(job,new Path(""));
        FileOutputFormat.setOutputPath(job,new Path(""));
        // 提交job
        job.waitForCompletion(true); // 全程监控
    }
}

切片（128m）--> MapTask (1.整行读入2.按split切分3.KV形式存入Map) --> 分区(根据业务需求，分区需要将结果溢写到磁盘) 
--> Reduce(根据分区去拉取Map中的数据，一个分区对应一个Reduce) --> 各分区聚合数据 -->输出到文件(落盘)

MapTask ReduceTask   分区 排序 衔接   Task即为JAVA进程
一行调用一次：Map（序列号，一行内容）每个<k,v>调用一次
ReduceTask每一组相同的Key调用一次
12.MapReduce代码
Mapper Reduce Driver

施工中。。。

HDFS分布式文件管理系统

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.junit.Test;

import java.io.IOException;
import java.net.URI;
import java.net.URISyntaxException;


public class HdfsClient {
    @Test
    public void testMkdirs() throws IOException, URISyntaxException, InterruptedException {

        // 1 获取文件系统
        Configuration configuration = new Configuration();

        // FileSystem fs = FileSystem.get(new URI("hdfs://hadoop102:8020"), configuration);
        FileSystem fs = FileSystem.get(new URI("hdfs://hadoop102:8020"), configuration,"atguigu");

        // 2 创建目录
        fs.mkdirs(new Path("/xiyou/huaguoshan/"));

        // 3 关闭资源
        fs.close();


    }
}

1. 高可用
自动保存多个副本(分布式多副本存储)，一个副本丢失可以自动恢复（副本自动恢复namenode->datanode）
2. HBase
二次封装(缓存) HDFS  优化低延迟访问数据
3.
HDFS使用场景：一次读入，多次读出
无法高效的对小文件进行存储    、  元数据加载到内存中   、  不能多线程写    、   仅支持append(追加)   不支持随机修改
4.
NameNode：管理hdfs名称空间，配置副本策略，管理Block映射信息，处理客户端读写请求
DataNode：  存储真实的数据块， 执行数据块的读/写操作
5.
Client：客户端
文件切分，Block(128M) 上传 ，与namenode交互，获取文件位置信息， 与DataNode交互 读数据到本地
Clcient命令管理访问HDFS     / namenode格式化  
6.
SecondaryNameNode：
定期合并 Fsimage 和 Edit 并且推送给namenode(元数据)
辅助恢复Namenode(有丢失风险)
7.
HDFS文件 块大小  (参数：dfs.blocksize)  128M
寻址时间为传输(下载)时间的1%时，为最佳状态
下载： 写磁盘(本地IO)   从HDFS->磁盘   磁盘的传输速率100MB/s
总结：块大小由磁盘的读写速率决定
8. web端  端口号   9870   19888
9. HDFS不适合读小文件
namenode在内存中存有上限，datanode存数据量小，吞吐量低
寻址时间过长(全盘扫描)，下载飞快 1%

---------

10.HDFS读/写流程八股   nn 2nn dn 工作机制整理   MrAppMaster一对多
Write： 写数据流程
Client ：                                         HDFS(nn dn)：
create 对象  DistributedFileSystem       
    -----发送上传文件请求------>    (nn)1.判断权限2.路径是否合理
    <------响应连接--------
    ----Block申请namenode-->
    <----返回datanode地址--- 1.机架最短路(一个本地节点其他机架节点)2.d1d2d3 三个点存数据(副本原则)
    --write  FSDataOutputStream->
    --向namenode请求Block传输通道->    
    <---应答成功-----------  1.并发传送数据
    -----64kPackets传输------->
    ---------传输数据完成------>

---------


Read：读数据
Client:                                              HDFS(nn dn)
create DistributedFileSystem
    -----发送下载文件请求------>
    <---返回目标的元数据(dn)----
    --read  FSDataInputStream->
    ----请求dn1,dn2(最近的dn)-->
    <------传输数据---------------
close()

-----------

nn工作原理：
元数据存放在内存中可随机访问和响应客户端请求，防止断电数据丢失产生备份数据FsImage于磁盘中
存中的元数据更新时，如果同时更新FsImage，就会导致效率过低；
因此，引入Edits文件（只进行追加操作，效率很高），
每当元数据有更新或者添加元数据时，修改内存中的元数据并追加到Edits中
需要定期进行FsImage和Edits的合并，如果这个操作由NameNode节点完成，又会效率过低
因此，引入一个新的节点SecondaryNamenode，专门用于FsImage和Edits的合并

client                            nn                                                   2nn
                   1.磁盘加载镜像和日志到内存       执行CheckPoint(1.60时间到2.Edits数据100万)
2.元数据的增删改请求    3.记录操作日志，更新滚动日志------> 拷贝到2nn    fsimage  edits          
                  4.内存中的增删改操作                    加载到内存并合并生成新的Fsimage
                  <-拷贝到nn，并且重命名为fsimage--   

----------


dn工作机制：
        dn (数据长度，校验和，时间戳)                              nn(元数据/副本策略/映射信息/client请求)
        dn启动后向nn注册  
        周期上报块信息
                         <--------------------双向连接心跳--------------------->  
                <-----超过10分钟+30s 该节点不可用----------   

JAVA-HashMap基础API

import java.util.*;
import java.util.ArrayList;

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> map = new HashMap<>();

        String group1Leader = "yxc";
        ArrayList<String> list1 = new ArrayList<>();
        list1.add(group1Leader);
        list1.add("java");
        list1.add("python");
        list1.add("cpp");
        list1.add("js");
        map.put(group1Leader,list1);

        String group2Leader = "wyf";
        ArrayList<String> list2 = new ArrayList<>();
        list2.add(group2Leader);
        list2.add("hadoop");
        list2.add("hive");
        list2.add("spark");
        list2.add("flink");
        map.put(group2Leader,list2);

        Set<Map.Entry<String, ArrayList<String>>> entries = map.entrySet();
        for (Map.Entry<String, ArrayList<String>> entry : entries) {
            String key = entry.getKey();
            ArrayList<String> value = entry.getValue();
            System.out.println("组长：" + key);
            System.out.println("组员有：");
            for (String name : value) {
                System.out.println("\t" + name);
            }
        }

        System.out.println("----------------");

        Collection<ArrayList<String>> values = map.values();
        ArrayList<Object> all = new ArrayList<>();
        for (ArrayList<String> group : values) {
            all.addAll(group);
        }
        System.out.println(all.contains("flink"));

        System.out.println("----------------");
        /* Hashtable: 线程安全，不允许 key，value 为 null
           HashMap  : 线程不安全  允许 key, value 为 null
           LinkedHashMap: 遍历时体现添加顺序
           TreeMap:    红黑树
                       可以按照key大小排序，key类型必须实现Comparable接口
                       或者在创建Treemap的时候指定为Comparator的实现类

          StringBuilder     StringBuffer
           Vector            ArrayList
           Hashtable         HashMap


           读JDBC中的 File 配置文件(jdbc.properties)
           使用类加载器和jdbc建立通道        load加载数据
           InputStream in = classLoader.getResourceAsStream(jdbc.properties)
        */
    }
}

JAVA模拟单链表

隔一段时间写一遍加强熟练度

import java.util.Iterator;

public class OneLink<E> implements Iterable<E>{
    private Node<E> first;
    private int size;

public void add(E e) { //尾部插入
    Node<E> newNode = new Node<>(e,null);

    if (first == null) {
        first = newNode;
    }else {
        Node node = first;
        while (node.next != null) { // 最后一个节点的特点.next = null
            node = node.next;
        }
        // 循环结束时 node.next == null
        node.next = newNode;
    }
    size ++;
}

public void remove(Object obj) {
    if (first == null) {
        return;
    }
    // 查找被删除目标结点
    Node node = first;
    Node before = null;
    if (obj == null) { // obj是否为空
        while (node != null) {
            if (node.data == null) { //这个点的值
                break;
            }
            before = node;
            node = node.next;
        }
    }else {
        while (node != null) {
            if (obj.equals(node.data)) { //这个点的值
                break;
            }
            before = node;
            node = node.next;
        }
    }
    // 如果全部找完 都没有找到  node == null
    if (node == null){ // 不存在被删除的目标 return
        return;
    }
    //  找到被删除的结点 分两种情况  是第一个结点  不是第一个结点
    if (before == null) {
        first = node.next;
    }else {
        before.next = node.next;
    }

    node.next = null;
    node.data = null;
    size --;
}

    @Override
    public Iterator<E> iterator() { // 返回一个iterator对象
        return new Itr();
    }
    private class Itr implements Iterator<E> { // 实现Iterator接口的class
    //  生成游标
        Node node = first;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public E next() {
            E data = (E) node.data;
            node = node.next;
            return data;
        }

    }

    private static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }
}

测试 TestOneLink

import java.util.Iterator;

public class TestOneLink {
    public static void main(String[] args) {
        OneLink<String> list = new OneLink<>();
        list.add("hello");
        list.add("python1");
        list.add("java");
        list.add("python2");
        list.add("world");

        for (String s : list) {
            System.out.println(s);
        }

        list.remove("python1");
        list.remove("python2");

        System.out.println("-------------");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

JAVA模拟双列表LinkedList

隔一段时间写一遍加强熟练度

import java.util.Iterator;

public class LinkedList<E> implements Iterable<E>{

    private Node<E> first; // 记录第一个结点的位置   头结点(head)   初始化为null
    private Node<E> last;  // 记录最后一个结点的位置  尾节点(tail)
    private int size;


    public void add(E e) {
        // 创建新节点，默认节点添加到当前链表的最后
        Node<E> newNode = new Node<E>(last, e, null);

        if (first == null) { // 如果链表为空链表 first指向newNode 新结点是链表的第一个结点
            first = newNode;
        }else {
            last.next = newNode;  //链表原来的最后一个结点的next指向新节点
        }

        // 新节点成了链表的最后一个结点
        last = newNode;
        size ++;
    }

    public void remove(Object obj) {
        if (first == null) { // 如果链表是空则不用处理 return
            return;
        }

        Node node = findNode(obj);
        if (node == null) {
            return; // 说明被删元素不存在
        }

        // 若被删元素存在 需要分情况讨论被删的点是否是自己本身
        Node pre = node.previous; // pre 表示被删除结点的的前一个结点
        Node next = node.next;    // next 表示被删除结点的下一个结点

        if (pre == null) { // 被删除的节点是第一个结点
            first = next;
           // next.previous = null;
        }else {
            pre.next = next;
        }
        if(next == null) { // 被删除的节点是最后一个节点
            last = pre;
        }else {
            next.previous = pre;
        }


        // 删除结点处理
        node.next = null;
        node.previous = null;
        node.data = null;

        // 元素个数减少
        size --;

    }

    private Node findNode(Object obj) {
        Node node = first;
        if (obj == null) { // 传入的数据可能为null  防止空指针
            while (node != null) {
                if (node.data == null) {
                    return node;
                }
                node = node.next; // 向右移动
            }
        }else {
            while (node != null) {
                if (obj.equals(node.data)) {
                    return node;
                }
                node = node.next;
            }
        }

        return null; // 没有进入上述的循环就是没找到 返回null
    }

    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    // 这里是非静态内部类，因为他需要访问链表的非静态first等
    private class Itr implements Iterator<E> {
        Node<E> node = first; // 一开始node默认指向第一个结点

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public E next() {
            E data = node.data; // 先将数据取出
            node = node.next;  //  移动到下一个结点
            return data; // 返回的是结点的数据
        }
    }


    // 静态内部类  结点类型
    private static class Node<E> {
        Node previous;
        E data;
        Node next;

        Node(Node previous,E data, Node next) {
        this.data = data;
        this.previous = previous;
        this.next = next;
    }
}
}

测试 LinkedList

import org.junit.jupiter.api.Test;

import java.util.Iterator;

public class TestLinkedList {
    @Test
    public void test() {
        LinkedList<String> list = new LinkedList<>();
        list.add("python1");
        list.add("hello");
        list.add("java");
        list.add("python2");
        list.add("world");
        list.add("python3");
        System.out.println("size = " + list.size());

        for (String s : list) {  // iter 快捷生成
            System.out.println(s);
        }

        System.out.println("---------------");
        list.remove("python1");
        list.remove("python2");
        list.remove("python3");

        System.out.println("---------------");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

JAVA数组模拟ArrayList

隔一段时间写一遍加强熟练度

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Predicate;

public class ArrayList<E> implements Iterable<E>{// 实现Iterable 可以用foreach
    private E[] elementData;
    private int size;

    private static final int DEFAULT_CAPACITY = 10;

    ArrayList() {}

    ArrayList(int initCapacity) {
        if (initCapacity <= 0)
            initCapacity = DEFAULT_CAPACITY;
        elementData = (E[])new Object [initCapacity];
    }

    // 扩容
    public void ensureCapacity(int size) {
        int oldCapacity = elementData.length;
        if (size >= oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity>>1);//扩容1.5倍
            elementData = Arrays.copyOf(elementData,newCapacity);
        }
    }

    // 越界
    public void checkIndex(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("add:index越界");//运行时异常
    }

    // 尾插
    public boolean add(E e) {
        add(size, e);
        return true;
    }

    // 插入任意位置
    public void add(int index,E e) {
        checkIndex(index);
        ensureCapacity(size);

        for (int i = size - 1; i >= index; i--) {
            elementData[i + 1] = elementData[i];
        }
        elementData[index] = e;
        size ++;
    }

    // 获取index位置的元素
    public E get(int index) {
        checkIndex(index);
        return elementData[index];
    }

    // set
    public E set(int index,E e) {
        checkIndex(index);
        elementData[index] = e;
        return e;
    }

    // 删除index位置的元素
    public E remove(int index) {
        checkIndex(index);

        E e = (E)elementData[index];
        for (int i = index + 1; i < size; i++) {
         elementData[i - 1] = elementData[i];
        }

        size --;
        return e;
    }

    // 删除某一元素
    public boolean remove(E e) {
        remove(indexOf(e));
        return true;
    }

    // removeIf(Predicate<E> p) 根据判断条件删除
    public void removeIf(Predicate<E> p) {
        for (int i = 0; i < size; i++) {
            if (p.test((E)elementData[i])){
                // 删除elementData[i]
                remove(elementData[i]); // 注意：remove后 被删除的元素会向前移动 在外层的遍历下会跳着遍历
                i --;                   // i -- 可以遍历到所有元素
            }
        }
    }

    // 清空表
    public void clear() {
        for (int i = 0; i < size; i++) {
            elementData[i] = null;
        }
        size = 0;
    }

    // 判断某一元素是否在表中
    public boolean contains(E e) {
        return !(-1 == indexOf(e));
    }

    // 获取第一次遇见元素e的位置
    public int indexOf(E e) {
        for (int i = 0; i < size; i++) {
            if (e == elementData[i]) {
                return i;
            }
        }
        return -1;
    }

    // 获取最后一次出现元素e的位置
    public int lastIndexOf(E e) {
        for (int i = size - 1; i >= 0 ; i--) {
            if (e == elementData[i]) {
                return i;
            }
        }
        return -1;
    }

    // 获取一个子序列  左闭右开
    ArrayList<E> subList(int fromIndex,int toIndex) {
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("输入参数非法");
        checkIndex(fromIndex);
        checkIndex(toIndex);

        ArrayList<E> list = new ArrayList<>(toIndex - fromIndex);
        for (int i = fromIndex; i < toIndex; i++) {
            list.add((E)elementData[i]);
        }
        return list;
    }

    @Override
    public String toString() {
        String s = "[";
        for (int i = 0; i < size; i++) {
            s += elementData[i];
            if (i != (size-1))
                s += ",";
        }
        s += "]";
        return s;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }
    // Itr 只能声明为非静态的内部类，因为Itr中需要访问外部类的非静态成员elementData
    private class Itr implements Iterator<E> {
        int cursor;

        @Override
        public boolean hasNext() {
            return cursor < size;
        }

        @Override
        public E next() {
            return (E) elementData[cursor ++];
        }
    }
}

测试 @Test

import org.junit.jupiter.api.Test;

import java.util.Iterator;
import java.util.function.Predicate;

public class TestArraylist {

    @Test
    public void test() {
        ArrayList<String> list = new ArrayList<>(10);
        list.add("hello");
        list.add("java");
        list.add(null);
        System.out.println(list);

        list.add(0,"yxco");
        list.add(1,"wyfo");
        System.out.println(list);

        System.out.println("-----------------------");
        for (String str : list) {
            System.out.println(str);
        }

        System.out.println("-----------------------");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("-----------------------");
        // 根据条件删除 removeIf
        list.removeIf(new Predicate<String>() {
            @Override
            public boolean test(String s) {
                return s != null && s.contains("o");
            }
        });
        for (String str : list) {
            System.out.println(str);
        }

    }
}