数据结构（Java）：集合类LinkedList&集合类Stack
1、集合类LinkedList
1.1 什么是LinkedList
LinkedList的底层是一个双向链表的结构（故不支持随机访问）：
在LinkedList中，定义了first和last，分别指向链表的首节点和尾结点。
每个节点中有一个成员用来存储数据，还有两个指针域next和prev分别存储下一个节点和上一个节点的地址。
LinkedList也实现了List接口。
1.2 LinkedList的有关方法
1.2.1 构造方法
第二个构造方法的使用和ArrayList是相同的，可以使用实现了Collection接口并且泛型上界为E的集合类来构造LinkedList。
1.2.2 常用方法
1.3 ArrayList和LinkedList的区别
最重要的区别就是 ArrayList底层结构是数组；而，LinkedList的底层结构是双向链表。
2、集合类Stack
Stack是Java为我们封装好的一个“栈”，要想学习Stack，我们需要想了解栈是什么。
2.1 栈
栈，是一种数据结构，是一种特殊的线性表，只允许在固定的一端（栈顶）进行元素的插入和删除操作，栈中的元素具有“先进后出”的特点。
元素进栈，成为压栈、入栈。
元素出栈，称为出栈。
2.1.1 栈的实现
数组、单链表、双链表都可以实现栈，但是哪一种更好呢？
我们知道，元素出栈和入栈，必须在栈顶操作，那么:
- 对于数组，直接让size--或size++就可以，时间复杂度为O（1）。
- 对于单链表，如果采用尾插法入栈（即首节点定义为栈底，尾结点定义为栈顶），那么入栈和出栈需要找到尾结点才能继续操作，时间复杂度为O（n）。即使定义了last指向尾结点，入栈可改善为O（1），而出栈依然为O（n）。但是，如果采用头插法入栈的话，入栈操作和出栈操作，均会改善为O（n）。
- 对于双向链表，无论是入栈还是出栈，时间复杂度均为O（1）。
2.2 Stack的实现
我们上面提到数组、单链表头插入栈、双链表都可以很好的实现栈，
而集合类Stack的底层结构是数组。
2.3 Stack的常用方法
- pop（） 将栈顶的元素取出，即出栈，同时返回栈顶的元素。
- peek（） 仅仅获取栈顶的元素，不会将元素出栈
- empty（）是Stack特有的判断栈是否为空的方法；Stack继承下来的isEmpty（）方法也具有相同的作用
- LinkedList中也有栈相关的方法，故也可以使用LinkedList来构建栈
原文地址：https://blog.csdn.net/2401_83595513/article/details/140332306
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！