个人建设网站成本,网页制作平台有,泰安约吧,流程图 网站LinkedList 是一个基于双向链表实现的集合类。
LinkedList 插入和删除元素的时间复杂度
头部插入/删除#xff1a;只需要修改头结点的指针即可完成插入/删除操作#xff0c;因此时间复杂度为 O(1)。尾部插入/删除#xff1a;只需要修改尾结点的指针即可完成插入/删除操作…LinkedList 是一个基于双向链表实现的集合类。
LinkedList 插入和删除元素的时间复杂度
头部插入/删除只需要修改头结点的指针即可完成插入/删除操作因此时间复杂度为 O(1)。尾部插入/删除只需要修改尾结点的指针即可完成插入/删除操作因此时间复杂度为 O(1)。指定位置插入/删除需要先移动到指定位置再修改指定节点的指针完成插入/删除因此需要移动平均 n/2 个元素时间复杂度为 O(n)。
LinkedList 实现了以下接口
List : 表明它是一个列表支持添加、删除、查找等操作并且可以通过下标进行访问。Deque 继承自 Queue 接口具有双端队列的特性支持从两端插入和删除元素方便实现栈和队列等数据结构。Cloneable 表明它具有拷贝能力可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作也就是可以将对象转换为字节流进行持久化存储或网络传输非常方便。
每个节点的定义
private static class NodeE {E item;// 节点值NodeE next; // 指向的下一个节点后继节点NodeE prev; // 指向的前一个节点前驱结点// 初始化参数顺序分别是前驱结点、本身节点值、后继节点Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}
}插入元素
// 在链表尾部插入元素
public boolean add(E e) {linkLast(e);return true;
}// 在链表指定位置插入元素
public void add(int index, E element) {// 下标越界检查checkPositionIndex(index);// 判断 index 是不是链表尾部位置if (index size)// 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可linkLast(element);else// 如果不是则调用 linkBefore 方法将其插入指定元素之前linkBefore(element, node(index));
}// 将元素节点插入到链表尾部
void linkLast(E e) {// 将最后一个元素赋值引用传递给节点 lfinal NodeE l last;// 创建节点并指定节点前驱为链表尾节点 last后继引用为空final NodeE newNode new Node(l, e, null);// 将 last 引用指向新节点last newNode;// 判断尾节点是否为空// 如果 l 是null 意味着这是第一次添加元素if (l null)// 如果是第一次添加将first赋值为新节点此时链表只有一个元素first newNode;else// 如果不是第一次添加将新节点赋值给l添加前的最后一个元素的nextl.next newNode;size;modCount;
}// 在指定元素之前插入元素
void linkBefore(E e, NodeE succ) {// assert succ ! null;断言 succ不为 null// 定义一个节点元素保存 succ 的 prev 引用也就是它的前一节点信息final NodeE pred succ.prev;// 初始化节点并指明前驱和后继节点final NodeE newNode new Node(pred, e, succ);// 将 succ 节点前驱引用 prev 指向新节点succ.prev newNode;// 判断尾节点是否为空为空表示当前链表还没有节点if (pred null)first newNode;else// succ 节点前驱的后继引用指向新节点pred.next newNode;size;modCount;
}
获取元素
// 获取链表的第一个元素
public E getFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return f.item;
}// 获取链表的最后一个元素
public E getLast() {final NodeE l last;if (l null)throw new NoSuchElementException();return l.item;
}// 获取链表指定位置的元素
public E get(int index) {// 下标越界检查如果越界就抛异常checkElementIndex(index);// 返回链表中对应下标的元素return node(index).item;
}// 返回指定下标的非空节点
NodeE node(int index) {// 断言下标未越界// assert isElementIndex(index);// 如果index小于size的二分之一 从前开始查找向后查找 反之向前查找if (index (size 1)) {NodeE x first;// 遍历循环向后查找直至 i indexfor (int i 0; i index; i)x x.next;return x;} else {NodeE x last;for (int i size - 1; i index; i--)x x.prev;return x;}
}
get(int index) 或 remove(int index) 等方法内部都调用了node(int index)方法来获取对应的节点。 从这个方法的源码可以看出该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半就从链表头开始遍历反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点充分利用了双向链表的特性来提高效率
删除元素
// 删除并返回链表的第一个元素
public E removeFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return unlinkFirst(f);
}// 删除并返回链表的最后一个元素
public E removeLast() {final NodeE l last;if (l null)throw new NoSuchElementException();return unlinkLast(l);
}// 删除链表中首次出现的指定元素如果不存在该元素则返回 fals
public boolean remove(Object o) {// 如果指定元素为 null遍历链表找到第一个为 null 的元素进行删除if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);return true;}}} else {// 如果不为 null ,遍历链表找到要删除的节点for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}// 删除链表指定位置的元素
public E remove(int index) {// 下标越界检查如果越界就抛异常checkElementIndex(index);return unlink(node(index));
}E unlink(NodeE x) {// 断言 x 不为 null// assert x ! null;// 获取当前节点也就是待删除节点的元素final E element x.item;// 获取当前节点的下一个节点final NodeE next x.next;// 获取当前节点的前一个节点final NodeE prev x.prev;// 如果前一个节点为空则说明当前节点是头节点if (prev null) {// 直接让链表头指向当前节点的下一个节点first next;} else { // 如果前一个节点不为空// 将前一个节点的 next 指针指向当前节点的下一个节点prev.next next;// 将当前节点的 prev 指针置为 null方便 GC 回收x.prev null;}// 如果下一个节点为空则说明当前节点是尾节点if (next null) {// 直接让链表尾指向当前节点的前一个节点last prev;} else { // 如果下一个节点不为空// 将下一个节点的 prev 指针指向当前节点的前一个节点next.prev prev;// 将当前节点的 next 指针置为 null方便 GC 回收x.next null;}// 将当前节点元素置为 null方便 GC 回收x.item null;size--;modCount;return element;
}
unlink图解
遍历链表
推荐使用for-each 循环来遍历 LinkedList 中的元素 for-each 循环最终会转换成迭代器形式。
作者声明
如有问题欢迎指正
