精华内容
下载资源
问答
  • LinkedList:底层源码定义一个双向链表 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; ...

    LinkedList:底层源码定义一个双向链表
    private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
    }
    }
    定义了两种添加元素方式:
    1.在链表头部添加元素
    private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
    last = newNode;
    else
    f.prev = newNode;
    size++;
    modCount++;
    }
    2.在链表尾部添加元素:
    void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
    first = newNode;
    else
    l.next = newNode;
    size++;
    modCount++;
    }
    其中添加元素方法:add(),addFirst(),调用linkFirst()方法,直接在头部添加元素
    add(index,element),在指定位置添加元素,通过size锁定位置,然后在其前部添加
    push(),offerFrist()调用addFirst,模拟栈功能,在队头插入
    offer(),offerLast()调用addList,模拟队列功能,在队尾插入
    -----------------------------------------------------------------
    删除元素:源码定义了2中删除元素的方法:
    1.删除链表头部元素
    private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
    last = null;
    else
    next.prev = null;
    size--;
    modCount++;
    return element;
    }
    2.删除链表尾部元素
    private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
    first = null;
    else
    prev.next = null;
    size--;
    modCount++;
    return element;
    }
    其中删除元素的方法:
    remove()、removeFirst()、pop()、poll()、pollFirst()
    都是调用的unlinkFirst()方法
    removeList()、pollLast()都是调用unlinkLast的方法。


    push()和pop()是模拟栈存储。先进后出(FILO),在头部操作

    offer()和poll()是模拟队列存储,先进先出(FIFO),在尾部进队,头部出队操作

    offerFirst()、offerLast()和pollFirst()、pollLast()模拟双向队列,在尾部可以进队出队,在头部可以进队出队

    展开全文
  • ArrayList,LinkedList,Vector,CopyOnWriteArrayList对比 ArrayList,LinkedList,Vector,CopyOnWriteArrayList都是List接口的实现类,List接口是有序集合,可以精确的控制在那个位置插入元素,可以通过索引位置访问...

    ArrayList,LinkedList,Vector,CopyOnWriteArrayList对比

    ArrayList,LinkedList,Vector,CopyOnWriteArrayList都是List接口的实现类,List接口是有序集合,可以精确的控制在那个位置插入元素,可以通过索引位置访问元素。但是这几实现类的实现原理完全不同,分别介绍一下。

    结论

    ArrayList,LinkedList,Vector,CopyOnWriteArrayList都实现了List接口,通过上面的介绍,我们来比较一下,什么情况下用哪个类呢?

    • 不需要线程安全时

      可以选用ArrayList或LinkedList,当插入,删除操作多于查找操作时,采用LinkedList,反之采用ArrayList,尤其是随机查找比较多时,采用ArrayList。

    • 需要线程安全时

      可以选用Vector,CopyOnWriteArrayList,当插入,删除操作多与查找操作时两种均可以,反之建议采用CopyOnWriteArrayList。

    展开全文
  • package List_Interface;... * 1、有序,存入123 取出123 * 2、有索引 * 3、允许存储重复元素 * * public void add(int index,E element):将指定的元素,添加到集合的指定位置上 * public E get(int i
    package List_Interface;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /*
     * java.util.List接口继承了Collection接口
     * List接口的特点:
     * 1、有序,存入123 取出123
     * 2、有索引
     * 3、允许存储重复元素
     * 
     * public void add(int index,E element):将指定的元素,添加到集合的指定位置上
     * public E get(int index):返回集合中指定位置的元素
     * public E remove(int index):移除集合中指定位置的元素
     * public E set(int index,E element):替换集合中指定位置的元素,返回被替换的元素
     */
    public class List_Interface {
    	public static<E> void main(String[] args) {
    		//创建一个List集合
    		List<String> list = new ArrayList<>();
    		list.add("1");
    		list.add("2");
    		list.add("3");
    		list.add("4");
    		list.add("5");
    		System.out.println(list);
    		list.add(3,"3.5");//指定索引处添加元素
    		System.out.println(list);
    		String i =list.set(3,"3.6");//替换指定索引处的元素 并返回被替换的元素
    		System.out.println(list);
    		System.out.println(i);
    		/*
    		 * 遍历list可以 
    		 * 普通for循环 利用get方法
    		 * 迭代器 
    		 * 增强for
    		 */
    	}
    }
    //IndexOutOfBoundException: 索引越界异常 一般集合会报
    //ArrayIndexOutOfBoundException: 数组索引越界异常
    //StringIndexOutOfBoundException: 字符串索引越界异常
    
    package List_Interface;
    
    import java.util.LinkedList;
    
    /*
     * java.util.LinkedList集合implements List接口
     * LinkedList集合的特点:
     * 1:底层是一个链表结构,查询慢,增删快
     * 2:包含了大量操作首尾元素的方法
     * 注意:::必须使用LinkedList集合特有的方法,不能使用多态
     */
    public class _LinkedList {
    public static void main(String[] args) {
    	show01();
    	show02();
    }
    public static void show01() {
    	LinkedList<String> linkedlist = new LinkedList<>();
    	linkedlist.add("a");
    	linkedlist.add("b");
    	linkedlist.add("c");
    	System.out.println(linkedlist);
    	linkedlist.addFirst("www");//在集合的开头插入一个元素
    	System.out.println(linkedlist);
    	linkedlist.addLast(".com");
    	System.out.println(linkedlist);//在集合末尾添加一个元素
    	linkedlist.push("www");//等效于addFirst
    	System.out.println(linkedlist);
    }
    public static void show02() {
    	LinkedList<String> linkedlist = new LinkedList<>();
    	linkedlist.add("a");
    	linkedlist.add("b");
    	linkedlist.add("c");
    	String i =linkedlist.getFirst();//获取第一号数据
    	String k = linkedlist.getLast();//获取最后一号数据
    	System.out.println(i+","+k);
    	linkedlist.clear();// 清空集合中的元素
    	boolean o = linkedlist.isEmpty();//如果集合是空的  返回true
    	System.out.println(o);
    	
    	linkedlist.removeFirst();//移除第一个元素
    	linkedlist.removeLast();//移除最后一个元素  同理
    }
    }
    
    
    展开全文
  • LinkedList

    2020-12-03 00:09:01
    LinkedList 概述 以双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。 按下标访问元素—get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从...

    LinkedList

    概述

    以双向链表实现。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。

    按下标访问元素—get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起)。

    插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作—add(),addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动。

    原理

    参考博客:https://www.cnblogs.com/skywang12345/p/3308807.html#a3

    LinkedList实际上是通过双向链表去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低
    既然LinkedList是通过双向链表的,但是它也实现了List接口{也就是说,它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的,如何将“双向链表和索引值联系起来的”?实际原理非常简单,它就是通过一个计数索引值来实现的。例如,当我们调用get(int location)时,首先会比较“location”和“双向链表长度的1/2”;若前者大,则从链表头开始往后查找,直到location位置;否则,从链表末尾开始先前查找,直到location位置。这就是“双线链表和索引值联系起来”的方法。

    源码如下参看上面的博客。

    总结
    (01) LinkedList 实际上是通过双向链表去实现的.它包含一个非常重要的内部类:Entry。Entry是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值上一个节点下一个节点
    (02) 从LinkedList的实现方式中可以发现,它不存在LinkedList容量不足的问题。
    (03) LinkedList的克隆函数,即是将全部元素克隆到一个新的LinkedList对象中。
    (04) LinkedList实现java.io.Serializable。当写入到输出流时,先写入“容量”,再依次写入“每一个节点保护的值”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。
    (05) 由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。

    总结起来如下表格:

            第一个元素(头部)                 最后一个元素(尾部)
            抛出异常        特殊值            抛出异常        特殊值
    插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
    移除    removeFirst()  pollFirst()      removeLast()    pollLast()
    检查    getFirst()     peekFirst()      getLast()        peekLast()
    

    (06) LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下表的方法等价:

    [复制代码](javascript:void(0)😉

    队列方法       等效方法
    add(e)        addLast(e)
    offer(e)      offerLast(e)
    remove()      removeFirst()
    poll()        pollFirst()
    element()     getFirst()
    peek()        peekFirst()
    

    [复制代码](javascript:void(0)😉

    (07) LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:

    栈方法        等效方法
    push(e)      addFirst(e)
    pop()        removeFirst()
    peek()       peekFirst()
    

    set和get函数

    public E set(int index, E element) { 
    checkElementIndex(index); 
    Node<E> x = node(index); 
    E oldVal = x.item; 
    x.item = element; 
    return oldVal; 
    }
    
    public E get(int index) { 
    checkElementIndex(index); 
    return node(index).item; 
    } 
    

    这两个函数都调用了 node 函数,该函数会以O(n/2)的性能去获取一个节点,具体实现如下所示:

    Node<E> node(int index) { 
    // assert isElementIndex(index); 
    if (index < (size >> 1)) { 
    Node<E> x = first; 
    for (int i = 0; i < index; i++) 
    x = x.next; 
    return x; 
    } else { 
    Node<E> x = last; 
    for (int i = size - 1; i > index; i--) 
    x = x.prev; 
    return x; 
    } 
    } 
    

    就是判断index是在前半区间还是后半区间,如果在前半区间就从head搜索,而在后半区间就从tail搜索。而不是一直从头到尾的搜索。如此设计,将节点访问的复杂度由O(n)变为O(n/2).

    遍历方式

    (01) 通过迭代器遍历。即通过Iterator去遍历。

    for(Iterator iter = list.iterator(); iter.hasNext();)
        iter.next();
    

    (02) 通过快速随机访问遍历LinkedList

    int size = list.size();
    for (int i=0; i<size; i++) {
        list.get(i);        
    }
    

    (03) 通过另外一种for循环来遍历LinkedList

    for (Integer integ:list) 
        ;
    

    (04) 通过**pollFirst()**来遍历LinkedList

    while(list.pollFirst() != null)
        ;
    

    (05) 通过**pollLast()**来遍历LinkedList

    while(list.pollLast() != null)
        ;
    

    (06) 通过**removeFirst()**来遍历LinkedList

    try {
        while(list.removeFirst() != null)
            ;
    } catch (NoSuchElementException e) {
    }
    

    (07) 通过**removeLast()**来遍历LinkedList

    try {
        while(list.removeLast() != null)
            ;
    } catch (NoSuchElementException e) {
    }
    ) {
    }
    

    (07) 通过**removeLast()**来遍历LinkedList

    try {
        while(list.removeLast() != null)
            ;
    } catch (NoSuchElementException e) {
    }
    
    展开全文
  • 做这个实验之前,我的猜想的是:因为每次都是在尾部插入数据,而LinkedLiist里面有一个last指针一直指向最后一个元素,而ArrayList则根据索引来找到最后一个元素,那么,这两个方式中,效率应该是差不多的;...
  • 文章目录背景ArrayListLinkedList实例分析1、增加数据2、插入数据3、遍历数据3.1、LinkedList遍历改进总结 背景 ArrayList与LinkedList是Java编程中经常会用到的两种基本数据结构,在书本上一般会说明以下两个特点:...
  • //Hashtable:数据查找快 public class hanjia{ public static void main(String[] args){ long total=0;//记录时间 long call=0;//记录时刻 Hashtable table=new Hashtable(); Li...
  • 编写一个应用程序,要求将LinkedList创建的对象写入文件,在读出一个LinkedList节点中的数据。 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; ...
  • java代码-定义一个学生类,使用LinkedList对学生类进行管理,执行添加操作,并打印数据
  • ArrayList实际上是一个可变长的数组;LinkedList则是由相互引用的节点组成的双向链表。
  • LinkedList 特点 有序,但内存空间中可能比较分散; 存储相对较快、获取相对较慢; 线程不安全。 LinkedList 继承/实现 继承 AbstractSequentialList: 线性序列结构的抽象,继承于 AbstractList; 抽象方法 ...
  • 1 LinkedList介绍LinkedList简介LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList实现List接口,能对它进行队列操作。LinkedList实现Deque接口,...
  • Created with Raphaël 2.2.0开始array 数组arraylist 动态数组list 列表queue 队列stack 堆栈linkedlist 链表hashtable 哈希表dictionary 字典hashset 哈希集sortedset 排序集结束 1.1 ArrayList ArrayList 是一个...
  • java基础之LinkedList

    2021-02-26 13:42:56
    我是个木得感情的更新机器LinkedList的属性:// 链表的表头,表头无数据。Entry是个链表类数据结构,详细明细请看后面。private transient Entry header = new Entry(null, null, null);// LinkedList中元素个数...
  • Java学习笔记之LinkedList基本用法

    千次阅读 2018-05-21 11:06:49
    LinkedList简介LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList 实现 List 接口,能进行队列操作。LinkedList 实现 Deque 接口,即能将...
  • LinkedList详解

    2019-02-21 21:22:43
    LinkedList是双向链表结构,链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。 LinkedList继承了AbstractSequentialList&lt;E&gt;,实现了List&lt;...
  • C#LinkedList链表

    千次阅读 2020-02-03 15:41:51
    链表在很多语言中都有介绍,它是一种链状的数据结构。它本身带有的节点可以指向下一个或上一个节点,从而可实现轮询。 二、链表的优缺点 优点: 一般数组都是需要一连串的内存空间来存储数据,但是链表结构不需要...
  • LinkedList介绍

    2020-05-25 17:57:44
    LinkedList继承关系 LinkedList简介 1.LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用。 2.LinkedList实现List接口,能让它进行队列操作。 3.LinkedList...
  • LinkedList深度解析

    2020-04-24 19:21:30
    LinkedList 深入解析1. LinkedList 基础介绍1.1 重要的私有属性和构造器1.11私有变量1.12 无参构造器1.13 有参构造器1.2 Node Helper类 LinkedList类的精华二级目录 1. LinkedList 基础介绍 1.1 重要的私有属性和...
  • LinkedList简单介绍是一个继承于AbstractSequentialList的双向链表。它可以被当成堆栈、队列或双端队列进行操作。实现了List接口,能对它进行队列操作。实现了Deque接口,能当作双端队列使用。实现了Cloneable接口...
  • 由于LinkedList底层数据结构链表节点没有索引,但是节点是由顺序的,且是双向顺序 // 所以LinkedList内部将头节点视为索引0,尾节点视为索引size-1,中间按顺序一次索引加1 // 2.内部如何查找索引位置,由于链表维护...
  • Java LinkedList

    2017-11-16 14:32:54
    public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable { // 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。 private t
  • Java类LinkedList常用API详解

    千次阅读 2020-07-25 08:39:28
    LinkedList - 测试类 package LinkedList_UtilityClass; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; import java.util.ListIterator; /** * LinkedList测试类 */ ...
  • ArrayList底层实现原理 ...线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表有两种存储方式: 一种是顺序存储结构 另一种是链式存储结构 数
  • 1.数据结构-链表链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。使用链表结构可以克服数组链表需要预先知道数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,346
精华内容 15,338
关键字:

linkedlist存入数据