精华内容
下载资源
问答
  • LinkedList

    千次阅读 多人点赞 2018-07-19 16:49:38
    LinkedList也实现了List接口,相对于ArrayList来说,它们的最大区别在于底层数据结构不同,LinkedList的底层是一个双向链表,这也决定了它的最大优点,那就是对于数据的修改比ArrayList更加方便快捷。 相对于...

    LinkedList也实现了List接口,相对于ArrayList来说,它们的最大区别在于底层数据结构不同,LinkedList的底层是一个双向链表,这也决定了它的最大优点,那就是对于数据的修改比ArrayList更加方便快捷。
    相对于ArrayList,LinkedList插入是更快的。因为LinkedList不需要改变数组的大小,也不需要在数组装满的时候要将所有的数据重新装入一个新的数组,类似于插入数据,删除数据时,LinkedList也优于ArrayList,其时间复杂度仅为O(1),而ArrayList删除数据是开销很大的,因为这需要重排数组中的所有数据(除了最后一个元素)。
    下面来看看LinkedList的一些常用方法。



    基本特点:

    1.非同步,线程不安全;
    2.支持null元素,元素可以重复;
    3.可以被当作堆栈、队列或双端队列进行操作。
    4.实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
    5.LinkedList包含两个重要的成员:header 和 size。

    	 ·header是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。
    其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 
    	 ·size是双向链表中节点的个数。
    


    常用方法:

    1、add(E e),添加元素,addAll(C c)添加一个集合,返回值都是boolean型。

    		LinkedList<Integer> linkedList = new LinkedList<>();
    		// 默认是尾插
            linkedList.add(10);
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.add(10);
            linkedList.addAll(arrayList);
    

    2.remove(O o),删除元素,参数可选,o值可以为null,返回值是boolean型。

    		// 参数为空时删除头结点
    		linkedList.remove();
    		linkedList.remove(10);
    

    3.get(int index),set(int index, E e),获取与修改,LinkedList体现优点的方法。

    		// 当指定索引超出数据个数时会产生越界异常,返回值是原来索引位置的数据
    		System.out.println(linkedList.set(0,20));
    		// 当指定索引超出数据个数时同样会产生越界异常
    		System.out.println(linkedList.get(10));
    

    4.LinkedList的迭代器

    		Iterator<Integer> integer = linkedList.iterator();
            while(integer.hasNext()){
                System.out.print(integer.next() + " ");
            }
            System.out.println();
    


    使用场景:

    结合LinkedList的优点,可以知道LinkedList适用于对数据进行频繁的修改操作的场景。



    简单实现:

    	class MyLinkedList<T> {
    	    /**
    	     * 结点类
    	     */
    	    class Entry{
            /**
             * 后驱
             */
            private Entry next;
            /**
             * 前驱
             */
            private Entry prev;
            /**
             * 数据
             */
            private T data;
            /**
             * 下标
             */
            private int index;
    
            /**
             * 默认构造方法
             */
            private Entry(){
                this.data = null;
                this.index = -1;
                this.next = null;
                this.prev = null;
            }
    
            /**
             * 带数据的构造方法
             * @param data
             */
            private Entry(T data){
                this.data = data;
                this.index = -1;
                this.next = null;
                this.prev = null;
            }
        }
    
        /**
         * 构造函数
         */
        private Entry head;
        public MyLinkedList(){
            head = new Entry();
        }
    
        /**
         * 添加
         * @param data
         */
        public void add(T data){
            Entry cur = head;
            while (cur.next != null){
                cur = cur.next;
            }
            Entry entry = new Entry(data);
            cur.next = entry;
            entry.prev = cur;
            entry.index = entry.prev.index + 1;
        }
    
        /**
         * 默认删除最后一个结点
         * @return
         */
        public T remove(){
            Entry cur = head;
            while(cur.next != null) {
                cur = cur.next;
            }
            T oldValue = cur.data;
            cur.index = -1;
            cur.data = null;
            cur.prev.next = null;
            return oldValue;
        }
    
        /**
         * 删除指定结点
         * @param data
         */
        public void remove(T data){
            Entry cur = head.next;
            while (cur != null){
                if (cur.data == data){
                    cur.data = null;
                    cur.prev.next = cur.next;
                    while(cur.next != null){
                        cur.next.index--;
                        cur = cur.next;
                    }
                    if (cur.next != null){
                        cur.next.prev = cur.prev;
                    }
                }
                cur = cur.next;
            }
        }
    
        /**
         * get方法
         * @param index
         * @return
         */
        public T get(int index){
            Entry cur = head;
            while(cur.next != null) {
                cur = cur.next;
                if (cur.index == index){
                    return cur.data;
                }
            }
            return null;
        }
    
        /**
         * set方法
         * @param index
         * @param data
         * @return
         */
        public T set(int index, T data){
            Entry cur = head;
            while (cur.next != null){
                cur = cur.next;
                if (cur.index == index){
                    T oldValue = cur.data;
                    cur.data = data;
                    return oldValue;
                }
            }
            return null;
        }
    
        /**
         * 输出
         */
        public void print(){
            Entry cur = head.next;
            while (cur != null){
                System.out.print(cur.data + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
    
    展开全文
  • ArrayList和LinkedList的区别 优点 缺点 和应用场景

    ArrayList 和 LinkedList

    相同点

    1. 都是List接口的容器类
    2. 都用于存储一系列对象的引用
    3. 都可以对元素进行CRUD

    不同点

    名称 ArrayList LinkdeList
    结构 动态数组 链表
    应用 查询 添加
    get/set 慢(移动指针)
    add/remove 慢(移动数据)

    缺点

    ArrayList 缺点

    1. ArrayList: 在内部构成是数组形式 增加一项内容时 有可能导致数组重新分配
      但对于 LinkedList: 这个开销是固定的,因为是在内存中分配一个entry然后通过指针指向
    2. ArrayList: 如果添加或者删除一个内容时,列表中的全部对象都要进行移动.
      但对于 LinkedList:添加或者删除一个元素时,开销是固定的
    3. 在list列表的结尾处预留了一定的容量空间
      因为本身的存储结构导致的

    LinkedList缺点

    不支持高效的随机访问 因为linkedList从开头开始遍历 , 每次随机访问都会重新遍历

    展开全文
  • LinkedList优点: 长度可变 插入删除简单 LinkedList缺点: 不能随机访问,必须从head结点顺序访问,所以也就不能够二分查找 存储pointer消耗内存 下面是LinkedList的简单实现以及简单操作(各个位置插入新节点,...

    LinkedList即单链表,如下图
    这里写图片描述
    LinkedList优点:

    1. 长度可变
    2. 插入删除简单

    LinkedList缺点:

    1. 不能随机访问,必须从head结点顺序访问,所以也就不能够二分查找
    2. 存储pointer消耗内存

    下面是LinkedList的简单实现以及简单操作(各个位置插入新节点,打印单链表):

    class LinkedList
    {
        Node head; 
        class Node
        {
            int data;
            Node next;
            Node(int d) {data = d; next = null; }
        }
    
        /* Inserts a new Node at front of the list. */
        public void push(int new_data)
        {
            Node new_node = new Node(new_data);
            new_node.next = head;
            head = new_node;
        }
    
        /* Inserts a new node after the given prev_node. */
        public void insertAfter(Node prev_node, int new_data)
        {
            if (prev_node == null)
            {
                System.out.println("The given previous node cannot be null");
                return;
            }
            Node new_node = new Node(new_data);
            new_node.next = prev_node.next;
            prev_node.next = new_node;
        }
    
        /* Appends a new node at the end.  This method is 
           defined inside LinkedList class shown above */
        public void append(int new_data)
        {
            Node new_node = new Node(new_data);
            if (head == null)
            {
                head = new Node(new_data);
                return;
            }
            new_node.next = null;
            Node last = head; 
            while (last.next != null)
                last = last.next;
            last.next = new_node;
            return;
        }
    
        /* This function prints contents of linked list starting from
            the given node */
        public void printList()
        {
            Node tnode = head;
            while (tnode != null)
            {
                System.out.print(tnode.data+" ");
                tnode = tnode.next;
            }
        }
    
        public static void main(String[] args)
        {
            /* Start with the empty list */
            LinkedList llist = new LinkedList();
    
            // Insert 6.  So linked list becomes 6->NUllist
            llist.append(6);
    
            // Insert 7 at the beginning. So linked list becomes
            // 7->6->NUllist
            llist.push(7);
    
            // Insert 1 at the beginning. So linked list becomes
            // 1->7->6->NUllist
            llist.push(1);
    
            // Insert 4 at the end. So linked list becomes
            // 1->7->6->4->NUllist
            llist.append(4);
    
            // Insert 8, after 7. So linked list becomes
            // 1->7->8->6->4->NUllist
            llist.insertAfter(llist.head.next, 8);
    
            System.out.println("\nCreated Linked list is: ");
            llist.printList();
        }
    }

    供后续方便查阅

    展开全文
  • ArrayList和LinkedList的各自优点

    千次阅读 2010-04-03 14:00:00
    java编程中我们用最多的几个类可以...我们来看看ArrayList和LinkedList的区别. 故名思意ArrayList是数组表,LinkedList是链接表. ArrayList的所有数据是在同一个地址上,而LinkedList的每个数据都拥有自己的地址. ...

    java编程中我们用最多的几个类可以就是String,ArrayList,HashMap了.

    特别是ArrayList我们几乎无人不知,甚至有乱用的嫌疑了.

    我们来看看ArrayList和LinkedList的区别.

    故名思意ArrayList是数组表,LinkedList是链接表.

    ArrayList的所有数据是在同一个地址上,而LinkedList的每个数据都拥有自己的地址.

    展开全文
  • 联系:都实现了List接口 有序 不唯一 区别: 1.ArrayList 优点:遍历元素...2.LinkedList 优点:插入 删除效率高 前提是必须低效率查询, 缺点:遍历和访问元素效率低 特点:采用链表的存储方式 ,底层是双向链表 ...
  • LinkedList 优点:插入、删除元素效率高 缺点:遍历数据效率低。 本文基于JDK1.8.131的源码分析(其他版本的源码,不做表述)。 数据结构 底层实现,双向链表 1.构造方法 构造方法以及涉及到的方法: transient ...
  • LinkedList 学习

    2018-08-09 16:59:46
    优点LinkedList 基于链表,插入删除快,但读取较慢 缺点:线程不安全,读取慢 LinkedList 链表的基础实现 private static class Node&amp;amp;lt;E&amp;amp;gt; { E item; Node&amp;amp;lt;E...
  • 优点LinkedList 基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作,LinkedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。 缺点:...
  • LinkedList集合

    2019-02-07 12:08:35
    1、LinkedList集合的原理  LinkedList底层是用链表实现 2、LinkedList集合的使用方法 LinkedList list = new LinkedList(); //增加在链表头部增加节点 list.addFirst(&quot;a&quot;); //增加在链表尾部增加...
  • 2、LinkedList优点:插入元素时比ArrayList效率高。 缺点:随机访问速度较ArrayList慢。综上所述,当需要频繁查找元素,且插入元素在链表尾部的时候可选择ArrayList当频繁插入元素,且插入位置在链表中的时候选择...
  • 链表LinkedList

    2020-05-09 11:18:01
    链表LinkedList 真正的动态数据结构,也是最简单的动态数据结构,有助于我们更加深入的理解引用(指针),递归 数据存储在“节点”(Node)中 Class Node{ E e; Node next; } 优点:真正的动态,不需要处理固定...
  • ArrayList 优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会...优点LinkedList是基于链表的数据结构,地址是任意的,所以在开辟内存空间时不需要等一个连续的...
  • 袋子重点:1、放 增加 2、取, 3、放之后,调整顺序,4、查找 1、List ,保持不变,有点像队列,先排先得到;... 2》LinkedList优点:  2.1 在中间放(加),扔掉(删除)东西最快。  2.2 在ArrayL
  • LinkedList特点

    2020-11-01 22:02:30
    LinkedList特点和底层实现 LinkedList的特点和存储结构 LinkedList底层用双向链表实现存储 特点:增删效率高,查询效率低,线程不安全 双向链表也叫双链表,是链表的一种,它的每个数据节点都有两个指针,分别指向前...
  • LinkedList讲解

    2017-08-15 21:58:16
    ArrayList和LinkedList的区别: ArrayList是可变长度的数组,分配空间是连续的。他的存储特点是:有序但是不唯一 LinkedList是链表形式存储的,他分配的...ArrayList的优点:查找遍历比较高效。(因为他是可变长度的数
  • 链表LinkedList  优点:插入元素快  缺点:查找元素慢  .net framework只提供了泛型版本  继承接口:ICollection<T>, IEnumerable<T>, ICollection, IEnumerable 常用方法和属性:  ...
  • LinkedList源码

    2019-03-24 14:26:16
    LinkedList底层是基于双向链表,链表在内存中不是连续的,而是通过引用来关联所有的元素,所以链表的优点在于添加和删除元素比较快,因为只是移动指针,并且不需要判断是否需要扩容,缺点是查询和遍历效率比较低。...
  • LinkedList详解

    2014-07-26 14:55:44
    linkedList底层是用节点类实现,我们来分析自己写的lIN
  • java中的List有两种类型 ...2、LinkedList 优点:插入元素时比ArrayList效率高。 缺点:随机访问速度较ArrayList慢。 综上所述,当需要频繁查找元素,且插入元素在链表尾部的时候可选择ArrayList ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,849
精华内容 11,139
关键字:

linkedlist优点