南雄市建设局网站,什么是网络营销和网络营销的职能,企业营销策划案例分析,产品展示类网站模板LinkedList集合特点 LinkedList 底层基于双向链表实现增删 效率非常高#xff0c;查询效率非常低。 LinkedList源码解读分析 LinkedList 是双向链表实现的 ListLinkedList 是非线程安全的#xff08;线程是不安全的#xff09;LinkedList 元素允许为null,允许重复元素Linked… LinkedList集合特点 LinkedList 底层基于双向链表实现增删 效率非常高查询效率非常低。 LinkedList源码解读分析 LinkedList 是双向链表实现的 ListLinkedList 是非线程安全的线程是不安全的LinkedList 元素允许为null,允许重复元素LinkedList 是基于链表是实现的因此插入删除效率高如果根据下标增删 效率还是非常低的查询效率低LinkedList 是基于链表实现的因此不存在容量不足的问题所以没有扩容的方法LinkedList 还是实现了栈和队列的操作方法因此也可以作为栈、队列和双端队列来使用 示例代码
package com.collection.Demo08;import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;public class Test01 {public static void main(String[] args) {/*** LinkedList 底层基于链表实现 增删 效率非常高 查询效率是非常低*/ListString linkedList new LinkedList();linkedList.add(mayikt1);linkedList.add(mayikt2);linkedList.add(mayikt3);linkedList.get(0);/*** LinkedList get()底层是如何实现的呢* 底层基于双向链表实现*/System.out.println(linkedList.size());IteratorString iterator linkedList.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}System.out.println(删除之后);linkedList.remove(1);IteratorString iterator2 linkedList.iterator();while (iterator2.hasNext()){System.out.println(iterator2.next());}}
}package com.collection.Demo08;import java.util.LinkedList;public class Test02 {public static void main(String[] args) {LinkedListString strings new LinkedList();strings.add(mayikt01);strings.add(mayikt02);strings.add(mayikt03);strings.remove(0);System.out.println(strings.get(0));//mayikt01System.out.println(strings.getFirst());//mayikt01System.out.println(strings.getLast());//mayikt03}
}手写LinkedList集合
package com.collection.Demo08;/*** LinkedList底层是基于链表实现* 手写LinkedList集合*/public class MayiktLinkedListE {private NodeE first;//第一个节点private NodeE last; //最后一个节点int size 0; //LinkedList存放的元素个数private static class NodeE {private E item;//当前节点的值private NodeE prev;//上一个节点private NodeE next;//下一个节点
// transient NodeE next;// transient表示next节点不能够被序列化的/*** param prev 当前节点的上一个节点* param item 当前节点的值* param next 当前节点的下一个节点*/public Node(NodeE prev, E item, NodeE next) {this.item item;this.prev prev;this.next next;}}public void add(E e) {//add()创建一个新的node节点时新的node节点的上一个节点是还未新增时的last尾节点Node l last;//获取当前链表中最后一个节点//创建一个新的node节点//newNode节点的上一个节点就是当前链表中的最后一个节点NodeE newNode new Node(l, e, null);last newNode;if (l null) {//如果在链表中没有最后一个节点的话——链表为空first newNode;} else {l.next newNode;}size;}/*** 根据index 查询 链表中对应的node节点* 对半查找*/NodeE node(int index) {if (index size 1) { //size 1 size/2//查询链表中间值的左边NodeE f first;for (int i 0; i index; i) {f f.next;}return f;} else {//查询链表中间值的右边NodeE l last;for (int i size - 1; i index; i--) {l l.prev;}return l;}}public E get(int index) {//下标如果越界的话 需要抛出异常return node(index).item;}//根据下标查询public E remove(int index) {return unlink(node(index));}private E unlink(NodeE node) {//1.根据index 查询对应的node节点时间复杂度为O(n)//2.删除链表效率非常高比arrayList效率高因为arrayList需要移动数组而链表只需修改prev,next的指向问题//获取删除的node节点 上一个和下一个node节点final E element node.item;//获取删除节点元素值NodeE prev node.prev;//删除节点的上一个节点NodeE next node.next;//删除节点的下一个节点//如果删除的节点 上一个节点为空if (prev null) { //删除的该节点是头节点first next;} else {prev.next next;node.prev null;//改为null,是为了通知GC 回收}if (next null) {//删除的该节点是尾节点last prev;} else {next.prev prev;node.next null;}node.item null;//改为null,是为了通知GC 回收size--;return element;}public static void main(String[] args) {MayiktLinkedListString stringMayiktLinkedList new MayiktLinkedList();stringMayiktLinkedList.add(mayikt01);stringMayiktLinkedList.add(mayikt02);stringMayiktLinkedList.add(mayikt03);stringMayiktLinkedList.add(mayikt04);stringMayiktLinkedList.remove(1);System.out.println(stringMayiktLinkedList.get(0));System.out.println(stringMayiktLinkedList.get(1));
// System.out.println(stringMayiktLinkedList.get(2));
// System.out.println(stringMayiktLinkedList.get(3));}
}下一篇文章HashMap集合
