您的位置: 首页  >  文章  >  LinkedList和ArrayList简述

LinkedList和ArrayList简述

分类: 文章 • 2023-12-31 14:10:52

LinkedList和ArrayList简述
LinkedList和ArrayList简述

文章目录

1. ArrayList

1.指南

ArrayList继承自实现List接口的AbstractList类,该List接口继承自Collection和Iterable（可迭代接口）接口

1. ArrayList Features

  1. Ordered :
  2. Index based
  3. Dynamic resizing
  4. Non synchronized
  5. Duplicates allowed

2. Internal Working of ArrayList

ArrayList.java

public class ArrayList<E> extends AbstractList<E>  implements List<E>, RandomAccess,                    Cloneable, java.io.Serializable {  
    transient Object[] elementData;     //backing array 
    private int size;                   //array or list size  
    //more code
}

3. ArrayList Example

3.1 Create ArrayList

//Empty arrayList
List<String> names=new ArrayList<String>();

//ArrayList initialized with another collection
List<Integer> numbers=new ArrayList<>(Arrays.asList(1,2,3,4,5));

3.2 Add and remove Element

//Create arrayList
List<String> names=new ArrayList();

names.add("wang");   //[wang]
names.add("FEEL");   //[wang,FEEL]

names.set(1,"brain");   //[wang,brain]

names.remove(1);        //[wang]

3.3 Iterate

使用iterator()或者listIterator()获得迭代器实例的引用，这个迭代器可用来迭代arrayList中的元素.

Iterate arrayList

ArrayList<Integer> list=new ArrayList<>(Arrays.asList(1,2,3,4,5,6));

Iterator<Integer> it=list.iterator();

while(it.hasNext()){
    System.out.println(it.next());
}

程序输出：

Console

1
2
3
4
5
6

4. ArrayList Methods

  • add()
  • addAll()
  • clear()
  • clone()
  • contains()
  • forEach()
  • get()
  • indexOf()
  • listIterator()
  • remove
  • removeAll()
  • replaceAll()
  • sort()
  • subList()
  • toArray()

2. LinkedList

LinkedList类是List和Deque接口的双链表实现,它实现了所有的list操作.

1. Hierarchy

LinkedList类继承自AbstractSequentialList类并实现List和Deque接口,这里的E是Linkedlist存储值的类型.

LinkedList.java

public class LinkedList<E> extends AbstractSequentialList<E>
 	implements List<E>,Deque<E>,Cloneable,java.io.Serializable{
 		//implementation
 }

LinkedList和ArrayList简述

2. Features

  • 双链表的实现，实现了List和Deque接口。因此，它还可以被用作Queue,Deque，Stack。
  • 允许所有元素，包括复制和NULL
  • LinkedList维护元素的插入顺序
  • 它不是同步的，如果多个线程同时访问一个list，并且至少有一个线程修改list的结构，，则它必须从外部同步。
  • 使用Collections.synchronizedList(new LinkedList())得到一个同步（synchronized)的linkedlist。
  • 迭代器通过这个类返回时是fail-fast（快速失败)的，可能会产生异常：ConcurrentModificationException.
  • 它不实现RandomAccess接口，因此我们只能按顺序访问其中元素，不支持随机访问元素。
  • 可以使用ListIterator迭代遍历LinkedList元素

3. Constructors

  • LinkedList()：初始化一个空的LinkedList实现
  • LinkedListExample(Collection c):初始化包含指定集合元素的LinkedList

4. Methods

  • boolean add(Object o)
  • void add(int index,Object element)
  • void addFirst(Object o)
  • void addLast(Object o)
  • int size()
  • boolean contains(Object o)
  • boolean remove(Object o)
  • Object getFirst()
  • int indexOf(Object o)
  • Object[] toArray()
  • Iterator iterator()
  • List subList(int fromIndex,int toIndex)

5. Example

5.1 Add,remove,iterate

LinkedListExample examples

import java.util.*;

public class LinkedListExample{
    public static void main(String[] args) {
        LinkedList<String> linkedList=new LinkedList<>();

        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");

        System.out.println(linkedList);

        linkedList.add(4,"A");
        linkedList.add(5,"A");

        System.out.println(linkedList);

        linkedList.remove("A");  //removes A
        linkedList.remove(0);    //remove B

        System.out.println(linkedList);

        //Iterate
        ListIterator<String> it=linkedList.listIterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

输出结果：

[A, B, C, D]
[A, B, C, D, A, A]
[C, D, A, A]
C
D
A
A

5.2 Convert between Array and LinkedList

import java.util.*;

public class TestLinkedList{
    public static void main(String[] args) {
        LinkedList<String> linkedList=new LinkedList<>();

        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");

       // LinkedList to Array
       String[] array=new String[linkedList.size()];
       linkedList.toArray(array);
       System.out.println(Arrays.toString(array));

       //Array to LinkedList
       LinkedList<String> list=new LinkedList<>(Arrays.asList(array));
       System.out.println(list);

    }
}

输出结果:

[A, B, C, D]
[A, B, C, D]

5.3 How to sort LinkedList

  • Collections.sort()
  • Collections.sort(linkedList,comparator)
import java.util.*;

public class TestSort{
    public static void main(String[] args) {
        LinkedList<String> linkedList=new LinkedList<>();

        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");

       //unsorted
       System.out.println(linkedList);

       //Sort the list
       Collections.sort(linkedList);
       System.out.println(linkedList);

        //Custom sorting
        Collections.sort(linkedList,Collections.reverseOrder());
        System.out.println(linkedList);

    }
}

输出结果：

[A, B, C, D]
[A, B, C, D]
[D, C, B, A]

6. Usecases

  1. 在任何桌面应用程序，都可以将操作记录在linkeList中，并实现从上一次开始的Undo和Redo 函数。
  2. 浏览器的Next和Previous按钮可以使用LinkedList编程
  3. LinkedList（与HashTable配对)对于LRU缓存非常有用

7. Performance

  • add(E element):复杂度O(1)
  • add(E element)和add(int index,E element) :复杂度为O(n)
  • remove(int index): O(n)
  • Iterator.remove()????(1)
  • ListIterator.add(E element)：O(1)

8. ArrayList vs LinkedList

  • ArrayList是使用动态可调整数组的概念实现的，而LinkedList是一个双链表的实现
  • ArrayList允许随机访问元素，而LinkedList不支持
  • LinkedList实现了Queue接口，比ArrayList有更多的方法，比如：offer(),peek()等
  • 与LinkedList相比，ArrayList在add和remove操作时速度比较慢，但在get操作时更快，因为如果LinkedList中的数组满之后要拷贝内容到新数组，而对于可变大小数组ArrayList不需要.

9. Conclusion

通过上述,我们学习到了什么是LinkedList，以及LinkedList 和ArrayList之间的区别，以及如何创建LinkedList，如何添加,删除，和查询LinkedList中的元素以及遍历LinkedList。

相关推荐