PHP网站开发常用函数,建站公司 phpwind,运营管理八个模块,做网站挣钱来个好心人指点一下呗本篇内容包括#xff1a;LinkedList 的概述、LinkedList 的结构既双向链表实现与LinkedList-Node 结构、LinkedList 的使用#xff08;构造方法常用方法#xff09;、关于 Queue 队列的介绍、关于 ArrayList 和 LinkedList 的区别以及算法#xff1a;翻转链表#xf… 本篇内容包括LinkedList 的概述、LinkedList 的结构既双向链表实现与LinkedList-Node 结构、LinkedList 的使用构造方法常用方法、关于 Queue 队列的介绍、关于 ArrayList 和 LinkedList 的区别以及算法翻转链表 一、LinkedList 概述 LinkedList 是用链表作为数据存储结构的 List 集合链表数据结构的特点是每个元素分配的空间不必连续因此链表很适合数据的动态插入和删除但是其随机访问和遍历速度比较慢。另外LinkedList还提供了 List 接口中没有定义的方法专门用于操作表头和表尾元素可以当作堆栈、队列和双向队列使用。 LinkedList 是以链表实现的插入、删除时只需要改变前后两个节点指针指向即可实现了真正的动态不需要处理固定容量的问题但是丧失了随机访问的能力 索引访问。
LinkedList 是一个双向链表实现插入、删除时只需要改变前后两个节点指针指向即可实现了真正的动态不需要处理固定容量的问题。LinkedList 在当数据量很大或者操作很频繁的情况下添加和删除元素时具有比 ArrayList 更好的性能。但在元素的查询和修改方面要弱于ArrayList。
LinkedList 与 ArrayList 一样 LinKedList 也不是线程安全的。 二、LinkedList 的结构
1、双向链表实现
LinKedList 的数据存储是基于双向链表实现。
LinkedList 类每个结点用内部类 Node 表示LinkedList 通过 first 和 last 引用分别指向链表的第一个和最后一个元素当链表为空时first 和 last 都为 NULL 值。 关于 LinKedList 操作数据时
插入数据很快先是在双向链表中找到要插入节点的位置 index找到之后再插入一个新节点。 双向链表查找 index 位置的节点时有一个加速动作若 index 双向链表长度的 1/2则从前向后查找否则从后向前查找删除数据很快先是在双向链表中找到要插入节点的位置 index找到之后进行如下操作node.previous.next node.next; node.next.previous node.previous; node null 查找节点过程和插入一样获取数据很慢每次获取数据都需要从 Head 节点从头开始查找遍历数据很慢同获取数据一样每次遍历数据都需要从头开始。
2、LinkedList-Node 结构
LinkedList 类内部的 Node 结点代码如下 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;}}Node 节点一共有三个属性item 代表节点值prev 代表节点的前一个节点next 代表节点的后一个节点。每个结点都有一个前驱和后继结点并且在 LinkedList 中也定义了两个变量分别指向链表中的第一个和最后一个结点。 三、LinkedList 的使用
1、构造方法
方法名方法说明public LinkedList()此构造函数用于构造一个空列表。public LinkedList(Collection? extends E c)此构造函数将按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表
2、常用方法_作为队列Linked继承了Queue
方法名方法说明boolean add(E e)此方法将指定的元素追加到此列表/队列的末尾E remove()此方法检索并删除此列表的头部第一个元素如果此列表为空则报错E removeFirst()此方法删除并返回此列表中的第一个元素如果此列表为空则报错E removeLast()此方法检索并删除此列表的最后一个元素如果此列表为空则报错E poll()此方法检索并删除此列表的头部第一个元素E pollFirst()此方法检索并删除此列表的第一个元素如果此列表为空则返回nullE pollLast()此方法检索并删除此列表的最后一个元素如果此列表为空则返回nullE element()此方法检索但不删除此列表的头部第一个元素
3、常用方法_作为栈FILO 先进后出的栈
方法名方法说明void push(E e)此方法将元素推送到此列表所表示的堆栈上E pop()此方法从此列表表示的堆栈中弹出一个元素E peek()此方法检索但不删除此列表的头部第一个元素E peekFirst()此方法检索但不删除此列表的第一个元素如果此列表为空则返回nullE peekLast()此方法检索但不删除此列表的最后一个元素如果此列表为空则返回null
4、常用方法_作为链表
方法名方法说明void add(int index, E e)此方法将指定的元素插入此列表中的指定位置。E remove(int index)此方法删除此列表中指定位置的元素E remove(Object o)此方法从该列表中删除指定元素的第一个匹配项如果存在E set(int index, E e)此方法使用指定的元素替换此列表中指定位置的元素E get(int index)此方法返回此列表中指定位置的元素E getFirst()此方法返回此列表中的第一个元素E getLast()此方法返回此列表中的最后一个元素int size()此方法返回此列表中的元素数boolean contains(Object o)如果此列表包含指定的元素则此方法返回trueboolean isEmpty()如果此列表为空则此方法返回trueint indexOf(Object o)此方法返回此列表中第一次出现的指定元素的索引如果此列表不包含该元素则返回-1int lastIndexOf(Object o)此方法返回此列表中指定元素最后一次出现的索引如果此列表不包含该元素则返回-1void clear()此方法将从此列表中删除所有元素Object clone()此方法返回返回此LinkedList的浅表副本Object[] toArray()此方法以适当的顺序从第一个元素到最后一个元素返回包含此列表中所有元素的数组T T[] toArray(T[] a)此方法以适当的顺序从第一个元素到最后一个元素返回包含此列表中所有元素的数组返回数组的运行时类型是指定数组的运行时类型四、相关知识点
1、关于 Queue 队列
队列Queue也是一种操作受限的线性表只允许在表的一端进行插入而在表的另一端进行删除。向队列中插入元素称为入队或进队删除元素称为出队或离队。 这和我们日常生活中的排队是一致的最早排队的也是最早离队的。其操作的特性是先进先出First In First Out, FIFO故又称为先进先出的线性表。基本上一个队列就是一个先入先出FIFO的数据结构
在Java 中 Queue 接口与 List、Set 同一级别都是继承了 Collection 接口。LinkedList 实现了 Deque 接口。
2、关于 ArrayList 和 LinkedList 的区别
在结构上ArrayList 底层是数组在内存上是连续的LinkedList 底层是双向链表在内存上是不连续的
在性能上ArrayList 由于内存上连续支持随机查询查询速度更快但是在增删时由于会涉及到数据的移动和数组的扩容往往是要慢于 LinkedList 的但并不绝对可以提前设置好足够的数组空间并采用尾插的方式
3、算法翻转链表
假设链表为 1→2→3→∅我们想要把它改成 ∅←1←2←3。
在遍历链表时将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点因此必须事先存储其前一个节点。在更改引用之前还需要存储后一个节点。最后返回新的头引用。
class Solution {public ListNode reverseList(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode next curr.next;curr.next prev;prev curr;curr next;}return prev;}
}
