LinkedList 双向链表
目录
1、实现自己的双向链表 (不带头)
1.1、display、size、contains方法
1.2、头插法尾插法
1.3、任意位置插入一个节点
1.4、删除第一个值为key的节点
1.5、删除所有值为key的节点
1.6、清空结点
2、LinkedList
2.1、什么是LinkedList
2.2、LinkedList常用方法
2.3、LinkedList的遍历
3、ArrayList 和LinkedList区别
双向链表结构：
1、实现自己的双向链表 (不带头)
与单链表一样，先实现IList接口，再重写其中的所有方法
创建一个静态内部类ListNode，表示结点，结点中包含数据域、prev域和next域
1.1、display、size、contains方法
display、size、contains方法
1.2、头插法尾插法
头插法
尾插法
引入 last 用于指向链表的尾，优点是在使用尾插法插入一个结点的时候，时间复杂度是O(1)，因为它省略了找最后一个结点的过程
在插入结点时，统一先绑定后面的节点，减少出错的可能
1.3、任意位置插入一个节点
任意位置插入一个节点
1.4、删除第一个值为key的节点
删除一个结点
1.5、删除所有值为key的节点
1.6、清空结点
粗暴的写法，也能回收所有结点
更好的写法
2、LinkedList
2.1、什么是LinkedList
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的结点中，通过引用将节点连接起来，所以在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
- LinkedList比较适合任意位置插入的场景
构造方法：
2.2、LinkedList常用方法
2.3、LinkedList的遍历
IList myLinkedList = new MyLinkedList();
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // 尾插
list.add(2);
list.add(3);
list.add(4);
// 直接使用toString
System.out.println(list);
// foreach遍历
for(Integer x: list) {
System.out.print(x+" ");
}
System.out.println();
// for 循环
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
// 使用迭代器遍历---反向遍历
ListIterator<Integer> it2 = list.listIterator(list.size());
while (it2.hasPrevious()) {
System.out.print(it2.previous()+" ");
}
System.out.println();
3、ArrayList 和LinkedList区别
面试问题：
1.ArrayList 和LinkedList区别是什么?
2.顺序表和链表的区别？
3.数组和链表的区别？
元素高效存储：比如说每次都往最后一个位置插入，很快就能完成
应用场景补充：
如果是经常根据下标进行查找的使用顺序表 (ArrayList)
如果经常进行插入和删除操作的可以使用链表 (LinkedList)
