网站充值支付宝收款怎么做,2345网址导航app,ppt模板下载网址,微信打卡小程序怎么弄线性数据结构
链表 LinkList
链表的数据结构
一组由节点组成的数据结构#xff0c;每个元素指向下一个元素#xff0c;是线性序列。
最简单的链表结构#xff1a;
数据指针#xff08;存放执行下一个节点的指针#xff09;
不适合的场景#xff1a;
需要循环遍历将…线性数据结构
链表 LinkList
链表的数据结构
一组由节点组成的数据结构每个元素指向下一个元素是线性序列。
最简单的链表结构
数据指针存放执行下一个节点的指针
不适合的场景
需要循环遍历将导致时间复杂度的提升
链表分类—单向链表
链表结构
数据指针 Next指向下一个节点
链表分类-双向列表
链表结构
数据指针 Next(指向下一个节点)指针 Prev指向前一个节点
链表分类-循环列表
链表结构
数据指针 Next(指向下一个节点最后一个节点指向第一个节点)
实现一个双向链表
实现链表节点
public class NodeE {E item;NodeE prev;NodeE next;public Node(E item, NodeE prev, NodeE next) {this.item item;this.prev prev;this.next next;}
}在头节点之前插入节点
void insertNodeBeforeHead(E e){
final NodeE oldHeadNodehead;
final NodeE newHeadNodenew NodeE(e,null,oldHeadNode);headnewHeadNode;if(oldHeadNodenull){// 说明原先链表中没有元素tailnewHeadNode;}else{// 如果有元素则需要改变头节点的指针指向oldHeadNode.prevnewHeadNode;}size;}在尾节点之后插入节点
void insertNodeAfterTail(E e){
final NodeE oldTailNodetail;
final NodeE newTailNodenew NodeE(e,oldTailNode,null);tailnewTailNode;if(oldTailNodenull){headnewTailNode;}else{oldTailNode.nextnewTailNode;}size;}拆除链表
E unlinkByNode(NodeE node){
final E elementnode.item;
final NodeE prevNodenode.prev;
final NodeE nextNodenode.next;// 改变前一个元素的next指针指向的元素if(prevNodenull){// 说明是头节点headnextNode;}else{prevNode.nextnextNode;node.prevnull;}// 改变后一个元素的prev指针指向的元素if(nextNodenull){// 说明是尾节点没有下一个元素tailprevNode;}else{nextNode.prevprevNode;node.nextnull;}size--;node.itemnull;return null;}移除元素 public boolean removeNodeByElement(E e){if(enull){for(NodeE starthead;start!null;startstart.next){if(start.itemnull){unlinkByNode(start);return true;}}}else{for(NodeE starthead;start!null;startstart.next){if(start.item.equals(e)){unlinkByNode(start);return true;}}}return false;}LinkedList 源码解读
继承关系 关键属性 transient int size0;/*** Pointer to first node.* Invariant: (first null last null) ||* (first.prev null first.item ! null)*/
transient NodeE first;/*** Pointer to last node.* Invariant: (first null last null) ||* (last.next null last.item ! null)*/
transient NodeE last;Node
其中节点 Node 的数据结构如下是 LinkedList 的内部类 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;}
}transient 的作用
首先需要理解 Java 中序列化和反序列化的作用
序列化将内存中的对象信息转化为二进制数组的方法可以将数组保存和传输然后使用原来的类模板恢复对象的信息。反序列化使用原来的类模板将序列化后的二进制数组恢复为 Java 对象。
如何实现序列化和反序列化
实现 Serializable 接口 写对象信息ObjectOutputStream.writeObject(Object object)该方法会判断 object 是否重写了 writeObject 方法如果重写了则通过反射调用重写后的方法完成序列化读对象信息ObjectInputStream.readObject()
什么情况下不需要序列化
节省空间去除部分无用的属性持有对象的引用对象在内存中的地址值
LinkedList 将 first 和 last 修饰成 transient 的原因
节省空间重新连接链表结点中保存前驱和后继的引用序列化之后前序结点和后继结点的地址发生了改变需要连接新的节点。
writeObject readObject
LinkedList 重写了 writeObject 和 readObject 方法自定义了序列化和反序列化的过程用于重新链接节点
序列化writeObject /*** Saves the state of this {code LinkedList} instance to a stream* (that is, serializes it).** serialData The size of the list (the number of elements it* contains) is emitted (int), followed by all of its* elements (each an Object) in the proper order.*/
private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out any hidden serialization magic 调用默认的序列化方法s.defaultWriteObject();// Write out size 指定序列化的容量单位32 bit ints.writeInt(size);// Write out all elements in the proper order.// 只把结点中的值序列化前序和后继的引用不序列化for(NodeE xfirst;x!null;xx.next)s.writeObject(x.item);}
反序列化readObject
/*** Reconstitutes this {code LinkedList} instance from a stream* (that is, deserializes it).*/
SuppressWarnings(unchecked)
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException,ClassNotFoundException{// Read in any hidden serialization magic 用默认的反序列化方法s.defaultReadObject();// Read in size 指定读的容量int sizes.readInt();// Read in all elements in the proper order.// 读取每一个结点保存的值创建新结点重新连接链表。for(int i0;isize; i)linkLast((E)s.readObject()); // linkLast是向链表中的尾部插入节点的方法}向链表的最后一个节点插入元素值为 e 的节点linkLast(E e)
核心流程
拿到当前的尾节点记为 l使用需要创建的元素 e 创建一个新的节点 newNodeprev 属性为 l 节点next 属性为 null将当前尾节点设置为上面新创建的节点 newNode如果 l 节点为空则代表当前链表为空, 将 newNode 设置为头结点否则将 l 节点的 next 属性设置为 newNode /*** Links e as last element.*/void linkLast(E e){
final NodeE llast;
final NodeE newNodenew Node(l,e,null);lastnewNode;if(lnull)firstnewNode;elsel.nextnewNode;size;modCount;}向指定节点前插入元素值为 e 的节点: linkBefore(E e, Node succ)
核心流程
拿到 succ 节点的 prev 节点使用 e 创建一个新的节点 newNode其中 prev 属性为 pred 节点next 属性为 succ 节点将 succ 节点的 prev 属性设置为 newNode如果 pred 节点为 null则代表 succ 节点为头结点要把 e 插入 succ 前面因此将 first 设置为 newNode否则将 pred 节点的 next 属性设为 newNode /*** Inserts element e before non-null Node succ.*/void linkBefore(E e,NodeE succ){
// assert succ ! null;
final NodeE predsucc.prev;
final NodeE newNodenew Node(pred,e,succ);succ.prevnewNode;if(prednull)firstnewNode;elsepred.nextnewNode;size;modCount;}移除链接上的节点 x取消链接 xE unlink(Node x)
核心流程
定义 element 为 x 节点的值next 为 x 节点的下一个节点prev 为 x 节点的上一个节点如果 prev 为空则代表 x 节点为头结点则将 first 指向 next 即可否则x 节点不为头结点将 prev 节点的 next 属性指向 x 节点的 next 属性并将 x 的 prev 属性清空如果 next 为空则代表 x 节点为尾节点则将 last 指向 prev 即可否则x 节点不为尾节点将 next 节点的 prev 属性指向 x 节点的 prev 属性并将 x 的 next 属性清空将 x 的 item 属性清空以便垃圾收集器回收 x 对象 /*** Unlinks non-null node x.*/E unlink(NodeE x){
// assert x ! null;
final E elementx.item;
final NodeE nextx.next;
final NodeE prevx.prev;if(prevnull){firstnext;}else{prev.nextnext;x.prevnull;}if(nextnull){lastprev;}else{next.prevprev;x.nextnull;}x.itemnull;size--;modCount;return element;}插入元素add
默认插入方法尾部插入boolean add(E e)
直接插入链表尾部 /*** Appends the specified element to the end of this list.** pThis method is equivalent to {link #addLast}.** param e element to be appended to this list* return {code true} (as specified by {link Collection#add})*/
public boolean add(E e){linkLast(e);return true;}指定位置插入元素add(int index,E element)
流程
检查索引 index 是否越界只要用到了索引 index都会判断是否越界如果索引 index 和链表当前的长度 size 相同则执行尾部插入否则将 element 插入原 index 位置节点的前面 /*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any* subsequent elements to the right (adds one to their indices).** param index index at which the specified element is to be inserted* param element element to be inserted* throws IndexOutOfBoundsException {inheritDoc}*/
public void add(int index,E element){checkPositionIndex(index);if(indexsize)linkLast(element);elselinkBefore(element,node(index));}获取节点get
核心流程
根据 index调用 node 方法,寻找目标节点返回目标节点的 item。 /*** Returns the element at the specified position in this list.** param index index of the element to return* return the element at the specified position in this list* throws IndexOutOfBoundsException {inheritDoc}*/
public E get(int index){checkElementIndex(index);return node(index).item;}根据指定索引 index 位置查找节点
核心流程
如果 index 的长度是链表长度的一半则在链表前半部分从头节点开始遍历否则从尾节点开始遍历 /*** Returns the (non-null) Node at the specified element index.*/NodeE node(int index){// assert isElementIndex(index);if(index (size1)){NodeE xfirst;for(int i0;iindex; i)xx.next;return x;}else{NodeE xlast;for(int isize-1;iindex;i--)xx.prev;return x;}}替换指定位置的元素set
核心流程
调用 node 方法寻找到目标节点将目标节点的 item 属性替换为目标元素 /*** Replaces the element at the specified position in this list with the* specified element.** param index index of the element to replace* param element element to be stored at the specified position* return the element previously at the specified position* throws IndexOutOfBoundsException {inheritDoc}*/
public E set(int index,E element){checkElementIndex(index);NodeE xnode(index);E oldValx.item;x.itemelement;return oldVal;}移除节点
移除指定元素的节点boolean remove(Object o)
核心流程
因为普通元素值和 null 判断存在区别所以需要判断 o 是否为 null如果 o 为 null则遍历链表寻找 item 属性为空的节点并调用 unlink 方法将该节点移除否则遍历链表寻找 item 属性跟 o 相同的节点并调用 unlink 方法将该节点移除。 /*** Removes the first occurrence of the specified element from this list,* if it is present. If this list does not contain the element, it is* unchanged. More formally, removes the element with the lowest index* {code i} such that* tt(onullnbsp;?nbsp;get(i)nullnbsp;:nbsp;o.equals(get(i)))/tt* (if such an element exists). Returns {code true} if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** param o element to be removed from this list, if present* return {code true} if this list contained the specified element*/
public boolean remove(Object o){if(onull){for(NodeE xfirst;x!null;xx.next){if(x.itemnull){unlink(x);return true;}}}else{for(NodeE xfirst;x!null;xx.next){if(o.equals(x.item)){unlink(x);return true;}}}return false;}移除指定索引位置的节点remove(int index)
核心流程
调用 unlink 方法移除 index 位置的节点 /*** Removes the element at the specified position in this list. Shifts any* subsequent elements to the left (subtracts one from their indices).* Returns the element that was removed from the list.** param index the index of the element to be removed* return the element previously at the specified position* throws IndexOutOfBoundsException {inheritDoc}*/
public E remove(int index){checkElementIndex(index);return unlink(node(index));}清除链表中的所有元素clear
从 first 节点开始遍历将所有的节点的 item、next、prev 值设置为 null。 public void clear(){// Clearing all of the links between nodes is unnecessary, but:// - helps a generational GC if the discarded nodes inhabit// more than one generation// - is sure to free memory even if there is a reachable Iteratorfor(NodeE xfirst;x!null;){NodeE nextx.next;x.itemnull;x.nextnull;x.prevnull;xnext;}firstlastnull;size0;modCount;}question
描述链表的数据结构Java 中的 LinkedList 的数据结构和原理
Node 的源码
有 Next 指针、Prev 指针说明是双向链表
LinkedList 的 linkLast 向尾元素后插入元素的方法源码
尾元素的 prev 指针没有指向头元素说明非循环
结论非循环双向链表
链表中数据的插入、删除和获取的时间复杂度分析
获取O(n) 插入
有前置节点头尾插入O(1)无前置节点O(n)
什么场景下更适合使用链表
在不确定数据量且需要频繁插入和删除操作的场景下。
leetcode 题目
707 设计链表
707 设计链表
