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来构建栈