对顺序表以及双向链表的理解

文章目录1.List 引入1.什么是 List2.ArrayList 的理解2.1 什么是 ArrayList2.2 ArrayList 的模拟实现2.2.1 实现 MyArrayList 类2.3ArrayList 的局限性3.链表 与 LinkedList3.1 链表的概念3.2 链表的模拟实现3.2.1 自创 MySingleList 类3.3 单链表相关的 OJ 面试题3.4 LinkedList 的结构3.5 LinkedList 的模拟实现3.5.1 实现 MyLinkedList 类3.6ArrayList、链表、LinkedList 关系1.List 引入1.什么是 List图片来自于菜鸟教程在了解ArrayList即顺序表 (Sequential List) 与LinkedList即 双向链表 (Doubly Linked List) 之前有必要先明List是什么。List是一个接口其继承自Collection类似可以理解为“合同”。它规定了所有子类需要具备的功能索引访问get(i)、插入元素add、删除元素remove等功能。List 与 ArrayList、LinkedList 的关系List 首先是一个接口可理解为合同而ArrayList、LinkedList则是它的实现类可理解为员工在合同下工作。也就是说ArrayList、LinkedList两个类都需要重写List中的方法。2.ArrayList 的理解2.1 什么是 ArrayList先从图片上引入对ArrayList的概念其实就是数组ArrayList中文称为顺序表从物理意义上它是用一段连续的物理内存数组来表达线性关系的。从源码上看主要是这几个常量包括容量数组实际大小usedSize…2.2 ArrayList 的模拟实现2.2.1 实现 MyArrayList 类我们尝试模拟实现一下ArrayList的主要功能定义一个MyArrayList类具体代码可访问GitHub远程仓库首先创建一个模拟IList接口根据接口定义的方法以及ArrayList的源码去模拟实现MyArrayList类publicinterfaceIList{// 新增元素,默认在数组最后新增publicvoidadd(intdata);// 在 pos 位置新增元素publicvoidadd(intpos,intdata);// 判断数组是否已满publicbooleanisFull();// 判定是否包含某个元素publicbooleancontains(inttoFind);// 查找某个元素对应的位置publicintindexOf(inttoFind);// 获取 pos 位置的元素publicintget(intpos);// 给 pos 位置的元素设为 valuepublicvoidset(intpos,intvalue);//删除第一次出现的关键字keypublicvoidremove(inttoRemove);// 获取顺序表长度publicintsize();// 清空顺序表publicvoidclear();// 打印顺序表注意该方法并不是顺序表中的方法为了方便看测试结果给出的publicvoiddisplay();}MyArrayList类有以下变量及构造方法publicclassMyArrayListimplementsIList{publicint[]array;publicintusedSize;publicstaticfinalintDEFAULT_CAPACITY10;publicMyArrayList(){arraynewint[DEFAULT_CAPACITY];}}由于ArrayList官方源码是适配多种类型而使用泛型我们为方便理解就从整型去创建。其涉及的相关题目可以有 杨辉三角的实现简单的洗牌算法参考源码了解完之后就对ArrayList有初步理解了2.3ArrayList 的局限性由于ArrayList底层代码是一段连续空间当在ArrayList任意位置插入或者删除元素时就需要将后续元素整体往前或者往后搬移时间复杂度为O(n)效率较低。3.链表 与 LinkedList3.1 链表的概念链表是物理存储结构上非连存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。每个节点存储了当前节点的value以及对下一个节点的索引其结构类似图中内容实际中链表结构又是多样的单项或者双向带头或者不带头循环或者非循环无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。因此我们以单向无头非循环链表举例。3.2 链表的模拟实现3.2.1 自创 MySingleList 类实现的代码可访问该链接 - 参考源码我们同样可以实现上面的 IList 接口其变量、内部类以及构造方法有以下publicclassMySingleListimplementsIList{// 创建整个链表中的各个节点车厢staticclassListNode{publicintval;publicListNodenext;// 对下一个节点的索引// 初始化各个节点publicListNode(intval){this.valval;}}// 存储头节点引用火车头publicListNodehead;}主要方法有头插法addFirst()、尾插法addLast()、任意位置插入addIndex()、是否包含contains()、删除节点remove()等等我们选部分了解头插法publicvoidaddFirst(intdata){ListNodenodenewListNode(data);node.nextthis.head;this.headnode;}即在头节点前插入时间复杂度为O(1)而 ArrayList 中为O(n)尾插法publicvoidaddLast(intdata){ListNodenodenewListNode(data);if(this.headnull){this.headnode;return;}ListNodecurthis.head;// cur.next ! null可以走到倒数第二个节点// 但最后一个节点地址可获取while(cur.next!null){curcur.next;}cur.nextnode;}即在最后节点插入注意最后节点的next必须置空另外补充官方在链表中增加新节点是默认使用尾插删除节点Overridepublicvoidremove(intkey){if(this.headnull){return;}if(this.head.valkey){this.headthis.head.next;return;}// 创建当前节点curListNodecurFindNodeBeforeKey(key);cur.nextcur.next.next;}// 查找到删除节点前的一个节点privateListNodeFindNodeBeforeKey(intkey){// 创建当前节点ListNodecurthis.head;// cur要每一个都走一遍while(cur.next!null){if(cur.next.valkey){returncur;}curcur.next;}returnnull;}利用删除节点的前一节点访问到删除节点的val值去匹配key以及当前节点cur的next索引的修改3.3 单链表相关的 OJ 面试题删除链表中等于给定值 val 的所有节点。Leecode 移除链表元素反转一个单链表。Leecode 反转一个单链表给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。Leecode 链表的中间节点输入一个链表输出该链表中倒数第k个结点。 Leecode 返回倒数第k个节点将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。Leecode 合并两个有序链表编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。Leecode 分割链表链表的回文结构。Leecode 回文链表输入两个链表找出它们的第一个公共结点。Leecode 相交链表9.给定一个链表判断链表中是否有环。Leecode 环形链表尝试上面的 Oj 题后相信你对链表有自己的见解了以上 Oj 题我会同步发出题解文章3.4 LinkedList 的结构LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在任意位置插入或者删除元素时不需要搬移元素效率比较高。以下图片即为双向链表结构包含了val、prev前驱、next后驱以及head头指针和尾指针通过以下集合框架可以发现LinkedList也同样实现了 List 接口说明1.LinkedList 实现了 List 接口2.LinkedList 的底层使用了双向链表3.LinkedList 没有实现 RandomAccess 接口因此 LinkedList 不支持随机访问4.LinkedList 的任意位置插入和删除时效率比较高时间复杂度为 O(1)5.LinkedList 比较适合任意位置插入的场景3.5 LinkedList 的模拟实现3.5.1 实现 MyLinkedList 类和ArrayList、单向链表一样同样实现List接口在此我们就模拟实现IList接口publicclassMyLinkedListimplementsIList{// 内部类-各个节点classListNode{publicintval;publicListNodeprev;// 前驱publicListNodenext;// 后驱publicListNode(intval){this.valval;}}publicListNodehead;publicListNodelast;}与链表类似但删除时不再需要提前一个节点我们可直接到要删除的节点位置remove()- 删除方法Overridepublicvoidremove(intkey){ListNodecurhead;while(cur!null){if(cur.valkey){//删除在开头if(curhead){headhead.next;if(head!null){// 情况 A: 至少还有两个节点现在的 head 指向原第二个节点head.prevnull;}else{// 情况 B: 原本只有一个节点删完后 head 为 null// 必须同步清理 lastlastnull;}}else{//删除在其他中间、结尾cur.prev.nextcur.next;if(cur.nextnull){lastlast.prev;// 该情况为删除在结尾}else{cur.next.prevcur.prev;}}return;}curcur.next;}}如代码中注释删除位置首先分为两处–开头、2. 中间和结尾随后依次在分类讨论情况其常用方法与ArrayList类似3.6ArrayList、链表、LinkedList 关系线性表 (Linear List)——“我们要排成一队”(逻辑协议)├──顺序表 (Sequential List)——“大家必须坐连排座”(底层是数组)└──链表 (Linked List)——“大家随便坐手拉手就行”(底层是节点)├──单向链表——“只知道后面是谁”└──双向链表——“既知道前面也知道后面”概念名称属于什么物理结构在 Java 中的“肉身”顺序表线性表的一种实现连续数组ArrayList链表线性表的一种实现分散节点指针LinkedList链表节点链表的组成零件包含数据和指针的对象ListNode类以上是我关于Java的笔记分享感谢你读到这里这也是我学习路上的一个小小记录。希望以后回头看时能看到自己的成长~