400-616-5551

您所在位置: 首页> 学习课程> Java零基础手把手系列:LinkedList基础入门

Java零基础手把手系列:LinkedList基础入门

发布百知教育 来源:学习课程 2019-09-05

目录

1. 概述2. 特性3. LinkedList vs ArrayList3.1 底层实现结构3.2 基本操作3.3 内存占用4. 基本用法4.1 Create LinkedList(同步和非同步)4.2 添加元素4.3 删除元素4.4 队列操作5. 总结

1. 概述

源码里面的注释说:LinkedList一种双向链表的实现,实现了接口List和Deque(Java零基础手把手系列:Queue最简入门),它实现了所有链表的操作,可以存储任何元素,包括null。

/**
 * Doubly-linked list implementation of the {@code List} and {@code Deque}
 * interfaces.  Implements all optional list operations, and permits all
 * elements (including {@code null}).
 ...
 **/

本文将讲述该数据结构的基本类型和方法,并举例说明其简单的应用。

2. 特性

我们先来看一下LinkedList的一些基本特性:

  • 它的内部数据结构是一个叫Node的节点:


2.png


  • 通过index获取元素很慢,因为需要从头到尾的遍历(虽然源码里面有加速实现:如果index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找)

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
    * Returns the (non-null) Node at the specified element index.
    */

   Node<E> node(int index) {
       // assert isElementIndex(index);
       //如果index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查
       if (index < (size >> 1)) {
           //因为头部复制给x
           Node<E> x = first;
           //所以从0 遍历到 index - 1
           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;
       }
   }


  • 不是同步的,不是线程安全的

  • 它的Iterator和ListIterator迭代器是fail-fast的(什么意思呢,指的是在获取到迭代器之后,如果修改了列表,将抛出一个ConcurrentModificationException)

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}


  • 每一个元素都是一个Node节点,该节点保存了前一个元素、后一个元素的引用

  • LinkedList维持插入的顺序

3. LinkedList vs ArrayList

虽然两者都是List接口的实现类,但是还是有自己的特点,不同的特点决定了什么样的场景该使用哪一个

3.1 底层实现结构

ArrayList查询快

  • ArrayList的底层数据结构是数组,可以通过index随机获取元素,且时间复杂度是O(1)

  • LinkedList底层数据结构是链表,也就是每一个元素都会保存他的前一个,后一个元素的引用。因此,在LinkedList上面的查询操作是O(n)


3.png


3.2 基本操作

插入、添加、删除操作LinkedList比ArrayList快

  • LinkedList做上述操作的时候,只需要改变其previous和next指针的引用即可

  • ArrayList做上述操作,需要resize或者update index

3.3 内存占用

ArrayList更省内存

  • ArrayList每一个元素只需要保存它的data和index

  • LinkedList每一个元素除了data,还有previous和next引用

4. 基本用法

本小节展示LinkedList的基本使用

4.1 Create LinkedList(同步和非同步)

默认的创建如下:

LinkedList<String> linkedList = new LinkedList<>();

虽然LinkedList不是线程安全的,但是我们可以通过调用Collections.synchronizedList方法创建它的同步版本:

List list = Collections.synchronizedList(new LinkedList(...));

4.2 添加元素

LinkedList实现了List和Deque,所以:

  • add:添加元素到链表尾部

  • addAll:添加指定的一堆元素到链表尾部

  • addFirst:添加元素到链表头部

  • addLast:添加元素到链表尾部

4.3 删除元素

和添加一样,提供removeFirst和removeLast,这里不解释了,特别介绍一下:

  • removeFirstOccurence(Object o):删除第一次出现的元素o,也就是从头到头的遍历,直到发现第一个。如果操作成功返回true

  • removeLastOccurence(Object o):同First的操作,删除最后一次出现的元素o

4.4 队列操作

Deque接口提供Queue的行为(参考文章:4.Java零基础手把手系列:ArrayDeque简洁却不简单入门):

//检索第一个元素
linkedList.poll();
//出队一个元素
linkedList.pop();
//入队一个元素o
linkedList.push(Object o);

poll()和pop()的区别是当列表为空时,pop就会抛出NoSuchElementException()异常,而poll则会返回null。
push将在列表头添加一个元素。

LinkedList还有许多其他操作,使用方式与List和Deque一样,有不懂的可以讨论。

5. 总结

一般情况下,如果使用到List,都会选择ArrayList
但是在有些使用情况下,使用LinkedList会是更好的选择,比如需要频繁的插入,删除,更新列表元素时。


注释:内容来自微信公众号写bug咯,版权归原作者所有。

上一篇:那些留在深圳工作的IT程序员,过得怎么样?

下一篇:应届生去公司找个Java程序员的职位需要什么技能?

相关推荐

关闭

立即申请

www.baizhiedu.com