数据结构与算法Java描述第二节LinkedList-链表
目录
【数据结构与算法】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();
}四、顺序表与链表的对比
顺序表 与 链表 的区别主要体现在 查询 与 插入删除 的时间效率上，因此它们两个的使用场景不一样。