首页 文章 精选 留言 我的

精选列表

搜索[数据结构]，共7263篇文章
优秀的个人博客,低调大师

Java数据结构——单向链表实现

/** * 单向链表实现类 * @Description * 类描述： * @author GaoAnQiu * @Date * @modify * 修改记录： * */ public class Link { private int size = 0; private Node first; private Node last; public Node getFirst() { return first; } public void setFirst(Node first) { this.first = first; } public Node getLast() { return last; } public void setLast(Node last) { this.last = last; } public Link() { } /** * 返回链表长度 * @Description * 方法描述: * @return 返回类型： int * @return */ public int getLength() { return size; } public void printLink(Link link) { Node temp = first; while (temp != null) { System.out.print(temp.getData() + "-->"); temp = temp.getNext(); } System.out.println(); } /** * 返回指定位置的节点 * @Description * 方法描述: * @return 返回类型： Node * @param index * @return */ public Node get(int index) { Node temp = first; for (int i = 0; i < index; i++) { temp = temp.getNext(); } return temp; } /** * 插入第一个元素，头和尾都指向同一个元素 * @Description * 方法描述: * @return 返回类型： void */ private void onetNode(int element) { first = new Node(); first.setData(element); last = first; } public void addHead(int element) { if (size == 0) { onetNode(element); } else { Node node = new Node(); node.setData(element); node.setNext(first); first = node; } size++; } /** * 插入尾结点 * @Description * 方法描述: * @return 返回类型： void * @param element */ public void addTail(int element) { if (size == 0) { onetNode(element); } else { Node node = new Node(); node.setData(element); last.setNext(node); last = node; //将插入的结点设置为尾结点 size++; } } /** * 插入中间元素 * 头尾两处需要特殊处理 * @Description * 方法描述: * @return 返回类型： void * @param index * @param element */ public void add(int index, int element) { if (index > size) { throw new IndexOutOfBoundsException("待插入的位置超过链表的最大长度。"); } else { if (index == 0) { //下标为0时，插入头元素 addHead(element); } else if (size == index) { //下标与链表长度一致时，插入尾元素 addTail(element); } else { Node preNode = get(index - 1); // Node nextNode = get(index); Node newNode = new Node(); newNode.setData(element); preNode.setNext(newNode); newNode.setNext(nextNode); size++; } } } /** * 删除头节点 * @Description * 方法描述: * @return 返回类型： void */ public void delHead() { if (size == 0) { throw new IndexOutOfBoundsException("空链表，无元素可删除"); } else { if (size == 1) { //只有一个节点时，清空链表 clear(); } else { Node nextNode = first.getNext(); first = nextNode; } size--; } } /** * 清空链表 * @Description * 方法描述: * @return 返回类型： void */ public void clear() { first = last = null; size = 0; } public void delTail() { if (size == 0) { throw new IndexOutOfBoundsException("空链表，无可删除的元素。"); } else if (size == 1) { clear(); } else { //取出尾节点的前一个节点，next赋值为null Node preTail = get(size - 2); preTail.setNext(null); last = preTail; size--; } } /** * 删除节点 * @Description * 方法描述: * @return 返回类型： void * @param index */ public void del(int index) { if (index >= size) { throw new IndexOutOfBoundsException("删除位置越界"); } else { if (index == 0) { delHead(); } else if (index == size - 1) { delTail(); } else { Node preNode = get(index - 1); Node nextNode = get(index + 1); preNode.setNext(nextNode); size--; } } } } public class Node { private int data;//数据 private Node next;//指针 public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }
2019-04-16
优秀的个人博客,低调大师

GO语言的数据结构测试

用于docker了，go也慢慢看一些。。 推荐书籍《go语言实践》就是<Go in Action>的中文版，有文字版PDF的。 package main import ( "fmt" ) //main is the entry of the program func main() { var array1 [5]string array2 := [5]int{10, 20, 30, 40, 50} array3 := [...]int{10, 20, 30, 40, 50} array4 := [5]int{1: 10, 2: 20} array2[2] = 35 array5 := [5]*int{0: new(int), 1: new(int)} *array5[0] = 10 *array5[1] = 20 array6 := [5]string{"Red", "Blue", "Green", "Yellow", "Pink"} array1 = array6 array7 := [4][2]int{{10, 11}, {20, 21}, {30, 31}, {40, 41}} fmt.Println(array1, array2, array3, array4, array5, array6, array7) }

2017-06-28
优秀的个人博客,低调大师

HBase数据结构（读书笔记 ）

背景： 最近在做一些跟大数据相关的东西，涉及到数据的存储和分析，考虑各个方面，选择使用HBase进行存储，使用原生Java API进行数据分析，之后会陆续写一系列来说明最近做的东西，给像我这样未曾涉及过这个领域的人一点儿idea。 引言： HBase以表的方式组织数据源，这一点跟关系型数据库时一样的，在我们的application里面，通过API/Thrift、或者各种SQL引擎，将数据存入库里面或者进行查询；Hbase的表由行（Row）和列（Column）共同构成，与关系型数据库不同的是，HBase有一个列族（Column Family）的概念，它将一列或者多列组织在一起，HBase的列必须属于某一个列族。 行和列的交叉点称为单元格（Cell）,单元格是版本化的。单元格的内容也就是列的值是不可分割的字节数组，以二进制的形式存储。HBase没有数据类型，任何列值都被转换成字符数组进行存储。HBase表中的行是通过行键（Rowkey）来进行区分的，行健也是用来唯一确定一行的标识，不同的行健嗲表不同的行，行健也是一段字节数组，不论是字符串还是数字，最终都会被转换成自己数组进行存储。HBase表中的行是按照RowKey排序的，排序方式采用字典顺序，所有表中的行都必须有RowKey。 逻辑模型 HBase是一个类似GoogleBigTable的开源分布式数据库，它最基本的单位是列，一列或者多列组成行，行有行健，每一行的行健都是唯一的，相同的行健的插入操作被认为是对同一行的操作，也就是说如果做了两次写入操作，而行健是同一个，那么后面的操作可以认为是对改行的某些列的更新操作。 列名是右列族前缀和修饰符连接而成，分隔符是应为冒号。 物理模型 在逻辑模型中，表可以被看成一个稀疏的行的集合。但是在物理上，表是按照列分开存储的。HBase的列是按照列族分组的，HFile是面向列的，存放行的不同的列的物理文件，一个列族的数据存放在多个HFile中，最重要的是一个列族的数据会被同一个Region管理，物理上存放在一起。Region是管理HFile的一种机制。
2016-12-09
优秀的个人博客,低调大师

HBase与Zookeeper数据结构查询

一、前言 最近一年了吧，总是忙于特定项目的业务分析和顶层设计，很少花时间和精力放到具体的技术细节，感觉除了架构理念和分析能力的提升，在具体技术层次却并没有多大的进步。因为一些原因，总被人问及一些技术细节，很多细节都模糊了，花点时间，温习一下吧。技术部分将作为下一个阶段的工作重点。 二、操作说明 查看Zookeeper内部HBase相关数据，有两个主要的渠道：一、通过Hbase shell命令zk_dump查看；二、通过zk_cli.sh查看； 三、zk_dump 1 HBase is rooted at /hbase 2 Active master address: localhost,60000,1411261739960 3 Backup master addresses: 4 Region server holding hbase:meta: localhost,60020,1411261739301 5 Region servers: 6 localhost,60020,1411261739301 7 /hbase/replication: 8 /hbase/replication/peers: 9 /hbase/replication/rs: 10 /hbase/replication/rs/localhost,60020,1411261739301: 11 Quorum Server Statistics: 12 192.168.230.128:2181 13 Zookeeper version: 3.4.6-1569965, built on 02/20/2014 09:09 GMT 14 Clients: 15 /192.168.230.128:54264[1](queued=0,recved=204,sent=212) 16 /192.168.230.128:54269[1](queued=0,recved=113,sent=113) 17 /192.168.230.128:54265[1](queued=0,recved=460,sent=507) 18 /192.168.230.128:54271[1](queued=0,recved=131,sent=131) 19 /192.168.230.128:54274[1](queued=0,recved=86,sent=86) 20 /192.168.230.128:54656[1](queued=0,recved=12,sent=12) 21 /192.168.230.128:54654[1](queued=0,recved=3,sent=3) 22 /192.168.230.128:54270[1](queued=0,recved=94,sent=94) 23 /192.168.230.128:54481[1](queued=0,recved=242,sent=242) 24 /192.168.230.128:54657[0](queued=0,recved=1,sent=0) 25 26 Latency min/avg/max: 0/1/155 27 Received: 1352 28 Sent: 1406 29 Connections: 10 30 Outstanding: 0 31 Zxid: 0x65 32 Mode: standalone 33 Node count: 38 四、zk_cli.sh 1 [zk: 192.168.230.128:2181(CONNECTED) 30] ls 2 ZooKeeper -server host:port cmd args 3 connect host:port 4 get path [watch] 5 ls path [watch] 6 set path data [version] 7 rmr path 8 delquota [-n|-b] path 9 quit 10 printwatches on|off 11 create [-s] [-e] path data acl 12 stat path [watch] 13 close 14 ls2 path [watch] 15 history 16 listquota path 17 setAcl path acl 18 getAcl path 19 sync path 20 redo cmdno 21 addauth scheme auth 22 delete path [version] 23 setquota -n|-b val path 24 [zk: 192.168.230.128:2181(CONNECTED) 31] ls / 25 [hbase, zookeeper] 26 [zk: 192.168.230.128:2181(CONNECTED) 32] ls /hbase 27 [meta-region-server, backup-masters, table, draining, region-in-transition, table-lock, running, master, namespace, hbaseid, online-snapshot, replication, splitWAL, recovering-regions, rs] 28 [zk: 192.168.230.128:2181(CONNECTED) 33] 五、说明 关于输出结果的解读，就不去细说了，感兴趣的兄弟，自己去问度娘吧。 莫愁前路无知己，夜漫自有早行人。大数据架构师技术交流： 347018601 作者：张子良 出处：http://www.cnblogs.com/hadoopdev 本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
2014-09-20
优秀的个人博客,低调大师

Hbase系统架构及数据结构

HBase中的表一般有这样的特点： 1 大：一个表可以有上亿行，上百万列 2 面向列:面向列(族)的存储和权限控制，列(族)独立检索。 3 稀疏:对于为空(null)的列，并不占用存储空间，因此，表可以设计的非常稀疏。 下面一幅图是Hbase在Hadoop Ecosystem中的位置。 二、逻辑视图 HBase以表的形式存储数据。表有行和列组成。列划分为若干个列族(row family) Row Key 与nosql数据库们一样,row key是用来检索记录的主键。访问hbase table中的行，只有三种方式： 1 通过单个row key访问 2 通过row key的range 3 全表扫描 Row key行键 (Row key)可以是任意字符串(最大长度是 64KB，实际应用中长度一般为 10-100bytes)，在hbase内部，row key保存为字节数组。 存储时，数据按照Row key的字典序(byte order)排序存储。设计key时，要充分排序存储这个特性，将经常一起读取的行存储放到一起。(位置相关性) 注意： 字典序对int排序的结果是1,10,100,11,12,13,14,15,16,17,18,19,2,20,21,…,9,91,92,93,94,95,96,97,98,99。要保持整形的自然序，行键必须用0作左填充。 行的一次读写是原子操作 (不论一次读写多少列)。这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。 列族 hbase表中的每个列，都归属与某个列族。列族是表的chema的一部分(而列不是)，必须在使用表之前定义。列名都以列族作为前缀。例如courses:history，courses:math都属于courses 这个列族。 访 问控制、磁盘和内存的使用统计都是在列族层面进行的。实际应用中，列族上的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数 据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。 时间戳 HBase 中通过row和columns确定的为一个存贮单元称为cell。每个 cell都保存着同一份数据的多个版本。版本通过时间戳来索引。时间戳的类型是 64位整型。时间戳可以由hbase(在数据写入时自动 )赋值，此时时间戳是精确到毫秒的当前系统时间。时间戳也可以由客户显式赋值。如果应用程序要避免数据版本冲突，就必须自己生成具有唯一性的时间戳。每个 cell中，不同版本的数据按照时间倒序排序，即最新的数据排在最前面。 为了避免数据存在过多版本造成的的管理 (包括存贮和索引)负担，hbase提供了两种数据版本回收方式。一是保存数据的最后n个版本，二是保存最近一段时间内的版本（比如最近七天）。用户可以针对每个列族进行设置。 Cell 由{row key, column(= + ), version} 唯一确定的单元。cell中的数据是没有类型的，全部是字节码形式存贮。 三、物理存储 1 已经提到过，Table中的所有行都按照row key的字典序排列。 2 Table 在行的方向上分割为多个Hregion。 3 region按大小分割的，每个表一开始只有一个region，随着数据不断插入表，region不断增大，当增大到一个阀值的时候，Hregion就会等分会两个新的Hregion。当table中的行不断增多，就会有越来越多的Hregion。 4 HRegion是Hbase中分布式存储和负载均衡的最小单元。最小单元就表示不同的Hregion可以分布在不同的HRegion server上。但一个Hregion是不会拆分到多个server上的。 5 HRegion虽然是分布式存储的最小单元，但并不是存储的最小单元。 事实上，HRegion由一个或者多个Store组成，每个store保存一个columns family。 每个Strore又由一个memStore和0至多个StoreFile组成。如图： StoreFile以HFile格式保存在HDFS上。 HFile的格式为： HFile分为六个部分： Data Block 段–保存表中的数据，这部分可以被压缩 Meta Block 段 (可选的)–保存用户自定义的kv对，可以被压缩。 File Info 段–Hfile的元信息，不被压缩，用户也可以在这一部分添加自己的元信息。 Data Block Index 段–Data Block的索引。每条索引的key是被索引的block的第一条记录的key。 Meta Block Index段 (可选的)–Meta Block的索引。 Trailer– 这一段是定长的。保存了每一段的偏移量，读取一个HFile时，会首先读取Trailer，Trailer保存了每个段的起始位置(段的Magic Number用来做安全check)，然后，DataBlock Index会被读取到内存中，这样，当检索某个key时，不需要扫描整个HFile，而只需从内存中找到key所在的block，通过一次磁盘io将整个 block读取到内存中，再找到需要的key。DataBlock Index采用LRU机制淘汰。 HFile的Data Block，Meta Block通常采用压缩方式存储，压缩之后可以大大减少网络IO和磁盘IO，随之而来的开销当然是需要花费cpu进行压缩和解压缩。 目标Hfile的压缩支持两种方式：Gzip，Lzo。 HLog(WAL log) WAL 意为Write ahead log(http://en.wikipedia.org/wiki/Write-ahead_logging)，类似mysql中的binlog,用来 做灾难恢复只用，Hlog记录数据的所有变更,一旦数据修改，就可以从log中进行恢复。 每 个Region Server维护一个Hlog,而不是每个Region一个。这样不同region(来自不同table)的日志会混在一起，这样做的目的是不断追加单个 文件相对于同时写多个文件而言，可以减少磁盘寻址次数，因此可以提高对table的写性能。带来的麻烦是，如果一台region server下线，为了恢复其上的region，需要将region server上的log进行拆分，然后分发到其它region server上进行恢复。 HLog 文件就是一个普通的Hadoop Sequence File，Sequence File 的Key是HLogKey对象，HLogKey中记录了写入数据的归属信息，除了table和region名字外，同时还包括 sequence number和timestamp，timestamp是”写入时间”，sequence number的起始值为0，或者是最近一次存入文件系统中sequence number。HLog Sequece File的Value是HBase的KeyValue对象，即对应HFile中的KeyValue，可参见上文描述。 四、系统架构 Client 1 包含访问hbase的接口，client维护着一些cache来加快对hbase的访问，比如regione的位置信息。 Zookeeper 1 保证任何时候，集群中只有一个master 2 存贮所有Region的寻址入口。 3 实时监控Region Server的状态，将Region server的上线和下线信息实时通知给Master 4 存储Hbase的schema,包括有哪些table，每个table有哪些column family Master 1 为Region server分配region 2 负责region server的负载均衡 3 发现失效的region server并重新分配其上的region 4 GFS上的垃圾文件回收 5 处理schema更新请求 Region Server 1 Region server维护Master分配给它的region，处理对这些region的IO请求 2 Region server负责切分在运行过程中变得过大的region 可以看到，client访问hbase上数据的过程并不需要master参与（寻址访问zookeeper和region server，数据读写访问regione server），master仅仅维护者table和region的元数据信息，负载很低。 五、关键算法/流程 region定位 系统如何找到某个row key (或者某个 row key range)所在的region bigtable 使用三层类似B+树的结构来保存region位置。 第一层是保存zookeeper里面的文件，它持有root region的位置。 第二层root region是.META.表的第一个region其中保存了.META.z表其它region的位置。通过root region，我们就可以访问.META.表的数据。 .META.是第三层，它是一个特殊的表，保存了hbase中所有数据表的region 位置信息。 说明： 1 root region永远不会被split，保证了最需要三次跳转，就能定位到任意region 。 2.META.表每行保存一个region的位置信息，row key 采用表名+表的最后一样编码而成。 3 为了加快访问，.META.表的全部region都保存在内存中。 假设，.META.表的一行在内存中大约占用1KB。并且每个region限制为128MB。 那么上面的三层结构可以保存的region数目为： (128MB/1KB) * (128MB/1KB) = = 2(34)个region 4 client会将查询过的位置信息保存缓存起来，缓存不会主动失效，因此如果client上的缓存全部失效，则需要进行6次网络来回，才能定位到正确的region(其中三次用来发现缓存失效，另外三次用来获取位置信息)。 读写过程 上文提到，hbase使用MemStore和StoreFile存储对表的更新。 数 据在更新时首先写入Log(WAL log)和内存(MemStore)中，MemStore中的数据是排序的，当MemStore累计到一定阈值时，就会创建一个新的MemStore，并 且将老的MemStore添加到flush队列，由单独的线程flush到磁盘上，成为一个StoreFile。于此同时，系统会在zookeeper中 记录一个redo point，表示这个时刻之前的变更已经持久化了。(minor compact) 当系统出现意外时，可能导致内存(MemStore)中的数据丢失，此时使用Log(WAL log)来恢复checkpoint之后的数据。 前面提到过StoreFile是只读的，一旦创建后就不可以再修改。因此Hbase的更新其实是不断追加的操作。当一个Store中的StoreFile达到一定的阈值后，就会进行一次合并(major compact),将对同一个key的修改合并到一起，形成一个大的StoreFile，当StoreFile的大小达到一定阈值后，又会对StoreFile进行split，等分为两个StoreFile。 由于对表的更新是不断追加的，处理读请求时，需要访问Store中全部的StoreFile和MemStore，将他们的按照row key进行合并，由于StoreFile和MemStore都是经过排序的，并且StoreFile带有内存中索引，合并的过程还是比较快。 写请求处理过程 1 client向region server提交写请求 2 region server找到目标region 3 region检查数据是否与schema一致 4 如果客户端没有指定版本，则获取当前系统时间作为数据版本 5 将更新写入WAL log 6 将更新写入Memstore 7 判断Memstore的是否需要flush为Store文件。 region分配 任何时刻，一个region只能分配给一个region server。master记录了当前有哪些可用的region server。以及当前哪些region分配给了哪些region server，哪些region还没有分配。当存在未分配的region，并且有一个region server上有可用空间时，master就给这个region server发送一个装载请求，把region分配给这个region server。region server得到请求后，就开始对此region提供服务。 region server上线 master 使用zookeeper来跟踪region server状态。当某个region server启动时，会首先在zookeeper上的server目录下建立代表自己的文件，并获得该文件的独占锁。由于master订阅了server 目录上的变更消息，当server目录下的文件出现新增或删除操作时，master可以得到来自zookeeper的实时通知。因此一旦region server上线，master能马上得到消息。 region server下线 当region server下线时，它和zookeeper的会话断开，zookeeper而自动释放代表这台server的文件上的独占锁。而master不断轮询 server目录下文件的锁状态。如果master发现某个region server丢失了它自己的独占锁，(或者master连续几次和region server通信都无法成功),master就是尝试去获取代表这个region server的读写锁，一旦获取成功，就可以确定： 1 region server和zookeeper之间的网络断开了。 2 region server挂了。 的其中一种情况发生了，无论哪种情况，region server都无法继续为它的region提供服务了，此时master会删除server目录下代表这台region server的文件，并将这台region server的region分配给其它还活着的同志。 如果网络短暂出现问题导致region server丢失了它的锁，那么region server重新连接到zookeeper之后，只要代表它的文件还在，它就会不断尝试获取这个文件上的锁，一旦获取到了，就可以继续提供服务。 master上线 master启动进行以下步骤: 1 从zookeeper上获取唯一一个代码master的锁，用来阻止其它master成为master。 2 扫描zookeeper上的server目录，获得当前可用的region server列表。 3 和2中的每个region server通信，获得当前已分配的region和region server的对应关系。 4 扫描.META.region的集合，计算得到当前还未分配的region，将他们放入待分配region列表。 master下线 由 于master只维护表和region的元数据，而不参与表数据IO的过程，master下线仅导致所有元数据的修改被冻结(无法创建删除表，无法修改表 的schema，无法进行region的负载均衡，无法处理region上下线，无法进行region的合并，唯一例外的是region的split可以 正常进行，因为只有region server参与)，表的数据读写还可以正常进行。因此master下线短时间内对整个hbase集群没有影响。从上线过程可以看到，master保存的 信息全是可以冗余信息（都可以从系统其它地方收集到或者计算出来），因此，一般hbase集群中总是有一个master在提供服务，还有一个以上 的’master’在等待时机抢占它的位置。 六、访问接口 七、结语： 全文对Hbase做了简单的介绍，有错误之处，敬请指正。未来将结合Hbase在淘宝数据平台的应用场景，在更多细节上进行深入。 参考文档 Bigtable: A Distributed Storage System for Structured Data HFile: A Block-Indexed File Format to Store Sorted Key-Value Pairs for a thorough introduction Hbase Architecture 101
2013-06-21
优秀的个人博客,低调大师

源码详解数据结构Linked List

摘要：java.util.LinkedList 是 Java 集合框架中的成员之一，底层是基于双向链表实现，集合容量可动态变化的。 本文分享自华为云社区《LinkedList 源码分析》，作者： 陈皮的JavaLib。 LinkedList 简介 java.util.Linked List 是 Java 集合框架中的成员之一，底层是基于双向链表实现，集合容量可动态变化的。它继承自 Abstract Sequential List 抽象类，实现了 List 接口。同时还实现了 Cloneable 和 Serializable 三个标记接口，说明 Array List 是可克隆复制的，可序列化的。 Array List 数组列表底层是基于动态数组实现的，所以优点是能支持快速随机访问，但是增删操作可能会比较慢（因为可能需要进行数组扩容，数据拷贝）。而且数组需要先申请一定的内存空间，可能会造成浪费。而链表列表 LinkedList 的优点是增删操作速度比较快，而且列表存储多少元素就动态申请多少节点来存储，比较节省内存空间。 为何要使用双向链表呢，主要在于遍历效率比单向链表高。例如当我们需要查找指定下标的节点，在指定下标进行增删改操作时，先判断这个位置是靠近头部还是尾部，从而决定从头部还是从尾部开始查找，提高效率。 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { } 2 LinkedList 源码分析 2.1 内部变量 LinkedList 的元素是存储在节点对象中的，节点类是 LinkedList 类的一个内部私有静态类，源码如下所示： private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } LinkedList 中定义了3个变量，一个代表当前列表的元素个数，另外两个变量指向链表的头部和尾部。以及它的父类 AbstractList 中的 modCount 变量，每次对链表的增删改操作都会使它加1。 transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0; 2.2 构造函数 ArrayList 有2个构造函数，一个无参构造函数，另一个使用指定 Collection 集合来构造集合的构造函数。 无参构造函数，什么都没有操作。 public LinkedList() {} 使用指定 Collection 集合来构造链表，如果 Collection 不能为 null ，否则会抛出 npe 。 public LinkedList(Collection<? extends E> c) { this(); addAll(c); } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } 2.3 常用方法 public E getFirst() 获取链表的第一个元素，如果不存在第一个节点，抛出异常。 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() 获取链表的最后一个元素，如果链表为空，则抛出异常。 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } public E removeFirst() 删除第一个元素，如果链表为空，则抛出异常。 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() 删除最后一个元素，如果链表为空，则抛出异常。 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } public void clear() 情况链表，遍历每一个节点，将每一个节点的内部引用都置为 null ，便于进行垃圾回收。 public void clear() { for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } public boolean add(E e) 在链表尾部添加一个元素。 public boolean add(E e) { linkLast(e); return true; } public Iterator iterator() 获取 list 的迭代器，用于遍历集合中的元素。 public Iterator<E> iterator() { return new Itr(); } public int size()：返回集合元素个数。 public boolean contains(Object o)：是否包含某个元素。 public boolean remove(Object o)：删除某个元素。 public E get(int index)：获取指定下标的元素。 public E set(int index, E element)：在指定下标修改元素值。 public void add(int index, E element)：在指定下标添加元素。 3 常见面试题分析 3.1 LinkedList 是线程安全的吗？ 我们通过分析源码可知，对它的任何操作都是没有加锁的，所以在多线程场景下，它是线程不安全的。它适合在非多线程使用场景下，并且增删操作比较多的情况。 public static void main(String[] args) throws InterruptedException { LinkedList<String> list = new LinkedList<>(); Thread thread1 = new Thread(() -> { for (int i = 0; i < 1000; i++) { list.add(Thread.currentThread().getName() + i); } }, "Thread01"); thread1.start(); Thread thread2 = new Thread(() -> { for (int i = 0; i < 1000; i++) { list.add(Thread.currentThread().getName() + i); } }, "Thread02"); thread2.start(); thread1.join(); thread2.join(); System.out.println(list.size()); // 输出不一定是2000，例如1850 } 如果增删操作比较多的话，可以使用 LinkedList ，LinkedList 增删操作速度比较快。 如果需要线程安全的话，可以使用 JDK 集合中的工具类 Collections 提供一个方法 synchronizedList 可以将线程不安全的 List 集合变成线程安全的集合对象，如下所示。 public static void main(String[] args) throws InterruptedException { LinkedList<String> list = new LinkedList<>(); // 封装成线程安全的集合 List<String> synchronizedList = Collections.synchronizedList(list); Thread thread1 = new Thread(() -> { for (int i = 0; i < 1000; i++) { synchronizedList.add(Thread.currentThread().getName() + i); } }, "Thread01"); thread1.start(); Thread thread2 = new Thread(() -> { for (int i = 0; i < 1000; i++) { synchronizedList.add(Thread.currentThread().getName() + i); } }, "Thread02"); thread2.start(); thread1.join(); thread2.join(); System.out.println(synchronizedList.size()); } 3.2 LinkedList 优缺点 优点：增删操作速度快，不仅有头部和尾部双指针，可以根据要操作的下标靠近哪边，从而决定从哪一边开始遍历找到指定的下标。找到位置后，删除和插入操作的时间复杂度为 O(1) 。 缺点：不支持快速随机访问，相对 ArrayList 比较慢，但也不是决定的，取决于列表的长度，以及访问的下标位置。 3.3 使用迭代器 Iterator 过程中，可以增删元素吗？ 通过源码分析，在获取集合的迭代器方法中，返回的是 AbstractList 抽象类中定义的 ListItr 迭代器对象，在他的父类 Itr 中持有变量 expectedModCount ，在初始化迭代器对象时这个变量的值被赋予此时链表中的操作次数 modCount 。在迭代获取元素时，会检查这两变量是否相等，不相等则抛出并发修改异常。所以不支持在使用迭代器的过程中，对原链表进行增删改操作。但是可以调用迭代器的增删操作。 private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; } public boolean hasPrevious() { return cursor != 0; } public E previous() { checkForComodification(); try { int i = cursor - 1; E previous = get(i); lastRet = cursor = i; return previous; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public int nextIndex() { return cursor; } public int previousIndex() { return cursor-1; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.set(lastRet, e); expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; AbstractList.this.add(i, e); lastRet = -1; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } private class Itr implements Iterator<E> { /** * Index of element to be returned by subsequent call to next. */ int cursor = 0; /** * Index of element returned by most recent call to next or * previous. Reset to -1 if this element is deleted by a call * to remove. */ int lastRet = -1; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */ int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 3.4 LinkedList 可以存储 null 值吗？元素可以重复吗？ LinkedList 底层是由双向链表实现的，并且在添加元素的时候，没有对元素进行值校验，所以可以存储 null 值，并且存储的元素是可以重复的。 public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 3.5 如何边遍历 ArrayList 元素，边删除指定元素？ 不支持在遍历的同时对原链表进行操作，会抛出 ConcurrentModificationException 并发修改异常，前面我们提到使用迭代器 Iterator 遍历集合时，不能对集合进行增删操作（会导致 modCount 值变化）。应该使用 Iterator 类的 remove 方法。 package com.chenpi; import java.util.Iterator; import java.util.LinkedList; /** * @author 陈皮 * @version 1.0 * @description * @date 2022/3/1 */ public class ChenPi { public static void main(String[] args) { LinkedList<String> list = new LinkedList<>(); list.add("Java"); list.add("C++"); list.add("Python"); list.add("Lua"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String next = iterator.next(); if ("C++".equals(next)) { iterator.remove(); continue; } System.out.println(next); } } } // 输出结果如下 Java Python Lua 点击关注，第一时间了解华为云新鲜技术~
2022-03-17
优秀的个人博客,低调大师

数据结构一：数据+链表 （Datawhale 系列）

Task1.1 数组 1.1.1实现一个支持动态扩容的数组 public class EnsureCapacityArray { private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; //传入固定值的情况 public EnsureCapacityArray(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); } } //没有传入数组大小的情况 public EnsureCapacityArray() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容 * @param minCapacity */ public void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //数组容量最大的情况 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } } 1.1.2 实现一个大小固定的有序数组，支持动态增删改操作 这里理解，大小固定的有序数组，那也就是说数组大小和内部的元素个数完全相同。那么增的时候，需要扩容，删的时候，需要减容。然后数组有序，也就是说，改的时候需要重新排序。 public class FixedArray{ private static final int DEFAULT_SIZE = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULT_ELEMENTDATA = new Object[DEFAULT_SIZE]; transient Object[] elementData; private int size; public FixedArray(){ this.elementData=DEFAULT_ELEMENTDATA; } public FixedArray(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); } } //保证增和删时数组长度和元素长度一致 private void ensureCapacityInternal(int minCapacity ){ if (minCapacity - elementData.length > 0) grow(minCapacity); } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; public void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //数组容量最大的情况 private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } //去掉删除之后，重新排序的，空的数组 public void trimToSize() { if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } } //判断数组长度 public int size(){ return size; } //判断数组是否为空 public boolean isEmpty() { return size == 0; } //排序 @SuppressWarnings("unchecked") private <E> void sort() { Arrays.sort((E[]) elementData, 0, size); } //添加 public <E> boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; sort(); return true; } //删除 public <E> boolean remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(); System.arraycopy(elementData, index+1, elementData, index, size-1); size--; trimToSize(); return true; } //改 public <E> boolean set(int index,Object e) { elementData[index] = e; sort(); return true; } //查 public Object get(int index) { return elementData[index]; } } 1.1.3 合并两个有序的数组 public static int[] mergeArrays(int[]a ,int[]b){ int alen=a.length; int blen=b.length; int aindex=0; int bindex=0; int [] re=new int[alen+blen]; for(int i=0;i<alen+blen;i++){ if(aindex<alen && bindex<blen){ re[i]=a[aindex] > b[bindex] ? b[bindex++] :a[aindex++]; continue; } if(aindex==alen && bindex<blen ) re[i]=b[bindex++]; if(bindex==blen &&aindex<alen) re[i]=a[aindex++]; } return re; } 1.1.4学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！ 哈希表 //两数之和 public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } //Happy Number(202) class Solution { public boolean isHappy(int n) { if(n==1) return true; while(n!=1 && n!=4){ int a=0; int ans=0; while(n>0){ a=n%10; ans+=a*a; n /=10; } n=ans; } if(n==1) return true; else return false; } } 1.1.5 练习 //Three Sum public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num); List<List<Integer>> res = new LinkedList<>(); for (int i = 0; i < num.length-2; i++) { if (i == 0 || (i > 0 && num[i] != num[i-1])) { int lo = i+1, hi = num.length-1, sum = 0 - num[i]; while (lo < hi) { if (num[lo] + num[hi] == sum) { res.add(Arrays.asList(num[i], num[lo], num[hi])); while (lo < hi && num[lo] == num[lo+1]) lo++; while (lo < hi && num[hi] == num[hi-1]) hi--; lo++; hi--; } else if (num[lo] + num[hi] < sum) lo++; else hi--; } } } return res; } //Majority Element public int majorityElement(int[] nums) { int res=0; int cnt=0; for(int num:nums){ if(cnt==0){ res=num; ++cnt; } else if(num == res) ++cnt; else --cnt; } return res; } //Missing Positive public int firstMissingPositive(int[] nums) { if(nums == null&&nums.length==0) return 1; int i; for(i=0;i<nums.length;i++){ if(nums[i] != i+1){ while(0<nums[i]&& nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){ int temp = nums[i]; nums[i] = nums[nums[i]-1]; nums[temp-1] = temp; } } } for(i=0;i<nums.length;i++) { if(nums[i]!=i+1) { return i+1; } } return i+1; } TASK1.2 链表 1.2.1 实现单链表、循环链表、双向链表，支持增删操作 //单链表 class singleNode{ public int data; public singleNode next; public singleNode head =null; public singleNode(int data){ this.data=data; } public void addNode(singleNode node){ singleNode newNode = new singleNode(data); if(head == null){ head = newNode; return; } singleNode temp = head; while(temp.next != null){ temp = temp.next; } temp.next = newNode; } public boolean removeNode(int index){ if(index<1 || index>length()){ return false; } if(index == 1){//删除头结点 head = head.next; return true; } singleNode preNode = head; singleNode curNode = preNode.next; int i = 1; while(curNode != null){ if(i==index){//寻找到待删除结点 preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点 return true; } //当先结点和前结点同时向后移 preNode = preNode.next; curNode = curNode.next; i++; } return true; } public int length(){ int length = 0; singleNode curNode = head; while(curNode != null){ length++; curNode = curNode.next; } return length; } } //双向链表 //单向循环链表类 public class CycleLinkList implements List { Node head; //头指针 Node current;//当前结点对象 int size;//结点个数 //初始化一个空链表 public CycleLinkList() { //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。 this.head = current = new Node(null); this.size =0;//单向链表，初始长度为零。 this.head.next = this.head; } //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。 //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域 public void index(int index) throws Exception { if(index <-1 || index > size -1) { throw new Exception("参数错误！"); } //说明在头结点之后操作。 if(index==-1) //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。 return; current = head.next; int j=0;//循环变量 while(current != head&&j<index) { current = current.next; j++; } } @Override public void delete(int index) throws Exception { // TODO Auto-generated method stub //判断链表是否为空 if(isEmpty()) { throw new Exception("链表为空，无法删除！"); } if(index <0 ||index >size) { throw new Exception("参数错误！"); } index(index-1);//定位到要操作结点的前一个结点对象。 current.setNext(current.next.next); size--; } @Override public Object get(int index) throws Exception { // TODO Auto-generated method stub if(index <-1 || index >size-1) { throw new Exception("参数非法！"); } index(index); return current.getElement(); } @Override public void insert(int index, Object obj) throws Exception { // TODO Auto-generated method stub if(index <0 ||index >size) { throw new Exception("参数错误！"); } index(index-1);//定位到要操作结点的前一个结点对象。 current.setNext(new Node(obj,current.next)); size++; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size==0; } @Override public int size() { // TODO Auto-generated method stub return this.size; } } //双向循环链表 //单向链表类 public class DoubleCycleLinkList implements List { Node head; //头指针 Node current;//当前结点对象 int size;//结点个数 //初始化一个空链表 public DoubleCycleLinkList() { //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。 this.head = current = new Node(null); this.size = 0;//单向链表，初始长度为零。 this.head.next = head; this.head.prior = head; } //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。 public void index(int index) throws Exception { if (index < -1 || index > size - 1) { throw new Exception("参数错误！"); } //说明在头结点之后操作。 if (index == -1) return; current = head.next; int j = 0;//循环变量 while (current != head && j < index) { current = current.next; j++; } } @Override public void delete(int index) throws Exception { // TODO Auto-generated method stub //判断链表是否为空 if (isEmpty()) { throw new Exception("链表为空，无法删除！"); } if (index < 0 || index > size) { throw new Exception("参数错误！"); } index(index - 1);//定位到要操作结点的前一个结点对象。 current.setNext(current.next.next); current.next.setPrior(current); size--; } @Override public Object get(int index) throws Exception { // TODO Auto-generated method stub if (index < -1 || index > size - 1) { throw new Exception("参数非法！"); } index(index); return current.getElement(); } @Override public void insert(int index, Object obj) throws Exception { // TODO Auto-generated method stub if (index < 0 || index > size) { throw new Exception("参数错误！"); } index(index - 1);//定位到要操作结点的前一个结点对象。 current.setNext(new Node(obj, current.next)); current.next.setPrior(current); current.next.next.setPrior(current.next); size++; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size == 0; } @Override public int size() { // TODO Auto-generated method stub return this.size; } } 1.2.2 实现单链表反转 public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; } 1.2.3 实现两个有序的链表合并为一个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } } 1.2.4 实现求链表的中间结点 public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode low=head; while(fast != null && fast.next != null){ low = low.next; fast= fast.next.next; } return low; } 1.2.5 练习 //Linked List Cycle I（环形链表） public boolean hasCycle(ListNode head) { ListNode f=head; ListNode s=head; if(head == null || head.next == null) return false; while(f!=null && f.next!=null){ f=f.next.next; s=s.next; if(f == s) return true; } return false; } //Merge k Sorted Lists（合并 k 个排序链表） public ListNode mergeKLists(ListNode[] lists){ if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2){ return mergeTwoLists(lists[0],lists[1]); } int mid = lists.length/2; ListNode[] l1 = new ListNode[mid]; for(int i = 0; i < mid; i++){ l1[i] = lists[i]; } ListNode[] l2 = new ListNode[lists.length-mid]; for(int i = mid,j=0; i < lists.length; i++,j++){ l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1),mergeKLists(l2)); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = null; if (l1.val <= l2.val){ head = l1; head.next = mergeTwoLists(l1.next, l2); } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; }
2019-05-10

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

时间: 2026-04-11 大小: 211.28KB 下载: 56次
腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

时间: 2026-08-21 大小: 1MB 下载: 10次
Spring

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

时间: 2026-08-21 大小: 5MB 下载: 2次
Rocky Linux

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

时间: 2026-08-21 大小: 1.42GB 下载: 6次
热门标签
DeepSeek Jdk25 OpenAi HarmonyOS6 Nacos3 SpringBoot4 SpringCloud Docker Kubernetes Service Mesh Redis Gemini3 Rocky

欢迎您来访！

登录后，您将获得更多功能！
热门文章
联系我们

有任何问题或合作意向欢迎联系我们

Email: 99873273@qq.com

QQ: 99873273

用户登录
用户注册