【Java】LinkedList 集合

这篇具有很好参考价值的文章主要介绍了【Java】LinkedList 集合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LinkedList集合特点

LinkedList 底层基于双向链表实现增删 效率非常高,查询效率非常低。


LinkedList源码解读分析

  1. LinkedList 是双向链表实现的 List
  2. LinkedList 是非线程安全的(线程是不安全的)
  3. LinkedList 元素允许为null,允许重复元素
  4. LinkedList 是基于链表是实现的,因此插入删除效率高(如果根据下标增删 效率还是非常低的),查询效率低
  5. LinkedList 是基于链表实现的,因此不存在容量不足的问题,所以没有扩容的方法
  6. LinkedList 还是实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用

【Java】LinkedList 集合,集合,链表,泛型,java,开发语言,集合,泛型,LinkedList 集合,手写LinkedList


示例代码:

package com.collection.Demo08;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;


public class Test01 {
    public static void main(String[] args) {
        /**
         * LinkedList 底层基于链表实现 增删 效率非常高 查询效率是非常低
         */
        List<String> linkedList = new LinkedList<>();
        linkedList.add("mayikt1");
        linkedList.add("mayikt2");
        linkedList.add("mayikt3");
        linkedList.get(0);
        /**
         * LinkedList get()底层是如何实现的呢?
         * 底层基于双向链表实现
         */
        System.out.println(linkedList.size());
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        System.out.println("===删除之后===");
        linkedList.remove(1);
        Iterator<String> iterator2 = linkedList.iterator();
        while (iterator2.hasNext()){
            System.out.println(iterator2.next());
        }
    }
}
package com.collection.Demo08;

import java.util.LinkedList;

public class Test02 {
    public static void main(String[] args) {
        LinkedList<String> strings = new LinkedList<>();
        strings.add("mayikt01");
        strings.add("mayikt02");
        strings.add("mayikt03");
        strings.remove(0);
        System.out.println(strings.get(0));//mayikt01
        System.out.println(strings.getFirst());//mayikt01
        System.out.println(strings.getLast());//mayikt03
    }
}

 手写LinkedList集合

package com.collection.Demo08;

/**
 * LinkedList底层是基于链表实现
 * 手写LinkedList集合
 */

public class MayiktLinkedList<E> {
    private Node<E> first;//第一个节点
    private Node<E> last; //最后一个节点
    int size = 0; //LinkedList存放的元素个数

    private static class Node<E> {
        private E item;//当前节点的值
        private Node<E> prev;//上一个节点
        private Node<E> next;//下一个节点
//        transient Node<E> next;// transient表示next节点不能够被序列化的

        /**
         * @param prev 当前节点的上一个节点
         * @param item 当前节点的值
         * @param next 当前节点的下一个节点
         */
        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    public void add(E e) {
        //add()创建一个新的node节点时,新的node节点的上一个节点是还未新增时的last尾节点
        Node l = last;//获取当前链表中最后一个节点
        //创建一个新的node节点
        //newNode节点的上一个节点,就是当前链表中的最后一个节点
        Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null) {
            //如果在链表中没有最后一个节点的话——链表为空
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 根据index 查询 链表中对应的node节点
     * 对半查找
     */
    Node<E> node(int index) {
        if (index < size >> 1) { //size >>1 =>size/2
            //查询链表中间值的左边
            Node<E> f = first;
            for (int i = 0; i < index; i++) {
                f = f.next;
            }
            return f;
        } else {
            //查询链表中间值的右边
            Node<E> l = last;
            for (int i = size - 1; i > index; i--) {
                l = l.prev;
            }
            return l;
        }
    }

    public E get(int index) {
        //下标如果越界的话 需要抛出异常
        return node(index).item;
    }

    //根据下标查询
    public E remove(int index) {
        return unlink(node(index));
    }

    private E unlink(Node<E> node) {
        //1.根据index 查询对应的node节点,时间复杂度为O(n)
        //2.删除链表效率非常高,比arrayList效率高,因为arrayList需要移动数组,而链表只需修改prev,next的指向问题
        //获取删除的node节点 上一个和下一个node节点
        final E element = node.item;//获取删除节点元素值
        Node<E> prev = node.prev;//删除节点的上一个节点
        Node<E> next = node.next;//删除节点的下一个节点
        //如果删除的节点 上一个节点为空
        if (prev == null) { //删除的该节点是头节点
            first = next;
        } else {
            prev.next = next;
            node.prev = null;//改为null,是为了通知GC 回收
        }
        if (next == null) {//删除的该节点是尾节点
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }
        node.item = null;//改为null,是为了通知GC 回收
        size--;
        return element;
    }

    public static void main(String[] args) {
        MayiktLinkedList<String> stringMayiktLinkedList = new MayiktLinkedList<>();
        stringMayiktLinkedList.add("mayikt01");
        stringMayiktLinkedList.add("mayikt02");
        stringMayiktLinkedList.add("mayikt03");
        stringMayiktLinkedList.add("mayikt04");
        stringMayiktLinkedList.remove(1);
        System.out.println(stringMayiktLinkedList.get(0));
        System.out.println(stringMayiktLinkedList.get(1));
//        System.out.println(stringMayiktLinkedList.get(2));
//        System.out.println(stringMayiktLinkedList.get(3));
    }
}

下一篇文章:HashMap集合文章来源地址https://www.toymoban.com/news/detail-734536.html

到了这里,关于【Java】LinkedList 集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Java】LinkedList 集合

