【Java】LinkedList 集合
LinkedList集合特点
LinkedList 底层基于双向链表实现增删 效率非常高，查询效率非常低。
LinkedList源码解读分析
- LinkedList 是双向链表实现的 List
- LinkedList 是非线程安全的（线程是不安全的）
- 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 底层基于链表实现 增删 效率非常高 查询效率是非常低*/List<String> linkedList = new LinkedList<>();linkedList.add("mayikt1");linkedList.add("mayikt2");linkedList.add("mayikt3");linkedList.get(0);/*** LinkedList get()底层是如何实现的呢？* 底层基于双向链表实现*/System.out.println(linkedList.size());Iterator<String> iterator = linkedList.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}System.out.println("===删除之后===");linkedList.remove(1);Iterator<String> 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) {LinkedList<String> 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 MayiktLinkedList<E> {private Node<E> first;//第一个节点private Node<E> last; //最后一个节点int size = 0; //LinkedList存放的元素个数private static class Node<E> {private E item;//当前节点的值private Node<E> prev;//上一个节点private Node<E> next;//下一个节点
// transient Node<E> next;// transient表示next节点不能够被序列化的/*** @param prev 当前节点的上一个节点* @param item 当前节点的值* @param next 当前节点的下一个节点*/public Node(Node<E> prev, E item, Node<E> next) {this.item = item;this.prev = prev;this.next = next;}}public void add(E e) {//add()创建一个新的node节点时，新的node节点的上一个节点是还未新增时的last尾节点Node l = last;//获取当前链表中最后一个节点//创建一个新的node节点//newNode节点的上一个节点，就是当前链表中的最后一个节点Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null) {//如果在链表中没有最后一个节点的话——链表为空first = newNode;} else {l.next = newNode;}size++;}/*** 根据index 查询 链表中对应的node节点* 对半查找*/Node<E> node(int index) {if (index < size >> 1) { //size >>1 =>size/2//查询链表中间值的左边Node<E> f = first;for (int i = 0; i < index; i++) {f = f.next;}return f;} else {//查询链表中间值的右边Node<E> 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(Node<E> node) {//1.根据index 查询对应的node节点，时间复杂度为O(n)//2.删除链表效率非常高，比arrayList效率高，因为arrayList需要移动数组，而链表只需修改prev,next的指向问题//获取删除的node节点 上一个和下一个node节点final E element = node.item;//获取删除节点元素值Node<E> prev = node.prev;//删除节点的上一个节点Node<E> 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) {MayiktLinkedList<String> 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集合