【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

    目录 基本介绍  常用方法 源码解析 1. LinkedList的底层结构,Node双向链表 2. LinkedList的几个内部变量 3. getFirst() 4. removeFirst() 5. addFirst(E e) 6. contains(Object o) 7. add(E e) 8. remove(Object o) 9. addAll(int index, Collection c) 10. get(int index) 11. spliterator() 总结 LinkedList是实现了List和Deque接口的双

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

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

    2024年01月16日
    浏览(40)
  • Java集合篇之深入解析LinkedList

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

    2024年02月19日
    浏览(37)
  • 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日
    浏览(43)
  • java集合框架(二)LinkedList常见方法的使用

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

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

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

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

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

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

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

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

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

    2024年02月20日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包