    LinkedList集合特点 LinkedList 底层基于双向链表实现增删 效率非常高,查询效率非常低。 LinkedList源码解读分析 LinkedList 是双向链表实现的 List LinkedList 是非线程安全的(线程是不安全的) LinkedList 元素允许为null,允许重复元素 LinkedList 是基于链表是实现的,因此插入删除效率高

    2024年02月07日
    浏览(44)
  • Java集合之LinkedList源码篇

    ☆* o(≧▽≦)o *☆嗨~我是小奥🍹 📄📄📄个人博客:小奥的博客 📄📄📄CSDN:个人CSDN 📙📙📙Github:传送门 📅📅📅面经分享(牛客主页):传送门 🍹文章作者技术和水平有限,如果文中出现错误,希望大家多多指正! 📜 如果觉得内容还不错,欢迎点赞收藏关注哟!

    2024年01月16日
    浏览(43)
  • java源码----集合系列1----ArrayList,linkedList

    底层是一个object数组 Arraylist 是java里面Collection  标准的一个集合,其 底层是一个object数组 。当new一个空参的ArrayList的时候,会默认生成一个空数组。 Arraylist上限是 Integer.MAX_VALUE - 8(Integer.MAX_VALUE  =  2^31-1) ; 超过上限会报内存溢出 这里为什么是Integer.MAX_VALUE-8  ,源码上的解

    2024年02月03日
    浏览(44)
  • Java集合篇之深入解析LinkedList

    作为ArrayList的同门师兄弟,LinkedList的师门地位逊色不少,除了在做算法题的时候我们会用到它之外,在实际的开发工作中我们极少使用它,就连它的创造者都说:“I wrote it,and I never use it”,想想颇有点好笑,但这并不影响我们去学习它,个人认为它底层的链表逻辑对于我

    2024年02月19日
    浏览(40)
  • java集合框架(二)LinkedList常见方法的使用

    @[toc] ## 一、什么是LinkedList LinkedList是Java中的一个双向链表。 它实现了List和Deque接口,在使用时可以像List一样使用元素索引,也可以像Deque一样使用队列操作。 LinkedList每个节点都包含了前一个和后一个节点的引用,因此可以很方便地在其中进行节点的插入、删除和移动。 相

    2024年02月05日
    浏览(45)
  • Java基础——LinkedList集合实现栈和队列

    (1)LinkedList的特点: 底层数据结构是双链表,查询慢,首尾操作的速度是极快的,所以多了很多首位操作的特有API。 (2)LinkedList集合的特有功能: 方法名称 说明 public void addFirst(E e) 在该列表开头插入指定的元素 public void addLast(E e) 将指定的元素追加到此列表的末尾 publ

    2023年04月12日
    浏览(45)
  • 数据结构(Java实现)LinkedList与链表(上)

    链表 逻辑结构 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(53)
  • 数据结构(Java实现)LinkedList与链表(下)

    ** ** 结论 让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下: 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(46)
  • java基础-集合+泛型+枚举

    说明: 集合框架是一个类库的集合,里面还有很多接口。 里面虚框都是接口 。 全部在java.util HashSet是基于HashMap实现的。 TreeSet是一个有序Set。 ArrayList能快速随机访问,可变大小。 LinkedList随机访问相对慢,但是可以当作stack或者queue来用。 下面是List接口常用的方法: 使用的

    2024年02月20日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包