前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页:KC老衲爱尼姑的博客主页 博主的github,平常所写代码皆在于此 刷题求职神器 共勉:ta
前言
在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”
博客主页:KC老衲爱尼姑的博客主页
共勉:talk is cheap, show me the code
作者是爪哇岛的新手,水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
LinkedList底层是基于双链表实现,内部使用节点存储数据,相比于数组而言,LinkedList删除和插入元素的效率远高于数组,而查找和修改的效率比数组要低。
LinkedList的继承关系
说明
//记录链表长度 transient int size = 0; //头指针 transient node<E> first;//尾指针 transient Node<E> last;
public LinkedList() { }
public LinkedList(Collection<? extends E> c) { this(); //将集合中的元素添加到链表中 addAll(c); }//将指定集合中的元素添加到链表中 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { //检查index是否合法 checkPositionIndex(index);//将结合转换成数组 Object[] a = c.toArray(); //得到数组的长度 int numNew = a.length; //判读数组长度是否为0 if (numNew == 0) return false;//定义一个节点pred为前驱,succ为后继 Node<E> pred, succ; //数组长度如果等于链表长度,向链表尾部添加元素 if (index == size) { succ = null;//将后继置空 pred = last;//将链表的最后一个节点的引用赋值给pred } else { //index不等于size,则说明是插入链表中间位置 succ = node(index);//index位置节点的引用 pred = succ.prev;//index位置前一个节点的引用 }//遍历数组,每遍历一个数组元素,就创建一个节点,再将它插入链表相应位置 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为新节点的引用 pred = newNode; } if (succ == null) { //如果是从尾部开始插入的,让last指向最后一个插入的节点 last = pred; } else { //如果不是从尾部插入的,则把尾部的数据和之前的节点连起来 pred.next = succ; succ.prev = pred; } size += numNew;//更新链表长度 modCount++; return true; }
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; } }
源码如下
public void addFirst(E e) { linkFirst(e); } //头插 private void linkFirst(E e) { final Node<E> f = first;//获取到头节点的引用 final Node<E> newNode = new Node<>(null, e, f); first = newNode;//更新first的指向 if (f == null)//如果为空则说明链表为空 last = newNode;//让尾指针指向新节点 else f.prev = newNode;// size++;//长度自增 modCount++; }
代码示例
public class Demo { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<Integer>(); list.addFirst(1); list.addFirst(2); list.addFirst(3); System.out.println(list); }}//运行结果//[3, 2, 1]
图解头插
源码如下
public void addLast(E e) { linkLast(e);//尾插} //尾插具体实现 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++;}
代码示例
public class Demo { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<Integer>(); list.addLast(1); list.addLast(2); list.addLast(3); System.out.println(list); }}//运行结果//[1, 2, 3]
图解尾插
源码如下
public E getFirst() { final Node<E> f = first;//得到first引用 if (f == null)//链表中无节点 throw new NoSuchElementException();//抛出异常 return f.item;//返回头节点的数据 }
源码如下
public E getLast() { final Node<E> l = last;//得到last引用 if (l == null)//链表中无节点 throw new NoSuchElementException();//抛出异常 return l.item;//返回头节点的数据 }
源码如下
public E removeFirst() { final Node<E> f = first;//得到头节点的引用 if (f == null)//如果为null则没有头节点 throw new NoSuchElementException();//抛出异常 return unlinkFirst(f);//删除操作 } //删除链表第一个节点 private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item;//得到头节点的数据 final Node<E> next = f.next;//得到第二个节点的引用 f.item = null;//将头节点数据域置空 f.next = null; //将头节点next域置空 first = next;//更新first指针的指向 if (next == null)//next等于null,说明只有一个节点 last = null; else next.prev = null;//将第二个节点的preve置空 size--;//长度-1 modCount++; return element;//返回要删除头节点的数据 }
源码如下
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException();//抛出异常 return unlinkLast(l); } //删除链表最后个节点 private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
源码如下
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++; }
源码如下
public void add(int index, E element) { checkPositionIndex(index);//检查index合法性 if (index == size)//如果相等,插入到尾部 linkLast(element);//尾插 else//非尾部位置 linkBefore(element, node(index));// } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } 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++; } void linkBefore(E e, Node<E> succ) { //succ为要插入位置的节点,同时也是你要插入该位置节点的后继 final Node<E> pred = succ.prev;//得到插入位置的前驱 final Node<E> newNode = new Node<>(pred, e, succ);//将元素,以及前驱和后继传入 succ.prev = newNode;//更新插入位置节点的前驱为要插入节点的引用 if (pred == null)//如果pred为空说明,要插入的节点已经跑到头节点之前了,需要重置头节点 first = newNode; else pred.next = newNode;//否则的话将pred的next域指向新节点即可 size++; modCount++; } //寻找指定位置的节点 Node<E> node(int index) { //如果index靠近链表的前部分,则从头开始遍历寻找要找的节点 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else {//靠近后半部分,则倒着寻找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
源码如下
public E remove(int index) { checkElementIndex(index);//检查index合法性 return unlink(node(index)); }//删除index位置的具体操作 E unlink(Node<E> x) { final E element = x.item;//要删除节点的值 final Node<E> next = x.next;//要删除节点的后一个节点的引用 final Node<E> prev = x.prev;//要删除节点的前一个节点//如果prev为空意味着删除的节点是头节点,否则就不是头节点 if (prev == null) { first = next; } else { prev.next = next; x.prev = null;//要删除的节点prev域置空 }//如果prev为空意味着删除的节点是尾节点,否则就不是尾节点 if (next == null) { last = prev; } else { next.prev = prev; x.next = null;//要删除的节点next域置空 } x.item = null;//将要删除节点的数据域置空 size--;//链表的长度减一 modCount++; return element;//返回删除节点的数据域的值 }
源码如下
public E get(int index) { checkElementIndex(index); return node(index).item; } //寻找指定位置的节点 Node<E> node(int index) { //如果index靠近链表的前部分,则从头开始遍历寻找要找的节点 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else {//靠近后半部分,则倒着寻找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
源码如下
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
上述的get()和set()方法中的node()方法是以二分查找来看index位置距离size的一半位置,在决定从头遍历还是从尾遍历。以o(n/2)的效率得到一个节点。
源码如下
//从头往尾找该元素第一次出现的下标 public int indexOf(Object o) { int index = 0; //元素为null if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { //元素不为null for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1;//在链表中找不到 }
源码如下
//从尾往头找该元素第一次出现的下标 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
源码如下
//清空链表 public void clear() {//遍历链表将每个节点中next,prve,item全部置空 for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null;//头尾引用都置空 size = 0;//长度值为0 modCount++; }
ArrayList与LinkedList的区别
终
来源地址:https://blog.csdn.net/qq_60308100/article/details/127647912
--结束END--
本文标题: 《JavaSE-第十七章》之LinkedList
本文链接: https://www.lsjlt.com/news/398502.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-01
2024-04-03
2024-04-03
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
一口价域名售卖能注册吗?域名是网站的标识,简短且易于记忆,为在线用户提供了访问我们网站的简单路径。一口价是在域名交易中一种常见的模式,而这种通常是针对已经被注册的域名转售给其他人的一种方式。
一口价域名买卖的过程通常包括以下几个步骤:
1.寻找:买家需要在域名售卖平台上找到心仪的一口价域名。平台通常会为每个可售的域名提供详细的描述,包括价格、年龄、流
443px" 443px) https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294.jpg https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294-768x413.jpg 域名售卖 域名一口价售卖 游戏音频 赋值/切片 框架优势 评估指南 项目规模
0