双向链表在java中的应用举例-LinkedList
程序员文章站
2022-07-14 08:34:29
...
双向链表在java中的应用举例-LinkedList
复习了链表,作为一种高效的存储数据的方式
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
这里LinkedList 继承于AbstractSequentialList的双向链表。
同时实现了List接口可以通过指向List进行实例化,能进行队列操作。
实现了Deque接口,也可以当作双端队列来使用。
Cloneable可以实现克隆操作。
java.io.Serializable表明该类可以进行序列化。
构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
可以看到里面提供一个空的构造函数和一个可以赋值的实现了collecton接口的集合
可以看到collection是集合的基本类,set,list都继承了collection接口,所以,可以将实现了上述的接口的类添加进去。
接下来 看一下addall方法
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length; //求出新加入的数组的大小
if (numNew == 0)
return false;
Node<E> pred, succ; //pred为插入位置的头结点,succ为后节点
if (index == size) { //如果直接是在最后进行插入
succ = null; //将尾节点设置尾空,本来是就是空,这个时候不需要尾节点进行作,
//当直接进行尾插的时候,仅仅需要一个节点就可以完成
pred = last; //将头结点设置到尾部,方便插入
} else {
succ = node(index); //设置尾节点为具体的位置
pred = succ.prev; //设置为succ的前置节点
}
for (Object o : a) { //循环加入节点
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); //因为是尾插,后置节点一直为空
if (pred == null)
first = newNode; //头结点为空,在第一次插入时候出现
else
pred.next = newNode; //如果不是第一次 插入,循环尾插
pred = newNode;
}
if (succ == null) { //如果是插入的位置在尾部,直接将last
//设置为pred 指向尾部,这里last的next为空
last = pred;
} else {
pred.next = succ; //如果不是插入在尾部,需要对头结点和尾节点进行链接,这里pre已经
//到达了尾部
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
这里要指出的是Node是其中的一个类部类,创建双向指针的内部类,代码如下,可以通过构造方法设置他的指向,也应该为了配合链表特性没有用标准 的set get方法。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
add方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
同理,上面的add方法也是通过尾插的方法将其插入尾部
同时类中还封装了其他很多的方法,本篇主要对LinkedList中的链表方法进行讲解,其他的部分读者可以自行参考源码。
如果有问题欢迎指正。
上一篇: Python第十章(文件与异常)课后习题
下一篇: 排查启动网卡启动错误
推荐阅读
-
Java日期时间API系列5-----Jdk7及以前的日期时间类TimeUnit在并发编程中的应用
-
深入了解final在java中的应用
-
linkedList中的双向链表JDK1.8
-
双向链表在java中的应用举例-LinkedList
-
中间件编程之RMI在Java中的应用 中间件编程Java网络应用企业应用
-
Java自定义注解以及在POI导出EXCEL中的一个应用 javaannotationPOIexcel
-
java单链表(Linked List)查找单链表中的倒数第k个节点的应用示例
-
java web之路 jsp状态管理 cookie在登陆中的应用
-
基于Protobuf动态解析在Java中的应用 包含例子程序
-
XML和JSON在Java开发中的实际应用