java基础:13.2 集合框架 - LinkedList、Queue
发布日期:2022-04-04 06:36:28 浏览次数:15 分类:博客文章

本文共 2647 字,大约阅读时间需要 8 分钟。

文章目录

与ArrayList一样,LinkedList也实现了List接口,诸如add,remove,contains等等方法。

双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。

按下标访问元素–get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起)。
插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作–add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动。

LinkedList 实现了:ListDeque (双向链表结构)、Queue(队列接口)。

 

1、Deque

LinkedList 
ll = new LinkedList
(); ll.addFirst("q0"); //头部加入 ll.addLast("q1"); // 尾部加入 System.out.println(ll.getFirst()); //查看最前面的对象 System.out.println(ll.getLast()); //查看最后面的对象 System.out.println(ll.removeFirst()); // 删除第一个对象 System.out.println(ll.removeLast()); // 删除最后一个对象 System.out.println(ll); // 取出会导致对象被删除

2、Queue

Queue是在两端出入的List,所以也可以用数组或链表来实现。

队列:先进先出FIFO
offer 在最后添加元素
poll 取出第一个元素
peek 查看第一个元素
LinkedList :以双向链表实现的LinkedList既是List,也是Queue。它是唯一一个允许放入null的Queue。
Queue<Hero> q= new LinkedList<Hero>();

还有很多Quene,比如ArrayDequePriorityQueue。。。

 

3、ArrayList 和 LinkedList 的区别

ArrayList

  1. 插入/删除数据速度慢。因为要把插入点后所有对象移位。
  2. 顺序结构,可直接定位到某个位置的对象,定位速度快。

LinkedList

  1. 插入,删除数据快。只要断开插入点的连接,重新连接到别的块就OK。
  2. 链表结构,不可以直接定位到某个位置的对象,必须根据链表的方向一个一个找,定位速度慢。
public class TestCollection {    public static void main(String[] args) {        List
l1 = new ArrayList<>(); List
l2 = new LinkedList<>(); insertFirst(l1,"ArrayList"); insertFirst(l2,"LinkedList"); } private static void insertFirst(List
l, String type) { int total = 1000 * 100; final int number = 5; long start = System.currentTimeMillis(); for (int i = 0; i < total; i++) { l.add(0, number); } long end = System.currentTimeMillis(); System.out.printf("在%s 最前面插入%d条数据,总共耗时 %d 毫秒 %n", type, total, end - start); } }

在ArrayList 最前面插入100000条数据,总共耗时 1006 毫秒

在LinkedList 最前面插入100000条数据,总共耗时 4 毫秒

4、练习

练习-使用LinkedList实现Stack栈

与FIFO(先入先出的)队列类似的一种数据结构是FILO先入后出栈Stack
根据接口Stack :
实现类:MyStack
public class MyStack implements Stack
并向这个栈中,压入5个英雄,接着弹出5个英雄
package collection;
import charactor.Hero;
public interface Stack {
//把英雄推入到最后位置
public void push(Hero h);
//把最后一个英雄取出来
public Hero pull();
//查看最后一个英雄
public Hero peek();
}

package collection;import java.util.LinkedList;import java.util.List;public class MyStack implements Stack{	LinkedList
heros = new LinkedList<>(); @Override //把英雄推入到最后位置 public void push(Hero h) { heros.addLast(h); } @Override public Hero pull() { // TODO Auto-generated method stub Hero h = heros.removeLast(); return h; } @Override public Hero peek() { // TODO Auto-generated method stub Hero h = heros.getLast(); return h; } }

转载地址:https://www.cnblogs.com/l20902/p/10610877.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java基础:13.3 集合框架 - 二叉树
下一篇:java基础:13.1 集合框架 - ArrayList

发表评论

最新留言

不错!
[***.144.177.141]2024年03月23日 10时29分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

dtc mysql_DTCC归来-高可用可扩展数据库架构探讨 2019-04-21
java怎样将日期本土化_Java中的日期操作 2019-04-21
java生产者消费者模型到精通_java生产者消费者模型 2019-04-21
java 执行 awk_3.1 biostar lesson3 linux学习日记;java版本;awk 2019-04-21
java二叉树求权值_百度笔试题目:二叉树路径权值和【转】 2019-04-21
欧亚马 java折叠车_如何选择欧亚马折叠车? 2019-04-21
python函数代码块以什么开头_Python初体验-开篇 代码全析 2019-04-21
java闹钟程序设计_JAVA课程设计_闹钟的设计与实现项目-报告_附源代码.doc 2019-04-21
java中的无效的列类型_java.sql.SQLException: 无效的列类型: 1111 2019-04-21
php rewrite url_PHP_URL Rewrite的设置方法,URL Rewrite需要服务器的支持! - phpStudy 2019-04-21
php读取大文件某行内容,PHP读取和修改大文件的某行内容_PHP教程 2019-04-21
打印php错误日志,php怎样打印错误日志 2019-04-21
Calendar导入java,Java程序使用Calendar.add()方法将分钟添加到当前时间 2019-04-21
mysql中用户线程作用,mysql用户线程的建立与用户线程的状态源码解析 2019-04-21
php页面引用公共文件,WeiPHP插件模板中快速引入公共模板文件 2019-04-21
php tracy,admin.php 2019-04-21
php访问父类的所有属性,php – 在父类中使用$this仅在子类中显示父类属性 2019-04-21
oracle比较强大的函数,SQL和ORACLE函数比较 2019-04-21
oracle12c order by,oracle 数据库中order by 的一些高级用法 2019-04-21
oracle8i substr,Oracle中的INSTR,NVL和SUBSTR函数的用法详解 2019-04-21