德阳做网站的互联网公司,联通官网,网站第一屏一般做多大,单位建设网站注意点目录
1#xff0c;ArrayList的缺陷
2#xff0c;链表
2.1 链表的概念及结构
2.2 链表的实现
2.2.1 无头单向非循环链表实现
3#xff0c;LinkedList的模拟实现
3.1 无头双向链表实现
4#xff0c;LinkedList的使用
4.1 什么是LinkedList
4.2 LinkedList的使用
5…目录
1ArrayList的缺陷
2链表
2.1 链表的概念及结构
2.2 链表的实现
2.2.1 无头单向非循环链表实现
3LinkedList的模拟实现
3.1 无头双向链表实现
4LinkedList的使用
4.1 什么是LinkedList
4.2 LinkedList的使用
5ArrayList和LinkedList的区别 1ArrayList的缺陷
当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。因此java 集合中又引入了LinkedList即链表结构。
2链表
2.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表是由一个一个节点组织起来的整体就叫做链表 注意
1从上图可以看出链式结构在逻辑上是连续的但是在物理上地址不一定是连续的
2现实中的节点一般都是从堆上申请出来的
3从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续可能不连续
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 我们主讲单向不带头非循环和双向不带头非循环因为截止到目前为止所有链表的题考的都是单项不带头非循环
1单向不带头非循环 带头 如果是带头的头节点里面也可以存储值但是不具备意义可以认为头节点是一个标志永远是头不会动了就是说对于不带头的链表如果把12删了head就会指向23节点的地址对于带头的链表来说把12删了head还是在原来位置。
循环 无头双向链表在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。
2.2 链表的实现
2.2.1 无头单向非循环链表实现
1首先定义一个类表链是由多个节点组成的节点是一个完整的结构提供给链表使用我们就可以把节点定义到内部类当中节点当中至少有两个域value的类型是intnext是用来存下一个节点的地址的所以next的类型应该是节点的类类型。 2整个链表有一个东西叫做head代表指向当前的链表属于链表的属性代表的是链表的头节点部分。head存的也是地址即类型为节点类型 3创建链表外部类里面定义一个方法用于链表的实现。首先有很多节点一个一个节点属于节点对象 此时的链表是这样的 问题一如何让第一个节点和第二个节点关联以此内推...... 当这个方法结束之后node12345就不会存地址了他们属于局部变量局部变量会被回收所以这个方法走完之后就没有这几个局部变量了
此时就形成了一个链表 测试类 4打印链表
问题一怎么从第一个节点走到第二个节点......
head head.next
问题二链表什么时候遍历完
head null 整个链表会遍历完。若head.next null 56不会打印
还是在外部类中定义一个方法用于遍历链表 测试类 5求链表的长度 还是在外部类当中定义一个方法定义一个count用来计数。 测试类 6头插法
我们插入的是一个节点实例化出来一个节点对象再把这个节点插入到头节点的前面head指向的位置应该指向插入节点的位置 node.next head
head node
两个顺序不可交换插入节点的时候一般首先绑后面 哪怕你所插入的链表是一个空链表这个代码也是可以完成的
即我们在创建链表的时候就可以不用上面createList方法枚举来创建了直接只要头插即可
测试类 7尾插法
首先还是需要实例化一个节点在需要找到当前链表的尾巴然后在把尾巴的next置为你所插入节点的地址即可 但是还需要考虑你的head为空的时候 测试类 8任意位置插入
可以把原链表做一个位置标记然后在某位置前面插入。例如在2位置前面插入一个节点。
首先要找到2位置的前一个节点cur只需要走2-1步。将插入节点的next改为1位置的next在把1位置的next改为所插入节点的地址。定义一个count来记录cur的位置 还要考虑其他问题
index 0—头插法 index size—尾插法
index 0 || index size 位置不合法抛异常即可 测试类 9判断某个关键字是否在链表当中 测试类 10删除第一次出现的关键字节点
首先要遍历链表是否你要删除的val。然后找到val节点的前一个节点cur不能走到val节点他是单向链表不能再回去了。在将你要删除的节点val定义为del将 cur.next del.next 或者写成cur.next cur.next。next 即可。 注意此代码不能删除头节点需要另外判断 测试类 11删除链表里面所有的key
要求对其本身就行修改
首先定义两个引用cur代表当前需要删除的节点prev代表cur节点的前驱节点判断ifcur.valkey如果成立让prev.next 等于cur节点的下一个节点cur.next再让cur往后走cur cur.nextprev还不能走因为永远要保持是cur的前驱。然后继续判断如果if条件不成立则需判断else的情况因为cur不是你要删除的key需要让perv走到curperv cur再让cur走向下一个节点cur cur.next。 但是这种情况没有考虑到头节点也需要删除。我们只需要判断一下头节点是否是你需要删除的key如果是删除头节点head head.next如果下个一个头节点还是你要删除的key则循环判断即可或者先让上面的代码走完在判断即可。 测试类 12清空链表
让每一个节点都被回收掉最直接的方式将head置为空意味着head不在引用这个对象即所有节点都会被回收。还要一种做法定义cur将cur.val置为空将cur.next置为空cur再往后走。但是要考虑头节点的val 3LinkedList的模拟实现
LinkedList是Java的一个集合类这个类可以当作链表来使用。前提是这个链表是一个双向链表
首先这种链表的节点至少包含3个域其中val是你存放的值next是下一个节点的地址prev是上一个节点的地址。同时LinkedList底层实现的时候还加了一个last代表永远指向链表的尾巴 3.1 无头双向链表实现
首先创建MyListedList类用来实现双向链表在定义一个内部类来创建一个节点在创建出headlast。 1实现双向链表的长度
定义一个cur来遍历链表定义一个count用来记录链表长度。 2打印链表的val 3查找链表是否包含关键key 4头插法
首先new一个节点将这个节点插入到当前链表的头部修改head.prvenode.next和headnode即可。
还有可能一个节点都没有即head和last都为空让head和last同时指向node即可 5尾插法
如果是空的来链表让head和last同时指向node即可
若不空只需要修改last.nextnode.prev和lastnode 6任意位置插入
现在不用在定义一个cur走到需要插入位置的前一个因为现在的节点里面包含next和prev直接走到所插入位置即可。 7删除关键字key
首先找到当前节点只需要将cur的前一个节点的next等于cur的后一个节点cur后一个节点的perv等于cur前的一个节点即可 但是呢这个代码是存在问题的。如果说我们在这要删除头节点12if条件成立走if里面的代码发现cur.prev是null会出现空指针异常。 那么我们在删除头节点时只需要将head往后走在将head的prev置为null即可。 那么此时又会出现一个问题如果说cur等于last删除尾巴节点上面else里面的代码第一条是没有问题的将cur的前驱的next置为null。 但是第二行代码就有问题cur的next为空空的前驱就会空指针异常。 所以在这种情况下就可以不执行这条代码让cur的前驱的next置为null以后让last等于last的前驱即可 还有一个问题当前链表只有一个节点 此时的代码对于当前链表是无法执行的走到红色框框里面的时候head的next为null即head等于null然后head的prev就会空指针异常
所以如果只有一个节点的情况下走到head head.next 的时候head为null说明只有一个节点让head的前驱置为null否则让last置为null。 8删除所有的值为key的节点
在remove方法中我们删除一个节点以后直接return出去我们只需要删完一个之后继续判断即可不return出去
9清空回收每一个节点
方法一直接将head和last置为null
方法二将每一个节点的valprevnext假如都是引用类型置为null再将head和last置为null因为把每一个节点置为null后head和last都还引用着对应的节点 到此我们自己实现了一个双向链表
4LinkedList的使用
4.1 什么是LinkedList
LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。
【说明】
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1)
这里时间复杂度O1指的是删除的时候不需要移动元素但是在找删除元素位置的时候需要遍历链表时间复杂度为ON。
5. LinkedList比较适合任意位置插入的场景
4.2 LinkedList的使用
写法 进入LinkedList的源码实现了这些接口 代表此时我们是以双向链表的形式去使用的
如果是Queue去引用LinkedList是当作队列去使用后序会讲的
1LinkedList的构造 带参数的构造方法
在顺序表中讲过这个称为通配符要么为E要么为E的子类。这个E就是你当前List所指定的泛型类型 还可以用ArrayList来进行传递因为ArrayListLinkedList都实现了Collection接口 2. LinkedList的其他常用方法介绍
add进入add的源码 默认是一个尾插法 3LinkedList的遍历
foreach循环 for循环 有一个问题如果说是在此时打印一个删除一个打印一个删除一个会输出什么 是不可以的因为size一直在变化把1打印之后有删掉1只剩下2和3两个元素且size变成2了再次打印的时候 i 等于1就是打印3即输出1和3。 如果把size变成一个固定的 我们发现出现了下标越界异常。
所以一边遍历一遍删必然会出现问题。当打印完0下标的元素时删掉0下标的元素0下标就会指向2元素位置当 i 等于2时要打印2下标的元素此时就会下标越界 使用迭代器遍历
iterator Listiterator iterator和Listiterator没有区别他们是父子关系只是Listiterator可以倒着打印
Iterator是不具备Previous这个类的要使用ListIterator 5ArrayList和LinkedList的区别
