上一篇我们围绕了ArrayList以及List进行简单介绍,本篇我们将围绕AbstractSequentialList、LinkedList进行。
AbstractSequentialList
AbstractSequentialList
是Java集合框架中的一个抽象类,它实现了List接口,并且是针对顺序访问的列表数据结构的基类。它提供了一些通用的方法实现,以简化具体实现类的开发。
他简单继承自AbstractList<E>
,实现了List接口中的大部分方法,并且通过使用迭代器来实现这些方法,主要实现方式是基于链接节点的数据结构,每个节点都包含元素值和指向下一个节点的引用。
并且,他是一个抽象类,所以不能直接实例化,而是需要通过继承它的子类来使用。子类需要实现抽象方法,包括get(int index)
、add(E element)
、remove(int index)
等,以提供具体的访问和修改列表的功能。
AbstractSequentialList
的子类包括LinkedList
和CopyOnWriteArrayList
等。LinkedList
是一个双向链表的实现,它提供了快速的插入和删除操作。CopyOnWriteArrayList
是一个线程安全的列表,它通过在修改操作时创建一个新的副本来实现线程安全性。
AbstractSequentialList类提供了一些常用的方法,包括添加元素、删除元素、获取元素、遍历元素等。它的子类可以根据具体的需求来实现这些方法,以实现不同类型的有序列表。
import java.util.AbstractSequentialList;
import java.util.LinkedList;
import java.util.ListIterator;
public class AbstractSequentialListExample {
public static void main(String[] args) {
AbstractSequentialList<String> list = new LinkedList<>();
// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Orange");
// 获取元素
System.out.println("First element: " + list.get(0));
System.out.println("Last element: " + list.get(list.size() - 1));
// 遍历元素
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// 删除元素
list.remove(1);
// 遍历元素
iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
主要作用:
- 用于实现有序列表,在提供了相关基本操作方法,包括添加元素,删除元素,获取元素,遍历元素等,其子类可以根据具体的需求来实现相关方法,从而实现不同类型的有序列表。
- 使用有序列表可以帮助我们解决许多问题,例如,我们可以通过
AbstractSequentialList
来实现一个待办事项列表,其中的任务按照优先级进行排序,我们也可以使用有序列表来实现一个排行榜,其中的成绩按照得分进行排序。 - 我们可以使用AbstractSequentialList来实现一个栈,其中的元素按照后进先出的顺序进行存储和访问。我们也可以使用AbstractSequentialList来实现一个队列,其中的元素按照先进先出的顺序进行存储和访问。
LinkedList
对比上述的AbstractSequentialList,我们用的最多的还是LinkedList,我们先回顾一下,什么是LinkedList?
什么是LinkedList?
他是Java集合框架集合中的一个实现了List接口的双向链表数据结构,并以节点的形式存储元素,并通过使用将相关节点连接起来形成链表。
特点
-
LinkedList的特点是可以高效地进行元素的插入和删除操作,因为它不需要像数组那样进行元素的移动。它还可以快速访问链表的第一个和最后一个元素,以及在任意位置插入和删除元素。
-
我们上篇讲解了ArrayList,知道了ArrayList的查询很快,但是插入和删除就比较慢了,这个LinkedList则是插入和删除快,但是查询慢。
主要原因在于,其数据结构,LinkedList的数据结构是由一个头节点和一个尾节点
组成,每个节点都包含一个元素和两个指针
,分别指向前一个节点和后一个节点,通过这些指针,LinkedList可以在常数时间内进行元素的插入和删除操作。
由于LinkedList是一个双向链表,所以它可以从头到尾或者从尾到头遍历元素。此外,LinkedList还实现了Deque接口,可以用作队列或栈的数据结构。
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
// 添加元素
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
// 获取元素
System.out.println("First element: " + linkedList.getFirst());
System.out.println("Last element: " + linkedList.getLast());
// 遍历元素
for (String element : linkedList) {
System.out.println(element);
}
// 在指定位置插入元素
linkedList.add(1, "Grape");
// 删除元素
linkedList.removeLast();
// 遍历元素
for (String element : linkedList) {
System.out.println(element);
}
}
}
LinkedList的默认构造函数:
主要用途
LinkedList主要是实现一个双向链表数据结构。
-
动态大小:LinkedList的大小可以根据需要动态增长或缩小,不需要预先指定容量大小。
-
高效的插入和删除操作:由于LinkedList是基于链表实现的,插入和删除元素的操作效率很高。在链表中插入或删除一个元素只需要改变相邻节点的指针,不需要像数组那样进行元素的移动。
-
随机访问较慢:由于LinkedList是基于链表实现的,它的随机访问效率较低。如果需要频繁地根据索引访问元素,使用ArrayList可能更合适。
-
支持双向遍历:LinkedList可以从头到尾或者从尾到头遍历元素,因为每个节点都包含了指向前一个节点和后一个节点的指针。
-
实现了List和Deque接口:LinkedList实现了List接口,可以用作普通的有序列表。它还实现了Deque接口,可以用作队列或栈的数据结构。
-
适用于频繁的插入和删除操作:由于LinkedList的插入和删除操作效率高,它特别适用于需要频繁进行插入和删除操作的场景,例如实现一个任务队列或消息队列。
ArrayList 和LinkedList的查询和删除进行比较
public class Demo2 {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();
// 添加元素
for (int i = 0; i < 1000000; i++) {
arrayList.add("Element " + i);
linkedList.add("Element " + i);
}
// 查询操作比较
long arrayListStartTime = System.nanoTime();
String arrayListElement = arrayList.get(500000);
long arrayListEndTime = System.nanoTime();
long linkedListStartTime = System.nanoTime();
String linkedListElement = linkedList.get(500000);
long linkedListEndTime = System.nanoTime();
System.out.println("ArrayList查询时间:" + (arrayListEndTime - arrayListStartTime) + " 纳秒");
System.out.println("LinkedList查询时间:" + (linkedListEndTime - linkedListStartTime) + " 纳秒");
// 添加操作比较
long arrayListAddStartTime = System.nanoTime();
arrayList.add(500000, "New Element");
long arrayListAddEndTime = System.nanoTime();
long linkedListAddStartTime = System.nanoTime();
linkedList.add(500000, "New Element");
long linkedListAddEndTime = System.nanoTime();
System.out.println("ArrayList添加时间:" + (arrayListAddEndTime - arrayListAddStartTime) + " 纳秒");
System.out.println("LinkedList添加时间:" + (linkedListAddEndTime - linkedListAddStartTime) + " 纳秒");
// 删除操作比较
long arrayListRemoveStartTime = System.nanoTime();
arrayList.remove(500000);
long arrayListRemoveEndTime = System.nanoTime();
long linkedListRemoveStartTime = System.nanoTime();
linkedList.remove(500000);
long linkedListRemoveEndTime = System.nanoTime();
System.out.println("ArrayList删除时间:" + (arrayListRemoveEndTime - arrayListRemoveStartTime) + " 纳秒");
System.out.println("LinkedList删除时间:" + (linkedListRemoveEndTime - linkedListRemoveStartTime) + " 纳秒");
}
}
注意,因为性能问题,你的电脑的时间和我的时间有所区别,具体时间的看你电脑的性能。
由上述结论我们可以得出一个结果,没错你猜对了。就是上述的主要用途写了。文章来源:https://www.toymoban.com/news/detail-793205.html
LinkedList的双向遍历
public class Demo3 {
public static void main(String[] args) {
LinkedList<String> studentList = new LinkedList<>();
// 添加学生姓名
studentList.add("Alice");
studentList.add("Bob");
studentList.add("Charlie");
studentList.add("David");
// 双向遍历
ListIterator<String> forwardIterator = studentList.listIterator();
//头指针
while (forwardIterator.hasNext()) {
System.out.println(forwardIterator.next());
}
System.out.println("-----");
//尾指针
ListIterator<String> backwardIterator = studentList.listIterator(studentList.size());
while (backwardIterator.hasPrevious()) {
System.out.println(backwardIterator.previous());
}
}
}
文章来源地址https://www.toymoban.com/news/detail-793205.html
到了这里,关于java基础 - 03 List之AbstractSequentialList、LinkedList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!