【数据结构与算法】Java描述：第二节：LinkedList 链表

一、链表的概念与结构

1.1 概念：

通俗的来说，链表是由一个个结点连接起来的就叫链表。

1.2 结构：

链表存储的数据 在 物理上是不一定连续的，它是由前面链接后面，一个个连起来的。

二、Java底层的 LinkedList 

2.1 Java底层构成：

LinkedList 的底层是 双向链表结构， 由于链表没有将元素存储在连续的空间中，元素存储在单独的j结点中，然后通过引用将 结点 连接起来了。

因此在在任意位置 插入 或者 删除 元素时，不需要搬移元素，效率比较高。

LinkedList 中包含 LinkNode 类

从上图我们可以看到 每个结点都有三部分构成，

分别是数据  (elem)，结点的上一个 (prev)，结点的下一个(next)

2.2 链表的构造方法：

和顺序表类似，可以传入另一个链表 作为参数来创建新的链表

三、链表相关方法

3.1 链表中的方法：

3.2 链表的遍历

public static void main(String[] args) {LinkedList<Integer> linkedList2 = new LinkedList<>();linkedList2.add(1);//默认都是尾插linkedList2.addLast(3);linkedList2.addLast(4);linkedList2.addLast(5);System.out.println(linkedList2);//迭代器反向遍历System.out.println("===== ListIterator ====");ListIterator<Integer> lit2 =  linkedList2.listIterator(linkedList2.size());while (lit2.hasPrevious()) {System.out.print(lit2.previous()+" ");}System.out.println();//迭代器正向遍历，属于子类System.out.println("===== ListIterator ====");ListIterator<Integer> lit =  linkedList2.listIterator();while (lit.hasNext()) {System.out.print(lit.next()+" ");}System.out.println();//迭代器正向遍历System.out.println("===== Iterator ====");Iterator<Integer> it = linkedList2.iterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();//for each遍历System.out.println("=====for each====");for(Integer x : linkedList2) {System.out.print(x +" ");}System.out.println();//for循环遍历System.out.println("=====for====");for (int i = 0; i < linkedList2.size(); i++) {System.out.print(linkedList2.get(i) +" ");}System.out.println();}

四、顺序表与链表的对比

顺序表 与 链表 的区别主要体现在 查询 与 插入删除 的时间效率上，因此它们两个的使用场景不一样。