在上一篇《顺序表》中,我们已经熟悉了 ArrayList
的使用并且进行了简单的模拟实现。ArrayList
底层使用数组来存储元素,由于其底层是一段连续的空间,当ArrayList
任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后移动,时间复杂度为O(n),效率比较低,因此ArrayList
不适合做任意位置插入和删除比较多的场景。因此:Java集合这种又引入了 LinkedList
,即链表结构。
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中引用链接次序实现的。
注意:
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
虽然有这么多的链表结构,但是我们重点掌握两种:
创建一个链表
画图表示:
head = head.next
head == null
代码实现:
在链表的第一个位置插入元素。
思路:
next
指向head
head
指向插入元素代码实现:
在链表的最后个位置插入元素
思路:
next
指向插入的元素。代码实现:
思路:
index
是否合法(index < 0 或者 index 大于链表长度
),如果不合法则抛出异常。index
等于0或者index
等于链表长度,则使用头插法或尾插法cur
找到index - 1
位置next
指向cur
的next
cur
的next
指向插入的元素代码实现:
异常类:
代码实现:
代码实现:
思路:
head
指向head
的next
next
指向删除节点的next
代码实现:
思路:
cur
:可能要删除的节点prev
:可能要删除的节点的前驱cur
的val
是不是要删除的元素,如果是prev
的next
指向cur
的next
,cur
指向cur
的next
;否则prev
指向cur
,cur
指向cur
的next
val
是否为的元素,如果是头节点指向头节点的neext
代码实现:
当一个对象,没有被引用的时候,就会被回收掉