精华内容
参与话题
问答
  • 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();
        }
    }
    
    展开全文
  • Linkedlist详解

    千次阅读 2018-05-27 00:17:32
    概述LinkedList 是 Java 集合中比较常用的数据结构,与 ArrayList 一样,实现了 List 接口,只不过 ArrayList 是基于数组实现的,而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList...

    一.  概述

    LinkedList 是 Java 集合中比较常用的数据结构,与 ArrayList 一样,实现了 List 接口,只不过 ArrayList 是基于数组实现的,而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList,而随机访问上则 ArrayList 性能更好。
    除了 LIst 接口之外,LinkedList 还实现了 Deque,Cloneable,Serializable 三个接口。这说明该数据结构支持队列,克隆和序列化操作的。与 ArrayList 一样,允许 null 元素的存在,且是不支持多线程的。

    二.  源码解读

    属性

    LinkedList 提供了以下三个成员变量。size,first,last。

     transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    其中 size 为 LinkedList 的大小,first 和 last 分别为链表的头结点和尾节点。Node 为节点对象。

    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;
       }
    }

    Node 是 LInkedList 的内部类,定义了存储的数据元素,前一个节点和后一个节点,典型的双链表结构。

    构造方法

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

    LinkedList 提供了两个构造方法:LinkedList() 和 LinkedList(Collection<? extends E> c)
    LinkedList() 仅仅构造一个空的列表,没有任何元素。size = 0。first 和 last 都为 null。
    后一个构造方法构造一个包含指定 Collection 中所有元素的列表,该构造方法首先会调用空的构造方法,然后通过 addAll() 的方式把 Collection 中的所有元素添加进去。

    • 调用 addAll() 方法,传入当前的节点个数 size,此时 size 为

    • 检查 index 是否越界

    • 将 collection 转换成数组

    • 遍历数组,将数组里面的元素创建为节点,并按照顺序连起来。

    • 修改当前的节点个数 size 的值

    • 操作次数 modCount 自增 1.

    public boolean addAll(Collection<? extends E> c) {
       return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
       checkPositionIndex(index);
       Object[] a = c.toArray();
       int numNew = a.length;
       if (numNew == 0)
           return false;
       Node<E> pred, succ;
       if (index == size) {
           succ = null;
           pred = last;
       } else {
           succ = node(index);
           pred = succ.prev;
       }
       for (Object o : a) {
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred, e, null);
           if (pred == null)
               first = newNode;
           else
               pred.next = newNode;
           pred = newNode;
       }
       if (succ == null) {
           last = pred;
       } else {
           pred.next = succ;
           succ.prev = pred;
       }
       size += numNew;
       modCount++;
       return true;
    }

    add 操作

    添加元素到链表末尾

    public boolean add(E e) {
       linkLast(e);
       return true;
    }
    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 方法直接调用了 linkLast 方法,而 linkLast 方法是不对外开放的。该方法做了三件事情,新增一个节点,改变其前后引用,将 size 和 modCount 自增 1。其中 modCount 是记录对集合操作的次数。
    在指定的位置插入元素

    public void add(int index, E element) {
       checkPositionIndex(index);
       if (index == size)
           linkLast(element);
       else
           linkBefore(element, node(index));
    }
    private void checkPositionIndex(int index) {
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
       return index >= 0 && index <= size;
    }
    void linkBefore(E e, Node<E> succ) {
       // assert succ != null;
       final Node<E> pred = succ.prev;
       final Node<E> newNode = new Node<>(pred, e, succ);
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
           pred.next = newNode;
       size++;
       modCount++;
    }

    首先检查下标是否越界,然后判断如果 index == size 则添加到末尾,否则将该元素插入的 index 的位置。其中 node(index) 是获取 index 位置的节点,linkBefore 负责把元素 e 插入到 succ 之前。

    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;
       }
    }

    可以看出 node() 方法这里写的还是挺赞的,不是傻乎乎的从头到尾或者从尾到头遍历链表,而是将 index 与 当前链表的一半做对比,比一半小从头遍历,比一半大从后遍历。对于数据量很大时能省下不少时间。

    get 操作

    很简单,首先获取节点,然后返回节点的数据即可。

    public E get(int index) {
       checkElementIndex(index);
       return node(index).item;
    }

    remove 操作

    移除指定位置的元素

    public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
    }
    E unlink(Node<E> x) {
       // assert x != null;
       final E element = x.item;
       final Node<E> next = x.next;
       final Node<E> prev = x.prev;
       if (prev == null) {
           first = next; // 如果移除的是头节点,那么头结点后移
       } else {
           prev.next = next;
           x.prev = null;  // 释放节点的前一个元素
       }
       if (next == null) {
           last = prev; // 如果移除的是尾节点,尾结点前移
       } else {
           next.prev = prev;
           x.next = null;  // 释放节点的后一个元素
       }
       x.item = null; // 释放节点数据
       size--;
       modCount++;
       return element;
    }

    先检查下标是否越界,然后调用 unlink 释放节点。
    移除指定元素

    public boolean remove(Object o) {
       if (o == null) {
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) {
                   unlink(x);
                   return true;
               }
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item)) {
                   unlink(x);
                   return true;
               }
           }
       }
       return false;
    }

    判断要移除的元素是否为 null,然后在遍历链表,找到钙元素第一次出现的位置,移除并返回 true。
    像其他的常用方法如:getFirst, getLast, removeFirst, removeLast, addFirst, addLast 等都很简单,扫一眼源码就能懂,我这里就不写了。

    迭代器

    LInkedList 的 iterator() 方法是在其父类 AbstractSequentialList 中定义的,最终一路 debug 到 LinkedList 类这里。其中 index 为 零。

    public ListIterator<E> listIterator(int index) {
       checkPositionIndex(index);
       return new ListItr(index);
    }

    我们来看看 ListItr。

    private Node<E> lastReturned;
       private Node<E> next;
       private int nextIndex;
       private int expectedModCount = modCount;
       ListItr(int index) {
           // assert isPositionIndex(index);
           next = (index == size) ? null : node(index);
           nextIndex = index;
       }
       public boolean hasNext() {
           return nextIndex < size;
       }
       public E next() {
           checkForComodification();
           if (!hasNext())
               throw new NoSuchElementException();
           lastReturned = next;
           next = next.next;
           nextIndex++;
           return lastReturned.item;
       }
        final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }
    }

    篇幅有限 ,我就只贴主要代码了。由源码可以看出初始化 ListItr 时,将 nextIndex 指向 index, 也就是零。如果该集合为空,那么 index == size 为 true,next 指向  null,否则 next 指向下标为零的元素,也就是第一个。
    hasNext 直接返回 nextIndex < size 简单明了。下面看看 next 方法,首先检查 expectedModCount 与 modCount 是否相等,看似无关紧要的代码保证了集合在迭代过程中不被修改[包括新增删除节点等]。然后将 lastReturned 指向 next,next 后移一个节点,nextIndex 自增 1,并返回 lastReturned 节点的元素。

    总结

    1、从源码可以看出 LinkedList 是基于链表实现的。如下图:


    这里写图片描述

    2、在查找和删除某元素时,区分该元素为 null和不为 null 两种情况来处理,LinkedList 中允许元素为 null。

    3、基于链表实现不存在扩容问题。

    4、查找时先判断该节点位于前半部分还是后半部分,加快了速度

    5、因为基于链表,所以插入删除极快,查找比较慢。

    6、实现了栈和队列的相关方法,所以可作为栈,队列,双端队列来用。



     如下代码
    10. public Object m() {
    11. Object o = new Float(3.14F);
    12. Object [] oa = new Object[1];
    13. oa[0] = o;
    14. o = null;
    15. oa[0] = null;
    16. print 'return 0';
    17. }
    Float对象在第11行被创建后, 什么时候能够被垃圾回收?   C
    A. 13行以后.
    B. 14行以后.
    C. 15行以后.
    D. 16行以后.


    垃圾回收器的基本原理是什么?垃圾回收器可以马上回收内存吗?有什么办法主动通知虚拟机进行垃圾回收

    对于GC来说,当程序员创建对象时,GC就开始监控这个对象的地址、大小以及使用情况。通常,GC采用有向图的方式记录和管理堆(heap)中的所有对象。通过这种方式确定哪些对象是"可达的",哪些对象是"不可达的"。当GC确定一些对象为"不可达"时,GC就有责任回收这些内存空间。可以。程序员可以手动执行System.gc(),通知GC运行,但是Java语言规范并不保证GC一定会执行。


     说出ArrayList,Vector, LinkedList的存储性能和特性.
    答案:ArrayListVector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector由于使用了synchronized方法(线程安全),通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。



    作者:coderlmm
    链接:https://juejin.im/post/5a90c2fd6fb9a06361089023


    展开全文
  • Java LinkedList基本用法

    万次阅读 多人点赞 2014-12-01 22:03:20
    LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用. LinkedList的构造函数如下 1. public LinkedList(): ——生成空的链表 2. public LinkedList(Collection col): 复制构造函数 1、...
    LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.
    LinkedList的构造函数如下
    1. public LinkedList():  ——生成空的链表
    2. public LinkedList(Collection col):  复制构造函数
    1、获取链表的第一个和最后一个元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2.   
    3. public class LinkedListTest{  
    4.   public static void main(String[] args) {  
    5.     LinkedList<String> lList = new LinkedList<String>();  
    6.     lList.add("1");  
    7.     lList.add("2");  
    8.     lList.add("3");  
    9.     lList.add("4");  
    10.     lList.add("5");  
    11.   
    12.   
    13.     System.out.println("链表的第一个元素是 : " + lList.getFirst());  
    14.     System.out.println("链表最后一个元素是 : " + lList.getLast());  
    15.   }  
    16. }  

    2、获取链表元素  
    [java] view plaincopy
    1. for (String str: lList) {  
    2.       System.out.println(str);  
    3.     }  
    3、从链表生成子表
    [java] view plaincopy
    1. List subl = lList.subList(14);  
    2.     System.out.println(subl);  
    3.     lst.remove(2);  
    4.     System.out.println(lst);  
    5.     System.out.println(lList);  
    4、添加元素:添加单个元素
     如果不指定索引的话,元素将被添加到链表的最后.
    public boolean add(Object element)
    public boolean add(int index, Object element)
    也可以把链表当初栈或者队列来处理:
    public boolean addFirst(Object element)
    public boolean addLast(Object element)
    addLast()方法和不带索引的add()方法实现的效果一样.
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2.   
    3. public class LinkedListTest{  
    4.   public static void main(String[] a) {  
    5.     LinkedList list = new LinkedList();  
    6.     list.add("A");  
    7.     list.add("B");  
    8.     list.add("C");  
    9.     list.add("D");  
    10.     list.addFirst("X");  
    11.     list.addLast("Z");  
    12.     System.out.println(list);  
    13.   }  
    14. }  
    5、删除元素
    [java] view plaincopy
    1. public Object removeFirst()  
    2. public Object removeLast()  
    3. import java.util.LinkedList;  
    4.   
    5.   
    6. public class MainClass {  
    7.   public static void main(String[] a) {  
    8.   
    9.   
    10.     LinkedList list = new LinkedList();  
    11.     list.add("A");  
    12.     list.add("B");  
    13.     list.add("C");  
    14.     list.add("D");  
    15.     list.removeFirst();  
    16.     list.removeLast();  
    17.     System.out.println(list);  
    18.   }  
    19. }  
    6、使用链表实现栈效果
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class MainClass {  
    3.   public static void main(String[] args) {  
    4.     StackL stack = new StackL();  
    5.     for (int i = 0; i < 10; i++)  
    6.       stack.push(i);  
    7.     System.out.println(stack.top());  
    8.     System.out.println(stack.top());  
    9.     System.out.println(stack.pop());  
    10.     System.out.println(stack.pop());  
    11.     System.out.println(stack.pop());  
    12.   }  
    13. }  
    14. class StackL {  
    15.   private LinkedList list = new LinkedList();  
    16.   public void push(Object v) {  
    17.     list.addFirst(v);  
    18.   }  
    19.   public Object top() {  
    20.     return list.getFirst();  
    21.   }  
    22.   public Object pop() {  
    23.     return list.removeFirst();  
    24.   }  
    25. }  
    7、使用链表来实现队列效果
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class MainClass {  
    3.   public static void main(String[] args) {  
    4.     Queue queue = new Queue();  
    5.     for (int i = 0; i < 10; i++)  
    6.       queue.put(Integer.toString(i));  
    7.     while (!queue.isEmpty())  
    8.       System.out.println(queue.get());  
    9.   }  
    10. }  
    11. class Queue {  
    12.   private LinkedList list = new LinkedList();  
    13.   public void put(Object v) {  
    14.     list.addFirst(v);  
    15.   }  
    16.   public Object get() {  
    17.     return list.removeLast();  
    18.   }  
    19.   public boolean isEmpty() {  
    20.     return list.isEmpty();  
    21.   }  
    22. }  

    8、将LinkedList转换成ArrayList

    [java] view plaincopy
    1. ArrayList<String> arrayList = new ArrayList<String>(linkedList);  
    2.     for (String s : arrayList) {  
    3.       System.out.println("s = " + s);  
    4.     }  

    9、删掉所有元素:清空LinkedList
        lList.clear();
    10、删除列表的首位元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class Main {  
    3.   public static void main(String[] args) {  
    4.     LinkedList<String> lList = new LinkedList<String>();  
    5.     lList.add("1");  
    6.     lList.add("2");  
    7.     lList.add("3");  
    8.     lList.add("4");  
    9.     lList.add("5");  
    10.     System.out.println(lList);  
    11.         //元素在删除的时候,仍然可以获取到元素  
    12.     Object object = lList.removeFirst();  
    13.     System.out.println(object + " has been removed");  
    14.     System.out.println(lList);  
    15.     object = lList.removeLast();  
    16.     System.out.println(object + " has been removed");  
    17.     System.out.println(lList);  
    18.   }  
    19. }  
    11、根据范围删除列表元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class Main {  
    3.   public static void main(String[] args) {  
    4.     LinkedList<String> lList = new LinkedList<String>();  
    5.     lList.add("1");  
    6.     lList.add("2");  
    7.     lList.add("3");  
    8.     lList.add("4");  
    9.     lList.add("5");  
    10.     System.out.println(lList);  
    11.     lList.subList(25).clear();  
    12.     System.out.println(lList);  
    13.   }  
    14. }  
    12、删除链表的特定元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class Main {  
    3.   public static void main(String[] args) {  
    4.     LinkedList<String> lList = new LinkedList<String>();  
    5.     lList.add("1");  
    6.     lList.add("2");  
    7.     lList.add("3");  
    8.     lList.add("4");  
    9.     lList.add("5");  
    10.     System.out.println(lList);  
    11.     System.out.println(lList.remove("2"));//删除元素值=2的元素  
    12.     System.out.println(lList);  
    13.     Object obj = lList.remove(2);  //删除第二个元素  
    14.     System.out.println(obj + " 已经从链表删除");  
    15.     System.out.println(lList);  
    16.   }  
    17. }  
    13、将LinkedList转换为数组,数组长度为0
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. import java.util.List;  
    3. public class Main {  
    4.   public static void main(String[] args) {  
    5.     List<String> theList = new LinkedList<String>();  
    6.     theList.add("A");  
    7.     theList.add("B");  
    8.     theList.add("C");  
    9.     theList.add("D");  
    10.     String[] my = theList.toArray(new String[0]);  
    11.     for (int i = 0; i < my.length; i++) {  
    12.       System.out.println(my[i]);  
    13.     }  
    14.   }  
    15. }  
    14、将LinkedList转换为数组,数组长度为链表长度
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. import java.util.List;  
    3. public class Main {  
    4.   public static void main(String[] args) {  
    5.     List<String> theList = new LinkedList<String>();  
    6.     theList.add("A");  
    7.     theList.add("B");  
    8.     theList.add("C");  
    9.     theList.add("D");  
    10.     String[] my = theList.toArray(new String[theList.size()]);  
    11.     for (int i = 0; i < my.length; i++) {  
    12.       System.out.println(my[i]);  
    13.     }  
    14.   }  
    15. }  
    15、将LinkedList转换成ArrayList
    [java] view plaincopy
    1. import java.util.ArrayList;  
    2. import java.util.LinkedList;  
    3. import java.util.List;  
    4. public class Main {  
    5.   public static void main(String[] args) {  
    6.     LinkedList<String> myQueue = new LinkedList<String>();  
    7.     myQueue.add("A");  
    8.     myQueue.add("B");  
    9.     myQueue.add("C");  
    10.     myQueue.add("D");  
    11.     List<String> myList = new ArrayList<String>(myQueue);  
    12.     for (Object theFruit : myList)  
    13.       System.out.println(theFruit);  
    14.   }  
    15. }  
    16、实现栈
    [java] view plaincopy
    1. import java.util.Collections;  
    2. import java.util.LinkedList;  
    3. public class Main {  
    4.   public static void main(String[] argv) throws Exception {  
    5.     LinkedList stack = new LinkedList();  
    6.     Object object = "";  
    7.     stack.addFirst(object);  
    8.     Object o = stack.getFirst();  
    9.     stack = (LinkedList) Collections.synchronizedList(stack);  
    10.   }  
    11. }  
    17、实现队列
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. public class Main {  
    3.   public static void main(String[] argv) throws Exception {  
    4.     LinkedList queue = new LinkedList();  
    5.     Object object = "";  
    6.     // Add to end of queue  
    7.     queue.add(object);  
    8.     // Get head of queue  
    9.     Object o = queue.removeFirst();  
    10.   }  
    11. }  
    18 、同步方法
    [java] view plaincopy
    1. import java.util.Collections;  
    2. import java.util.LinkedList;  
    3. public class Main {  
    4.   public static void main(String[] argv) throws Exception {  
    5.     LinkedList queue = new LinkedList();  
    6.     Object object = "";  
    7.     queue.add(object);  
    8.     Object o = queue.removeFirst();  
    9.     queue = (LinkedList) Collections.synchronizedList(queue);  
    10.   }  
    11. }  
    19、查找元素位置
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2.   
    3. public class Main {  
    4.   public static void main(String[] args) {  
    5.     LinkedList<String> lList = new LinkedList<String>();  
    6.     lList.add("1");  
    7.     lList.add("2");  
    8.     lList.add("3");  
    9.     lList.add("4");  
    10.     lList.add("5");  
    11.     lList.add("2");  
    12.     System.out.println(lList.indexOf("2"));  
    13.     System.out.println(lList.lastIndexOf("2"));  
    14.   }  
    15. }  
    20、替换元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2.   
    3. public class Main {  
    4.   public static void main(String[] args) {  
    5.     LinkedList<String> lList = new LinkedList<String>();  
    6.     lList.add("1");  
    7.     lList.add("2");  
    8.     lList.add("3");  
    9.     lList.add("4");  
    10.     lList.add("5");  
    11.     System.out.println(lList);  
    12.     lList.set(3"Replaced");//使用set方法替换元素,方法的第一个参数是元素索引,后一个是替换值  
    13.     System.out.println(lList);  
    14.   }  
    15. }  
    21、链表添加对象
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2. class Address {  
    3.   private String name;  
    4.   private String street;  
    5.   private String city;  
    6.   private String state;  
    7.   private String code;  
    8.   Address(String n, String s, String c, String st, String cd) {  
    9.     name = n;  
    10.     street = s;  
    11.     city = c;  
    12.     state = st;  
    13.     code = cd;  
    14.   }  
    15.   public String toString() {  
    16.     return name + " " + street + " " + city + " " + state + " " + code;  
    17.   }  
    18. }  
    19.   
    20.   
    21. class MailList {  
    22.   public static void main(String args[]) {  
    23.     LinkedList<Address> ml = new LinkedList<Address>();  
    24.     ml.add(new Address("A""11 Ave""U""IL""11111"));  
    25.     ml.add(new Address("R""11 Lane""M""IL""22222"));  
    26.     ml.add(new Address("T""8 St""C""IL""33333"));  
    27.     for (Address element : ml)  
    28.       System.out.println(element + "\n");  
    29.   }  
    30. }  
    22、确认链表是否存在特定元素
    [java] view plaincopy
    1. import java.util.LinkedList;  
    2.   
    3.   
    4. public class Main {  
    5.   public static void main(String[] args) {  
    6.     LinkedList<String> lList = new LinkedList<String>();  
    7.     lList.add("1");  
    8.     lList.add("2");  
    9.     lList.add("3");  
    10.     lList.add("4");  
    11.     lList.add("5");  
    12.     if (lList.contains("4")) {  
    13.       System.out.println("LinkedList contains 4");  
    14.     } else {  
    15.       System.out.println("LinkedList does not contain 4");  
    16.     }  
    17.   }  
    18. }  
    23、根据链表元素生成对象数组
    [java] view plaincopy
    1. Object[] objArray = lList.toArray();  
    2. for (Object obj: objArray) {  
    3.    System.out.println(obj);  
    4. }  
    24、链表多线程
    [java] view plaincopy
    1. import java.util.Collections;  
    2. import java.util.LinkedList;  
    3. import java.util.List;  
    4. class PrepareProduction implements Runnable {  
    5.   private final List<String> queue;  
    6.   PrepareProduction(List<String> q) {  
    7.     queue = q;  
    8.   }  
    9.   public void run() {  
    10.     queue.add("1");  
    11.     queue.add("done");  
    12.   }  
    13. }  
    14. class DoProduction implements Runnable {  
    15.   private final List<String> queue;  
    16.   DoProduction(List<String> q) {  
    17.     queue = q;  
    18.   }  
    19.   public void run() {  
    20.     String value = queue.remove(0);  
    21.     while (!value.equals("*")) {  
    22.       System.out.println(value);  
    23.       value = queue.remove(0);  
    24.     }  
    25.   }  
    26. }  
    27. public class Main {  
    28.   public static void main(String[] args) throws Exception {  
    29.     List q = Collections.synchronizedList(new LinkedList<String>());  
    30.     Thread p1 = new Thread(new PrepareProduction(q));  
    31.     Thread c1 = new Thread(new DoProduction(q));  
    32.     p1.start();  
    33.     c1.start();  
    34.     p1.join();  
    35.     c1.join();  
    36.   }  
    37. }  
    25、优先级链表(来自JBOSS)
    [java] view plaincopy
    1. import java.util.ArrayList;  
    2. import java.util.LinkedList;  
    3. import java.util.List;  
    4. import java.util.ListIterator;  
    5. import java.util.NoSuchElementException;  
    6.   
    7.   
    8. public class BasicPriorityLinkedList {  
    9.   
    10.   
    11.   protected LinkedList[] linkedLists;  
    12.   protected int priorities;  
    13.   protected int size;  
    14.   
    15.   
    16.   public BasicPriorityLinkedList(int priorities) {  
    17.     this.priorities = priorities;  
    18.     initDeques();  
    19.   }  
    20.   public void addFirst(Object obj, int priority) {  
    21.     linkedLists[priority].addFirst(obj);  
    22.     size++;  
    23.   }  
    24.   public void addLast(Object obj, int priority) {  
    25.     linkedLists[priority].addLast(obj);  
    26.     size++;  
    27.   }  
    28.   public Object removeFirst() {  
    29.     Object obj = null;  
    30.     for (int i = priorities - 1; i >= 0; i--) {  
    31.       LinkedList ll = linkedLists[i];  
    32.       if (!ll.isEmpty()) {  
    33.         obj = ll.removeFirst();  
    34.         break;  
    35.       }  
    36.     }  
    37.     if (obj != null) {  
    38.       size--;  
    39.     }  
    40.     return obj;  
    41.   }  
    42.   public Object removeLast() {  
    43.     Object obj = null;  
    44.     for (int i = 0; i < priorities; i++) {  
    45.       LinkedList ll = linkedLists[i];  
    46.       if (!ll.isEmpty()) {  
    47.         obj = ll.removeLast();  
    48.       }  
    49.       if (obj != null) {  
    50.         break;  
    51.       }  
    52.     }  
    53.     if (obj != null) {  
    54.       size--;  
    55.     }  
    56.     return obj;  
    57.   }  
    58.   
    59.   
    60.   public Object peekFirst() {  
    61.     Object obj = null;  
    62.     for (int i = priorities - 1; i >= 0; i--) {  
    63.       LinkedList ll = linkedLists[i];  
    64.       if (!ll.isEmpty()) {  
    65.         obj = ll.getFirst();  
    66.       }  
    67.       if (obj != null) {  
    68.         break;  
    69.       }  
    70.     }  
    71.     return obj;  
    72.   }  
    73.   
    74.   
    75.   public List getAll() {  
    76.     List all = new ArrayList();  
    77.     for (int i = priorities - 1; i >= 0; i--) {  
    78.       LinkedList deque = linkedLists[i];  
    79.       all.addAll(deque);  
    80.     }  
    81.     return all;  
    82.   }  
    83.   
    84.   
    85.   public void clear() {  
    86.     initDeques();  
    87.   }  
    88.   
    89.   
    90.   public int size() {  
    91.     return size;  
    92.   }  
    93.   
    94.   
    95.   public boolean isEmpty() {  
    96.     return size == 0;  
    97.   }  
    98.   
    99.   
    100.   public ListIterator iterator() {  
    101.     return new PriorityLinkedListIterator(linkedLists);  
    102.   }  
    103.   
    104.   
    105.   protected void initDeques() {  
    106.     linkedLists = new LinkedList[priorities];  
    107.     for (int i = 0; i < priorities; i++) {  
    108.       linkedLists[i] = new LinkedList();  
    109.     }  
    110.     size = 0;  
    111.   }  
    112.   
    113.   
    114.   class PriorityLinkedListIterator implements ListIterator {  
    115.     private LinkedList[] lists;  
    116.     private int index;  
    117.     private ListIterator currentIter;  
    118.     PriorityLinkedListIterator(LinkedList[] lists) {  
    119.       this.lists = lists;  
    120.       index = lists.length - 1;  
    121.       currentIter = lists[index].listIterator();  
    122.     }  
    123.   
    124.   
    125.     public void add(Object arg0) {  
    126.       throw new UnsupportedOperationException();  
    127.     }  
    128.   
    129.   
    130.     public boolean hasNext() {  
    131.       if (currentIter.hasNext()) {  
    132.         return true;  
    133.       }  
    134.       while (index >= 0) {  
    135.         if (index == 0 || currentIter.hasNext()) {  
    136.           break;  
    137.         }  
    138.         index--;  
    139.         currentIter = lists[index].listIterator();  
    140.       }  
    141.       return currentIter.hasNext();  
    142.     }  
    143.   
    144.   
    145.     public boolean hasPrevious() {  
    146.       throw new UnsupportedOperationException();  
    147.     }  
    148.   
    149.   
    150.     public Object next() {  
    151.       if (!hasNext()) {  
    152.         throw new NoSuchElementException();  
    153.       }  
    154.       return currentIter.next();  
    155.     }  
    156.   
    157.   
    158.     public int nextIndex() {  
    159.       throw new UnsupportedOperationException();  
    160.     }  
    161.   
    162.   
    163.     public Object previous() {  
    164.       throw new UnsupportedOperationException();  
    165.     }  
    166.   
    167.   
    168.     public int previousIndex() {  
    169.       throw new UnsupportedOperationException();  
    170.     }  
    171.   
    172.   
    173.     public void remove() {  
    174.       currentIter.remove();  
    175.       size--;  
    176.     }  
    177.   
    178.   
    179.     public void set(Object obj) {  
    180.       throw new UnsupportedOperationException();  
    181.     }  
    182.   }  
    183.   
    184.   
    185. }  
    26、生成list的帮助类(来自google)
    [java] view plaincopy
    1. import java.util.ArrayList;  
    2. import java.util.Collections;  
    3. import java.util.LinkedList;  
    4. import java.util.List;  
    5. public class Lists {  
    6.   private Lists() { }  
    7.   public static <E> ArrayList<E> newArrayList() {  
    8.     return new ArrayList<E>();  
    9.   }  
    10.   public static <E> ArrayList<E> newArrayListWithCapacity(int initialCapacity) {  
    11.     return new ArrayList<E>(initialCapacity);  
    12.   }  
    13.   public static <E> ArrayList<E> newArrayList(E... elements) {  
    14.     ArrayList<E> set = newArrayList();  
    15.     Collections.addAll(set, elements);  
    16.     return set;  
    17.   }  
    18.   public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {  
    19.     ArrayList<E> list = newArrayList();  
    20.     for(E e : elements) {  
    21.       list.add(e);  
    22.     }  
    23.     return list;  
    24.   }  
    25.   public static <E> LinkedList<E> newLinkedList() {  
    26.     return new LinkedList<E>();  
    27.   }  
    28. }  
    展开全文
  • ArrayLists和LinkedList的区别

    千次阅读 2018-09-25 10:45:30
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 ,这里的所谓动态数组并不是那个“ 有多少元素就申请多少空间 ”的意思,通过查看源码,可以发现,这个动态数组是这样实现的,如果没...

    学习

    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。  ,这里的所谓动态数组并不是那个“ 有多少元素就申请多少空间 ”的意思,通过查看源码,可以发现,这个动态数组是这样实现的,如果没指定数组大小,则申请默认大小为10的数组,当元素个数增加,数组无法存储时,系统会另个申请一个长度为当前长度1.5倍的数组,然后,把之前的数据拷贝到新建的数组。

    - ---------------------------------------------------------------------

    2. 对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。,ArrayList是数组,所以,直接定位到相应位置取元素,LinkedLIst是链表,所以需要从前往后遍历。

    -----------------------------------------------------------------------

    3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。//正确,ArrayList的新增和删除就是数组的新增和删除,LinkedList与链表一致。

    -------------------------------------------------------------------------

    4. ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。,因为ArrayList空间的增长率为1.5倍,所以,最后很可能留下一部分空间是没有用到的,因此,会造成浪费的情况。对于LInkedList的话,由于每个节点都需要额外的指针,所以,你懂的。

     

    --------------------------

     

    展开全文
  • List的实现接口又有几个,一个是ArrayList,还有一个是LinkedList,还有Vector。这次我们就来看看这三个类的源码。 ArrayList ArrayList是我们在开发中最常用的数据存储容器,它的底层是通过数组来实现的。我们在...
  • 测试程序源代码如下:public static void main(String[] args) { Random rand=new Random(); ArrayList<String> arrayList = new ArrayList();... LinkedList<String> linkedList = new LinkedLis
  • 隶书
  • LinkedList&ArrayList内存分析

    千次阅读 2019-05-06 23:37:41
    jdk版本不同略微不一致。以下是jdk1.8源码 LlinkedList 为双向链表,每个节点包含prev、item、next transient int size = 0; /** * Pointer to first node. * Invariant: (first == null &... ...
  • ArrayList存储是基于对象数组,数组中数据是在物理地址中连续存放。...LinkedList存储是基于链表的数据结构,链表存储不是连续的,而是一个单元既保存数据又保存下一个数据的地址。get时需要从头到尾依次比对,所
  • 最近研究数据结构时想起一个有趣的底层问题:关于Linklist和ArrayList的性能问题。 考虑到Linklist的底层是链表结构实现,其存储时所使用的内存地址原理上是不必要连续的;而Arraylist是采用数组方式实现的,其存储...
  • Java 集合深入理解(11):LinkedList

    万次阅读 2016-10-20 20:15:34
    今天心情鱼肚白,来学学 LinkedList 吧! 日常开发中,保存一组数据使用的最多的就是 ArrayList, 其次就是 LinkedList 了。我们知道 ArrayList 是以数组实现的,遍历时很快,但是插入、删除时都需要移动后面的元素...
  • LinkedList浅析

    万次阅读 2018-08-27 10:29:39
    LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实现 Deque 接口,...
  • List之LinkedList源码实现

    千次阅读 热门讨论 2018-09-02 16:25:15
    LinkedList是基于链表实现的,所以先讲解一下什么是链表。链表原先是C/C++的概念,是一种线性的存储结构,意思是将要存储的数据存在一个存储单元里面,这个存储单元里面除了存放有待存储的数据以外,还存储有其下一...
  • java集合之LinkedList详解

    万次阅读 2018-09-15 15:54:20
    我们上一次说到List的ArrayList,我们这次去看下LinkedList---顾名思义是链表,链表的优点就不用说了吧,增删效率比较高(具体的朋友们上网看吧),先来看下LinkedList的整体构架:  首先我们看到了LinkedList...
  • /* List 接口的实现 AarryList : 底层实现: 可变数组实现的,内部 通过数组拷贝实现根据内容可变长 优点 : 根据索引查询效率高 缺点 :错增加删除时效率低,因为要通过数组拷贝实现 应用场景: 存储耽搁数据,有序...
  • LinkList

    2020-02-13 15:01:55
    for顺序遍历耗时 > iterator迭代器遍历耗时 > 通过removeFirst()或removeLast()遍历耗时 > forach顺序遍历耗时 = 通过pollFirst()或pollLast()来遍历耗时。 import java.util.ArrayList;...
  • LinkList详解

    万次阅读 2018-04-27 15:22:26
    一、源码解析1、 LinkedList类定义2、LinkedList数据结构原理3、私有属性4、构造方法5、元素添加add()及原理6、删除数据remove()7、数据获取get()8、数据复制clone()与toArray()9、遍历数据:Iterator()二、ListItr...
  • ArrayList和LinkedList区别及使用场景

    万次阅读 多人点赞 2018-09-07 18:51:40
    ArrayList和LinkedList区别及使用场景 1. LinkedList和ArrayList的差别主要来自于Array和LinkedList数据结构的不同。ArrayList是基于数组实现的,LinkedList是基于双链表实现的。另外LinkedList类不仅是List接口的...
  • LinkedList详解

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

    万次阅读 2019-05-05 16:07:45
    ArrayList 和 LinkedList 的区别 ArrayList基于动态数组实现的非线程安全的集合;LinkedList基于链表实现的非线程安全的集合。 对于随机index访问的get和set方法,一般ArrayList的速度要优于LinkedList。因为...
  • LinkedList基本用法

    万次阅读 多人点赞 2012-10-06 11:50:02
    LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用. LinkedList的构造函数如下 1. public LinkedList(): ——生成空的链表 2. public LinkedList(Collection col): 复制构造函数 1、...
  • 简述ArrayList、Vector与LinkedList的异同点  Collection类的继承图如下:   从图中可以看出,LinkedList与ArrayList、ArrayDeque这三者都实现了List接口.所有使用方式也很相似,主要区别在于因为实现方式的不同,...
  • JDK 1.8 LinkedList源码分析

    千次阅读 多人点赞 2017-01-16 12:07:20
    LinkedList是一个实现了List接口和Deque接口的双端链表。 有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。 LinkedList不是线程安全的,如果想使...
  • java中ArrayList 、LinkList区别

    万次阅读 多人点赞 2011-08-11 13:42:24
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。   2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。  3.对于新增和删除操作add和remove,
  • ArrayList和LinkedList对比

    2017-02-14 15:31:38
    1、ArrayList和LinkedList简介 2、ArrayList和LinkedList对比 3、List常见遍历方式性能比较
  • Java重要类之LinkList类详解

    万次阅读 2016-09-23 17:25:59
    一.LinkList概述 LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能进行队列操作。 LinkedList 实现Deque接口,即能将...
  • ArrayList和LinkedList的区别、优缺点以及应用场景

    万次阅读 多人点赞 2018-12-09 09:17:21
    ArrayList和LinkedList都是实现了List接口的容器类,用于存储一系列的对象引用。他们都可以对元素的增删改查进行操作,那么他们区别、优缺点应用场景都有哪些呢?我们通过源码和数据结构来说明一下 ArrayList和...
  • LinkedList源码解析(基于JDK1.8)

    千次阅读 多人点赞 2018-05-27 18:41:48
    LinkedList将做为双链表来实现,它本身实现了List接口和Deque接口,并且实现了所有可选的列表操作,并且允许包含所有元素(包括null)。 下图是LinkedList的UML图: 从图中我们可以看出: 继承了...
  • java集合框架05——ArrayList和LinkedList的区别

    万次阅读 多人点赞 2016-04-13 20:39:09
    前面已经学习完了List部分的源码,主要是ArrayList和LinkedList两部分内容,这一节主要总结下List部分的内容。 List概括 先来回顾一下List在Collection中的的框架图: 从图中我们可以看出: 1. List是一个接口,它...
  • Java 常见面试题之“Arraylist和Linkedlist的区别”

    万次阅读 多人点赞 2018-07-24 11:19:22
    Arraylist:底层是基于动态数组,根据下表随机访问数组元素的效率高,向数组尾部添加元素的效率高;但是,删除数组中的数据以及向数组中间添加数据效率低,因为需要移动数组。例如最坏的情况是删除第一个数组元素,...

空空如也

1 2 3 4 5 ... 20
收藏数 239,492
精华内容 95,796
关键字:

linkedlist