• day20--Java集合03


    Java集合03

    8.LinkedList

    1)linkedList底层实现了双向链表双端队列的特点

    2)可以添加任意元素(元素可以重复),包括null

    3)线程不安全,没有实现同步

    • LinkedList的底层操作机制
      1. LinkedList底层维护了一个双向链表
      2. LinkedList中维护了两个属性first和last,分别指向首节点和尾节点
      3. 每个节点(Node对象)里面又维护了prev、next、item三个属性,其中通过prev指向前一个节点,通过next指向后一个节点,最终实现双向链表。
      4. 所以LinkedList的元素的添加和删除不是通过数组完成的,相对来说效率较高
    image-20220812165210269

    8.1双向链表

    双向链表202208121705

    例子:实现简单的双向链表

    package li.collections.list.linkedlist;
    public class LinkedListTest {
    public static void main(String[] args) {
    Node jack = new Node("jack");
    Node tom = new Node("tom");
    Node marry = new Node("marry");
    //连接节点,形成双向链表
    //jack-->tom-->marry
    jack.next = tom;
    tom.pre = jack;
    tom.next = marry;
    marry.pre = tom;
    Node first = jack;//让头节点指向Jack
    Node last = marry;//尾节点指向marry
    //从头到尾遍历
    while (true) {
    if (first == null) {
    break;
    }
    System.out.println(first);
    first = first.next;
    }
    System.out.println("==========");
    //从尾到头遍历
    while (true) {
    if (last == null) {
    break;
    }
    System.out.println(last);
    last = last.pre;
    }
    }
    }
    //定义一个Node对象,表示节点
    class Node {
    public Object item;//存放数据
    public Node next;//指针指向下一个节点
    public Node pre;//指针指向上一个节点
    public Node(Object name) {
    this.item = name;
    }
    @Override
    public String toString() {
    return "Node item=" + item;
    }
    }
    image-20220812172738715

    例子2:双向链表节点的增加和删除

    package li.collections.list.linkedlist;
    public class LinkedListTest {
    public static void main(String[] args) {
    Node jack = new Node("jack");
    Node tom = new Node("tom");
    Node marry = new Node("marry");
    //连接节点,形成双向链表
    //jack-->tom-->marry
    jack.next = tom;
    tom.pre = jack;
    tom.next = marry;
    marry.pre = tom;
    Node last = marry;//尾节点指向marry
    //链表添加数据
    //要求在tom和marry之间插入一个对象json
    Node json = new Node("json");
    //指针先连后删
    json.pre = tom;
    json.next = marry;
    marry.pre = json;
    tom.next = json;
    Node first = jack;//让头节点再次指向Jack
    //从头到尾遍历
    while (true) {
    if (first == null) {
    break;
    }
    System.out.println(first);
    first = first.next;
    }
    }
    }
    //定义一个Node对象,表示节点
    class Node {
    public Object item;//存放数据
    public Node next;//指针指向下一个节点
    public Node pre;//指针指向上一个节点
    public Node(Object name) {
    this.item = name;
    }
    @Override
    public String toString() {
    return "Node item=" + item;
    }
    }
    image-20220812175441341

    8.2LinkedList底层结构

    常用方法:

    image-20220812223502672

    例子1:LinkedList双向链表增加数据

    package li.collections.list.linkedlist;
    import java.util.LinkedList;
    public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    linkedList.add(1);
    linkedList.add(2);
    System.out.println("linkedList="+linkedList);
    }
    }
    1. 在执行LinkedList linkedList = new LinkedList();时,LinkedList底层创建了一个空的列表
    image-20220812182309277
    1. 执行linkedList.add(1);时,首先进行自动装箱(略),然后调用底层的add()方法,add()又调用linkLast()方法。
    image-20220812182344865 image-20220812190054956 image-20220812190542666

    linkLst()方法将新的节点加到双向链表的最后:

    首先创建一个node类型的常量 l ,首先将last的地址赋给l,因为刚开始没有数据,last指向null,因此l同样也指向null。

    image-20220812194014152

    再创建一个新的节点newNode,将add(1)传入的参数赋给newNode,newNode的pre指向l,即指向null,newNode的next也指向null。

    image-20220812194032328

    然后将last指向newNode
    image-20220812194101782

    第一次的l指向了null,因此执行first也指向新结点newNode语句

    image-20220812194409213

    最后是链表长度加1,修改次数modCount加1

    image-20220812194725735

    所以,第一个节点的时候情况如图:

    image-20220812214703327

    linkedList.add(2);执行第二次添加操作时,重复上述操作,最后来到linkLast()方法。

    1. 此时last指向的是第一个节点,执行final Node l = last;,则 l 也指向第一个节点。

    2. 再新建一个节点,将 l 设置为新结点的pre,即将新结点的前置节点设置为了第一个节点,将新结点的next设置为空。final Node newNode = new Node<>(l, e, null);

    3. 将last指向新结点

    4. 这里 l不再指向null,因此执行l.next=newNode;语句,因为l这时指向第一个节点,所以执行语句之后第一个节点的next将会指向newNode

    image-20220812190054956 image-20220812214944594

    例子2:双向链表删除数据

    package li.collections.list.linkedlist;
    import java.util.LinkedList;
    public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    linkedList.add(1);
    linkedList.add(2);
    linkedList.add(3);
    linkedList.remove();//这里默认删除第一个节点
    System.out.println("linkedList="+linkedList);//linkedList=[2, 3]
    }
    }

    image-20220812221112150image-20220812221125887

    image-20220812221155440

    分析unlinkFirst()方法:将f指向的双向链表中的第一个节点删除

    1. 首先在removeFirst()方法中将 f 指向第一个节点:final Node f = first;

    2. 然后取出第一个节点的值item:final E element = f.item;

    3. 然后将第一个节点next存储的地址赋给常量next,即将next指向第二个节点:final Node next = f.next;

    4. 然后将第一个节点的值置空,以及将第一个节点指向的地址置空,这样第一节点指向第二节点的next就断开了:f.item = null;

      f.next = null; // help GC

    5. 然后将next的地址赋给first,此时的next已经指向了第二个节点,所以first也指向第二个节点:first = next;

    6. 然后判断next是否为空,即判断删除的节点时候为最后一个节点,如果是,则将last置空;若否则将next指向节点的pre置空,也就是将第二个节点指向第一节点的指针断开。

    if (next == null)
    last = null;
    else
    next.prev = null;
    1. 而后链表长度-1,链表操作次数+1

    2. 最后返回删除数据的内容

    例子3:其他常用方法

    package li.collections.list.linkedlist;
    import java.util.Iterator;
    import java.util.LinkedList;
    public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    linkedList.add(1);
    linkedList.add(2);
    linkedList.add(3);
    //修改某个节点对象
    linkedList.set(1,999);//public E set(int index, E element)
    System.out.println("linkedList="+linkedList);//linkedList=[1, 999, 3]
    //得到某个节点对象
    System.out.println(linkedList.get(1));//得到第二个节点对象 999
    //遍历:因为LinkedList实现了List接口,所以LinkedList也可以使用增强for循环和迭代器
    // 1.增强for循环
    for (Object o:linkedList) {
    System.out.println(o);
    }
    //2.迭代器
    Iterator iterator = linkedList.iterator();
    while (iterator.hasNext()) {
    Object next = iterator.next();
    System.out.println(next);
    }
    //3.普通for循环
    for (int i = 0; i < linkedList.size(); i++) {
    System.out.println(linkedList.get(i));
    }
    }
    }

    8.3ArrayList和LinkedList的比较

    底层结构 增删的效率 改查的效率
    ArrayList 可变数组 较低:数组扩容 较高
    LinkedList 双向链表 较高:通过链表追加 较低

    如任选择ArrayList和LinkedList:

    1. 如果我们改查比较多,选择ArrayList
    2. 如果增删比较多,选择LinkedList
    3. 一般来说,在程序中百分之80到90都是查询,因此大部分情况下会选择ArrayList
    4. 在一个项目中,根据业务灵活查询,也可以两个集合一起用。一个模块使用ArrayList,另一个模块使用LinkedList
  • 相关阅读:
    C# 编写小巧快速的 Windows 动态桌面软件
    CAN通信波特率计算
    xsser工具使用教程
    智能壁炉:火焰的数字革命
    【2 线性表】奇偶数划分先后,奇在前偶在后。
    Selenium自动化测试 —— 通过cookie绕过验证码的操作!
    Mac Vue 项目上传到阿里云服务器及 nginx
    Rust常见集合
    JavaWeb基础9——Filter&Listener&Ajax
    RHCE第三天笔记
  • 原文地址:https://www.cnblogs.com/liyuelian/p/16581671.html