精华内容
下载资源
问答
  • ArrayList,LinkedList,Vector这三类都实现了java.util.List接口,但它们有各自不同的特性,主要如下: 一、同步性 ArrayList,LinkedList是不同步的,而Vector是同步的。【这里的不同步指的是。当使用线程和web的...

    java集合源码分析(推荐给看源码很吃力的朋友们): https://www.cnblogs.com/skywang12345/p/3323085.html#top
    ArrayList内部是动态数组实现,在增加空间时会复制全部数据到新的容量大一些的数组中。而LinkedList内部为双向链表,可以按需分配空间,扩展容量简单,因此LinkedList插入数据用时少

    ArrayList,LinkedList,Vector这三个类都实现了java.util.List接口,但它们有各自不同的特性,主要如下:

    一、同步性

    ArrayList,LinkedList是不同步的,而Vector是同步的。【这里的不同步指的是。当使用线程和web的时候,对这个集合对象进行操作,那么不同的线程,和不同的web客户端所获取的这个集合对象是不同的。所以是说不同步,且不安全的】所以如果不要求线程安全的话,可以使用ArrayList或LinkedList,可以节省为同步而耗费的开销。但在多线程的情况下,有时候就不得不使用Vector了。当然,也可以通过一些办法包装ArrayList,LinkedList,使他们也达到同步,但效率可能会有所降低。

    二、数据增长

    从内部实现机制来讲ArrayList和Vector都是使用Object的数组形式来存储的。当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销。

    三、检索、插入、删除对象的效率
    ArrayList和Vector中,从指定的位置(用index)检索一个对象,或在集合的末尾插入、删除一个对象的时间是一样的,可表示为O(1)。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置。为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。
    LinkedList中,在插入、删除集合中任何位置的元素所花费的时间都是一样的—O(1),但它在索引一个元素的时候比较慢,为O(i),其中i是索引的位置。

    在此,我们总结一下ArrayList和LinkedList的大致区别:
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
    2.对于随机访问get和set,ArrayList绝对优于LinkedList,因为LinkedList要移动指针。
    3.对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。

    ArrayList和LinkedList是两个集合类,用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。
    那么ArrayList和LinkedList在性能上有什么差别呢?什么时候应该用ArrayList什么时候又该用LinkedList呢? 我们下面就来解答这个问题:
    一.时间复杂度
    首先一点关键的是,ArrayList的内部实现基于基础的对象数组,因此,它使用get方法访问列表中的任意一个元素时 (random access),时间复杂度是O(1)它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查,直到另外一端。对 LinkedList而言,时间复杂度是O(i),访问列表中的某个指定元素没有更快的方法了。

    二.空间复杂度
    在LinkedList中有一个私有的内部类,定义如下:

    private static class Entry {   
        Object element;   
        Entry next;   
        Entry previous;   
    } 
    

    每个Entry对象reference列表中的一个元素,同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将 有1000个链接在一起的Entry对象,每个对象都对应于列表中的一个元素。这样的话,在一个LinkedList结构中将有一个很大的空间开销,因为 它要存储这1000个Entity对象的相关信息。

    ArrayList使用一个内置的数组来存储元素,这个数组的起始容量是10(据说现在初始容量是0).当数组需要增长时,新的容量按如下公式获得:新容量=(旧容量*3)/2+1,也就是说每一次容量大概会增长50%。这就意味着,如果你有一个包含大量元素的ArrayList对象, 那么最终将有很大的空间会被浪费掉,这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素,数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配,将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素,我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

    三.总结

    ArrayList和LinkedList在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:

    1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。

    2.在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。

    3.LinkedList不支持高效的随机元素访问。

    4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间 。

    可以这样说:当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能;当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。 所以,如果只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作,最好选择LinkedList!

    【ArrayList和LinkedList的区别有点类似与我们熟知的数组和链表之间的区别】

    1.ArrayList:底层是数组结构,长度可变,相当于一个可扩充的数组,线程不同步。增删速度慢,查询速度快。ArrayList是按照原数组的50%延长。构造一个初始容量为10的空列表。

    可变长度数组的原理:不断new新数组并将原数组元素复制到新数组。当元素超出数组长度,会产生一个新数组,将原数组的数据复制到新数组中,再将新的元素添加到新数组中。

    2.优点:数组结构的优点是便于对集合进行快速的随机访问,如果经常需要根据索引位置访问集合中的对象,使用由ArrayList类实现的List集合的效率较好。

    3.缺点:向指定索引位置插入对象和删除指定索引位置对象的速度较慢,如果经常需要向List集合的指定索引位置插入对象,或者是删除List集合的指定索引位置的对象,使用由ArrayList类实现的List集合的效率则较低,并且插入或删除对象的索引位置越小效率越低,原因是当向指定的索引位置插入对象时,会同时将指定索引位置及之后的所有对象相应的向后移动一位。当删除指定索引位置的对象时,会同时将指定索引位置之后的所有对象相应的向前移动一位.

    LinkedList:底层数据结构是链表,线程不同步。增删速度快。查找速度慢(在内存中需要一个个查询,判断地址来寻找下一个元素)。可以利用LinkedList实现堆栈(先进后出),队列结构(先进先出)。

    在这里插入图片描述那么为什么数组查询就快了呢?因为假设数组里面保存的是一组对象,每个对象都有内存大小,例如对象中有一个字段是int类型占用4个字节(只考虑实际数据占用的内存),数组在堆上的内存在数组被创建出来就被确定了是40个字节.如果我们要查找第9个对象,可以通过(9-1)*4=32,从33到36字节就是我们要找的对象.是不是很快呢?而链表却不能做到这样的效率.如上图,我们要找到A4,必须先找到A3,再先找到A2,再先找到A1.这样的查找效率会大大降低.

    好了,说了查找,再说说插入,数组的插入也相当的浪费效率,如果要在数组内的某一个位置进行插入,需要先将插入位置的前面复制一份,然后在新的数组后面添加新的元素,最后将旧的数组后半部分添加的新的数组后面,而在链表中插入就变得相当简单了,比如我要在A3和A4中插入B,只需定位到A3的指针和A4的数据即可,将A3的指针指向B的值,将B的指针指向A4的值,B就插入进了链表.

    ArrayLIst查询效率高:ArrayLIst是连续存放元素的,找到第一个元素的首地址,再加上每个元素的占据的字节大小就能定位到对应的元素。
    LinkedList插入删除效率高。因为执行插入删除操作时,只需要操作引用即可,元素不需要移动元素,他们分布在内存的不同地方,通过引用来互相关联起来。而ArrayLIst需要移动元素,故效率低。

    ArrayList是动态扩展数组,底层是用数组实现,插入位置有三种情况,从首位插入,中间位置插入,尾部插入。线性表的插入删除操作都是通过移动来实现的,由于数组长度固定不变,插入数据时,需要一个新的数组。
    1.当添加数据是在首位插入时,先将新的数据放入到新的数组内,然后将原始数组中的数据复制到新的数组。
    2.当数据插入的位置是中间位置时,先将插入位置前面的数据先放到新的数组里,再放新的数据,再复制旧的数据完成添加。3.数据尾部插入,由于不会影响其他元素,因此会直接插入到后面。
    同样,删除按位置也有三种情况:
    1.从头部删除,删除头结点然后移动后面的数据
    2.从中间指定位置删除,找到要删除数据的位置,删除后,后面的数据移动.
    3.从尾部删除:直接删除尾部数据完成删除操作。
    LinkedList是双向链表的数据结构,底层是用链表实现,是由相互引用的节点组成的双向链表,当插入数据到某个位置时,这个数据会形成一个新的节点,然后改变链表中对应的两个节点的引用关系就可以完成插入。同样,删除数据时,删除对应节点的引用就可以完成删除操作

    展开全文
  • * LinkedList 底层是一双向链表 模拟实现 */ public class MyLinkedList { private int size = 0; private node head; private node last; class node { node pre; node next; S
    package cn.sdut.chapter5;
    
    /*
     * LinkedList 底层是一个双向链表   模拟实现
     */
    public class MyLinkedList {
    
    	private int size = 0;
    	private node head;
    	private node last;
    
    	class node {
    		node pre;
    		node next;
    		String data;
    
    		node(String data) {
    			this.data = data;
    		}
    
    	}
    
    	// 添加
    	public void add(String str) {
    		node node = new node(str);
    		if (size == 0) {
    			this.head = node;
    			this.last = node;
    		} else {
    			this.last.next = node;
    			node.pre = this.last;
    			this.last = node;
    		}
    		size++;
    
    	}
    
    	public void print() {
    		node current = this.head;
    		while (current != null) {
    			System.out.println(current.data);
    			current = current.next;
    		}
    
    	}
    
    	//删除
    	public void remove(String str) {
    		node current = this.head;
    		while (current != null) {
    			if (current.data.equals(str)) {
    				if (current == this.head) {
    					this.head = current.next;
    					this.head.pre = null;
    				} else if (current == this.last) {
    					this.last = current.pre;
    					this.last.next = null;
    				} else {
    					current.next.pre = current.pre;
    					current.pre.next = current.next;
    				}
    				size--;
    				break;
    			} else {
    				current = current.next;
    			}
    
    		}
    	}
    
    }
    

    展开全文
  • 创建LinkedList对象,从这里开始 0、无参 public LinkedList() { } 默认的构造方法,是我们最常用的,它只是new了一对象 1、一参数,接受一Collection对象 public LinkedList(Collection<? ...

    (注意:本文源码基于JDK1.8) 

    创建LinkedList对象,从构造方法开始,接下来分析构造方法

     

    无参数的构造方法分析

        public LinkedList() {
        }

    创建LinkedList对象,方法体中什么也没有做。注意:隐式的执行了super()调用基类的构造方法!

     

    传入一个参数的构造方法分析

        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }

    传入参数为Collection对象,持有了多个元素,表示创建LinkedList对象后,同时添加多个元素

    1、调用无参数的构造方法

    首先调用无参的构造方法,目的是为了显式调用父类的构造方法,另外也可以初始化持有的其他实例变量

    2、调用addAll()方法,并将传入的Collection对象c传入进去,addAll()方法会添加多个元素进去

     

    重要字段介绍

    1、继承父类的实例变量modCount

    用于fail-fast机制检测

    2、三个实例变量+一个常量

    transient int size = 0;   
    transient Node<E> first; 
    transient Node<E> last;
    private static final long serialVersionUID = 876323262645176354L;

    size:表示LinkedList对象持有的元素总数,该实例变量使用transient修饰,不参与对象的序列化

    first:表示LinkedList对象持有的第一个结点对象,不参与对象序列化

    last:表示LinkedList对象持有的最后一个结点对象,不参与对象序列化

    serialVersionUID:一个常量值,反序列化对象时,JVM使用该UID值,与加载类库中的UID作一个对比,两个值一致才会进行反序列化对象,否则抛出一个异常,类版本不一样

     

    总结

    1、LinkedList基于一个双向链表,LinkedList对象持有双向链表头结点对象的引用,实例变量first指向此Node对象

    2、LinkedList对象持有表示双向链表尾结点对象的引用,实例变量last指向此Node对象

    3、LinkedList的父类为AbstractList,与ArrayList是同一个父类,实例变量modCount定义在AbstractList类中

    展开全文
  • Golang】实现 题目描述 给定两链表,寻找两链表的第一公共节点。 思路 第一种思路,创建一HashSet,先遍历一...这种方法的时间复杂度为O(n + k),空间复杂度为O(n),n是第一条链表节点数,k是第二条链...

    点击查看剑指Offer全解【Java & Golang】实现

    题目描述

    给定两个链表,寻找两个链表的第一个公共节点。
    在这里插入图片描述

    思路

    第一种思路,创建一个HashSet,先遍历一遍链表一,并且存储每个节点在HashSet中,接着遍历链表二,如果出现了HashSet中的节点,那么该节点就是第一个公共节点。这种方法的时间复杂度为O(n + k),空间复杂度为O(n),n是第一条链表节点数,k是第二条链表节点数。

    第二种思路,两个链表中,我们可以先遍历一次得到它们的长度分别为5 和4, 也就是较长的链表与较短的链表相比多一个结点。第二次先在长的链表上走1 步,到达结点2。接下来分别从结点2 和结点4 出发同时遍历两个结点, 直到找到它们第一个相同的结点6,这就是我们想要的结果。这种做法的时间复杂度也是O(n + k),但是不需要额外的空间复杂度,为O(1)。


    Java第一种思路实现

    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    import java.util.HashSet;
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            HashSet<ListNode> set = new HashSet<>();
            while (pHead1 != null) {
                set.add(pHead1);
                pHead1 = pHead1.next;
            }
            while (pHead2 != null) {
                if (set.contains(pHead2)) {
                    return pHead2;
                }
                pHead2 = pHead2.next;
            }
            return null;
        }
    }
    

    Java第二种思路实现

    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    import java.util.HashSet;
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
            int length1 = getListLength(head1);
            int length2 = getListLength(head2);
            int step = length1 - length2;
            if (step > 0) {
                for (int i = 0; i < step; i++) {
                    head1 = head1.next;
                }
            } else {
                for (int i = 0; i < -step; i++) {
                    head2 = head2.next;
                }
            }
            while (head1 != null && head2 != null) {
                if (head1 == head2) {
                    return head1;
                }
                head1 = head1.next;
                head2 = head2.next;
            }
            return null;
        }
    
        private static int getListLength(ListNode head) {
            int result = 0;
            while (head != null) {
                result++;
                head = head.next;
            }
            return result;
        }
    }
    

    Golang第一种思路实现

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func getIntersectionNode(headA, headB *ListNode) *ListNode {
        set := make(map[*ListNode]string)
        for headA != nil {
            // 使用map充当set
            set[headA] = "PRESENT"
            headA = headA.Next
        } 
        for headB != nil {
            if _, ok := set[headB]; ok{
                return headB
            }
            headB = headB.Next
        }
        return nil
    }
    

    Golang第二种思路实现

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func getIntersectionNode(headA, headB *ListNode) *ListNode {
        lenA := getLength(headA)
        lenB := getLength(headB)
        step := lenA - lenB
        if step > 0 {
            for i := 0; i < step; i++ {
                headA = headA.Next
            }
        } else {
            for i := 0; i < -step; i++ {
                headB = headB.Next
            }
        }
        for headA != nil && headB != nil {
            if headA == headB {
                return headA
            }
            headA = headA.Next
            headB = headB.Next
        }
        return nil
    }
    func getLength(head *ListNode) int {
        cur := head
        count := 0
        for cur != nil {
            count++
            cur = cur.Next
        }
        return count
    }
    
    展开全文
  • 手写基本容器——LinkedList底层实现1、建立一Node...2、每表的开始都是有一first和last来记录我们的和最后一的value值的地址就可以,然后中间的部分我们可以使用“前一”和“下一”来遍历整个数...
  • 1、LinkedList底层实现原理 ...每一节点都有三元素,一是当前节点的数据,也就是data部分,data左边就是指向该节点的上一节点的指针,右边就是指向该节点的下一节点的指针。 既然是双向链表,那么必定存...
  • 0、LinkedList实现了List接口、Deque接口,一既可以做线性表、又可以做栈、又可以做队列的super容器 1、LinkedList的底层数据结构是双向链表,插入与删除的效率很高哦,O(1)就搞定了 2、LinkedList查找就...
  • 1、实现了Iterable接口的类具有迭代功能。 2、List接口为Collection的子类,表示线形数据列表,其实现类有:ArrayList(数组线性表)与LinkedList(链表) ...4、LinkedList元素的Pre值一定为nell ,可...
  • 源码分析LinkedList

    2018-09-18 13:39:23
    目录 一、分析 、变量 三、方法 四、内部类 五、总结 实现原理 ... LinkedList 双向链表,支持null元素 、变量 ... * 指向元素节点 */ transient Node&lt;E&gt; first; ...
  • 文章目录1、ArrayList、LinkedList、HashMap中都有一字段叫modCount(表示list结构上被修改的次数。)1.1 该字段被Iterator以及ListIterator的实现类所使用,如果该值被意外更改,Iterator或者ListIterator 将抛出...
  • import java.util.LinkedList; public class StudentList2 { // 自我介绍方法 public void printer(Student student){ System.out.println("我是" + student.getName() + ",性别" + ...
  • LinkedList 相关

    2020-09-22 13:25:53
    LinkedList1 链表数据结构 1 链表数据结构 对于链表数据结构来说,基本的单元是节点Node 对于单向链表来说,任何一节点Node都有两属性: 第一是:存储的数据。第二是:下一节点的内存地址 ...
  • LinkedList集合

    2021-04-08 23:27:49
    第二:下一节点的内存地址 3.LinkedList集合底层也是有下标的 4.注意:ArrayList之所以检索效率比较高,不是单纯因为下标的原因。是因为底层数组发挥的作用。 5.LinkedList集合照样有下标,但是检索/查找某个...
  • 专栏第二篇,本文主要内容是手写一 LinkedList。 知识图谱 先呈上来链表章节的知识图谱。 Talk is cheap. Show me the code. – Linus Torvalds 手写 LinkedList package ...
  • 手写LinkedList

    2020-06-03 16:48:12
    一、 、 package com.ckw.test.linkedlist; /** * @author ckw * @version 1.0 * @date 2020/6/3 16:11 * @description: ...public class ... // 节点 private Node last; // 最后一节点 /
  • List--LinkedList(浅识)

    2016-05-02 20:07:36
    LinkedList是List接口的一实现类,用于存储数据对象。...所以说LinkedList分配内存为不连续的,只是结点之间保存了对上下节点地址的引用,这就导致了当查找LinkedList存储的数据时都需从节点开始查找。Lin
  • Golang】实现 题目描述 输入一链表,输出该链表中倒数第k结点。 思路 ...第二种思路是使用快慢指针,让fast指针快slow指针k节点,那么在fast指针指向末尾null时,则说明slow指针当前已经...
  • 1、LinkedList概述 1、链表在内存中有什么...如果是靠头近,那么从开始遍历;如果靠尾近,那么从最后一开始遍历。 A:多节点之间,通过地址进行连接。 例如,多个人手拉手,每人使用自己的右手拉住...
  • 第二部分:LinkedList数据结构 第三部分:LinkedList源码分析 第四部分:LinkedList遍历方式 第五部分:示例 第一部分:简介 LinkedList是一继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、...
  • 在这类中需要定义三属性: public class Node2 { Node2 previous; String data; Node2 next; } 1)先定义一Node2的类用于定义双向链表的属性 package com.ahuier; public class Node2 { Node2 ...
  • //节点 transient Node<E> first; //最后一节点 transient Node<E> last; 静态内部类 private static class Node<E> { E item;//节点的具体元素 Node<E> n.
  • linkedList的底层实现中,存储一表头first节点指向链表的节点,存储一last节点,指向链表的最后一节点,而每节点又存储了一指向其前一节点(previous)和后一节点(next)的指针。package ...
  • 本文是第二LinkedList。 ---@pdai JDK版本 JDK 1.8.0_110 概述总结 LinkedList底层是通过双向链表实现的,具体是first和last两node元素; 链表的特性决定了LinkedList按照index查找元...
  • LinkedList-源码

    2021-03-09 19:39:02
    第一个节点指向第二个节点,第二个节点指向第三个节点,依此类推。链接列表在Java标准库中可用,并且比在此分配中实现的操作要多得多。 链表上最常见的操作是add , remove和调整size 。 您将在代码模板的帮助下...
  • jdk1.8 LinkedList

    2019-08-30 15:12:52
    JDK1.8 LinkedList源码 ...第二句new Node()就表示创建一新节点,节点元素为e,前继节点为l,后继节点为null add()方法的返回值为布尔类型,只会返回true; 添加的过程就是调用linkLast方法的过程,其中它会先将最后一...
  • 双向链表的意思就是元素一个接一个的链接上去,例如有一个LinkedList, 有3个元素,第一个元素记录第二个和第四个元素的内存地址,第二个元素记录第一个和第三个元素的内存地址,第三个元素记录第一个元素的内存地址...
  • 手工实现linkedList

    2019-08-24 17:00:04
    第一个的next 是第二个第二个的next是第三个,.... 直到最后一个的next 可以为null 最后第一个的previous 是最后第二个,最后第二个的previous是最后第三个,.... 直到第一个的previous 可以为null; pa...
  • 第二个构造函数建立一个链接列表,该链接列表由类集c中的元素初始化。 除了它继承的方法之外,LinkedList类本身还定义了一些有用的方法,这些方法主要用于操作和访问列表。使用addFirst( )方法可以在列表头增加元素...
  • 这是第二个java中通用的数据结构 这和之前的 ArrayList 中的很多 接口有相同的… 如果这里没有提及…可以去 https://blog.csdn.net/weixin_46592754/article/details/105866191 看一下 本文… 快速导航LinkedList ...
  • 一、List集合常用子类:ArrayList、LinkedList ArrayList:底层数据结构是数组,查询快,增删慢 LinkedList:底层数据结构是链表,查询慢,增删快 ... public E getFirst():返回此列表中的元素 public E g

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 460
精华内容 184
关键字:

linkedlist第二个