跟我学java编程—掌握LinkedList的原理及应用

米粒教育

发布时间:18-04-2421:17

前面一节介绍了ArrayList,本节介绍LinkedList。LinkedList也是List接口的实现类,与ArrayList不同之处是采用的存储结构不同,ArrayList的数据结构为线性表,而LinkedList数据结构是链表。链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。

LinkedList是一个双向链表, 当数据量很大或者操作很频繁的情况下,添加和删除元素时具有比ArrayList更好的性能。但在元素的查询和修改方面要弱于ArrayList。LinkedList类每个结点用内部类Node表示,LinkedList通过first和last引用分别指向链表的第一个和最后一个元素,当链表为空时,first和last都为NULL值。LinkedList数据结构如下图所示:

图 14-11 LinkedList数据结构

LinkedList类内部的Node结点代码如下:

Node节点一共有三个属性:item代表节点值,prev代表节点的前一个节点,next代表节点的后一个节点。每个结点都有一个前驱和后继结点,并且在 LinkedList中也定义了两个变量分别指向链表中的第一个和最后一个结点。

transient Node<E> first;

transient Node<E> last;

1、添加元素到LinkedList

LinkedList提供了多个添加元素的方法:

boolean add(E e)

在链表尾部添加一个元素,如果成功,返回true,否则返回false。

void addFirst(E e)

在链表头部插入一个元素。

addLast(E e)

在链表尾部添加一个元素。

void add(int index, E element)

在指定位置插入一个元素。

添加元素到LinkedList示例代码如下:

代码通过add、addFirst、addLast方法加入元素,并通过println输出链表元素。输出结果如下图所示:

图 14-12 LinkedListAddDemo输出结果

2、从LinkedList中删除元素

LinkedList提供了多个删除元素的方法:

boolean remove(Object o)

从当前链表中移除指定的元素。

E remove(int index)

从当前链表中移除指定位置的元素。

E removeFirst()

从当前链表中移除第一个元素。

E removeLast()

从当前链表中移除最后一个元素。

E remove()

从当前链表中移除第一个元素,同removeLast()相同。

从LinkedList删除元素示例代码如下:

代码通过add方法加入元素,再通过remove、removeFirst、removeLast等方法移除元素,并通过println输出操作后的链表元素。输出结果如下图所示:

图 14-13 LinkedListRemoveDemo输出结

3、从LinkedList中获取元素

LinkedList提供了多个获取元素的方法:

E get(int index)

从当前链表中获取指定位置的元素。

E getFirst()

从当前链表中获取第一个元素。

E getLast()

从当前链表中获取最后一个元素。

从LinkedList获取元素示例代码如下:

代码通过add方法加入元素,再通过get、getFirst、getLast方法获取元素,并通过println输出操作后的链表元素。输出结果如下图所示:

图 14-14 LinkedListGetDemo输出结果

4、LinkedList的遍历方法

同前面介绍的集合类遍历方式一样,LinkedList可以通过迭代器、foreach语句、for循环语句等方法遍历集合的所有元素。

遍历LinkedList元素示例代码如下:

代码采用for循环、迭代器、foreach方式,遍历包含10万个元素的LinkedList,通过输出结果可以看出,foreach语句效率最高,其次是迭代器,效率最差的是for循环。输出结果如下图所示:

图 14-15 LinkedListTraverseDemo输出

■ 知识点拨

LinkedList存储元素的数据结构是双向链表结构,由存储元素的结点连接而成,每一个节点都包含前一个节点的引用,后一个节点的引用和节点存储的值。当一个新节点插入时,只需要修改其中保持先后关系的节点的引用即可。

返回顶部