LinkedList和ArrayList简述

墨蓝 2022-01-30 03:31 224阅读 0赞

![在这里插入图片描述][20190517213917284.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]

### 文章目录 ###

*   *  1. ArrayList
     *   *  1.指南
         *  1. ArrayList Features
         *  2. Internal Working of ArrayList
         *  3. ArrayList Example
         *   *  3.1 Create ArrayList
             *  3.2 Add and remove Element
             *  3.3 Iterate
         *  4. ArrayList Methods
     *  2. LinkedList
     *   *  1. Hierarchy
         *  2. Features
         *  3. Constructors
         *  4. Methods
         *  5. Example
         *   *  5.1 Add,remove,iterate
             *  5.2 Convert between Array and LinkedList
             *  5.3 How to sort LinkedList
         *  6. Usecases
         *  7. Performance
         *  8. ArrayList vs LinkedList
         *  9. Conclusion

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

![img][]

### 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`。

[20190517213917284.png]: /images/20220130/0b26e792f6b24d6da1263d1c36da943c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzOTAyNQ_size_16_color_FFFFFF_t_70]: /images/20220130/65b0af32ab0e46c399ec6883a0dd702f.png
[img]: https://cdn2.howtodoinjava.com/wp-content/uploads/2018/10/LinkedList-Hierarchy.png