目录

1,ArrayList的缺陷

2,链表

2.1 链表的概念及结构

2.2 链表的实现

2.2.1 无头单向非循环链表实现

3,LinkedList的模拟实现

3.1 无头双向链表实现

4,LinkedList的使用

4.1 什么是LinkedList

4.2 LinkedList的使用

5,ArrayList和LinkedList的区别


1,ArrayList的缺陷

当在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的类型是int,next是用来存下一个节点的地址的,所以next的类型应该是节点的类类型。

2,整个链表有一个东西叫做head,代表指向当前的链表,属于链表的属性,代表的是链表的头节点部分。head存的也是地址,即类型为节点类型

3,创建链表,外部类里面定义一个方法,用于链表的实现。首先有很多节点,一个一个节点属于节点对象

此时的链表是这样的

问题一:如何让第一个节点和第二个节点关联,以此内推......

当这个方法结束之后,node1,2,3,4,5就不会存地址了,他们属于局部变量,局部变量会被回收,所以这个方法走完之后,就没有这几个局部变量了

此时,就形成了一个链表

测试类:

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节点的前驱节点),判断if(cur.val==key),如果成立,让prev.next 等于cur节点的下一个节点(cur.next),再让cur往后走(cur = cur.next),prev还不能走,因为永远要保持是cur的前驱。然后继续判断,如果if条件不成立,则需判断else的情况,因为cur不是你要删除的key,需要让perv走到cur(perv = cur),再让cur走向下一个节点(cur = cur.next)。

但是这种情况没有考虑到头节点也需要删除。我们只需要判断一下头节点是否是你需要删除的key,如果是,删除头节点(head = head.next),如果下个一个头节点还是你要删除的key,则循环判断即可,或者先让上面的代码走完在判断即可。

测试类:

12,清空链表

让每一个节点都被回收掉,最直接的方式将head置为空,意味着head不在引用这个对象,即所有节点都会被回收。还要一种做法,定义cur,将cur.val置为空,将cur.next置为空,cur再往后走。但是要考虑头节点的val

3,LinkedList的模拟实现

LinkedList是Java的一个集合类,这个类可以当作链表来使用。前提是这个链表是一个双向链表

首先这种链表的节点,至少包含3个域,其中val是你存放的值,next是下一个节点的地址,prev是上一个节点的地址。同时LinkedList底层实现的时候,还加了一个last,代表永远指向链表的尾巴 

3.1 无头双向链表实现

首先创建MyListedList类用来实现双向链表,在定义一个内部类来创建一个节点,在创建出head,last。

1,实现双向链表的长度

定义一个cur来遍历链表,定义一个count用来记录链表长度。

2,打印链表的val

3,查找链表是否包含关键key

4,头插法

首先new一个节点,将这个节点插入到当前链表的头部,修改head.prve,node.next和head=node即可。

还有可能一个节点都没有,即head和last都为空,让head和last同时指向node即可

5,尾插法

如果是空的来链表,让head和last同时指向node即可

若不空,只需要修改last.next,node.prev和last=node

6,任意位置插入

现在不用在定义一个cur走到需要插入位置的前一个,因为现在的节点里面包含next和prev,直接走到所插入位置即可。

7,删除关键字key

首先找到当前节点,只需要将cur的前一个节点的next等于cur的后一个节点,cur后一个节点的perv等于cur前的一个节点即可 

但是呢,这个代码是存在问题的。如果说我们在这要删除头节点12,if条件成立,走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

方法二:将每一个节点的val,prev,next(假如都是引用类型)置为null,再将head和last置为null,因为把每一个节点置为null后,head和last都还引用着对应的节点

到此,我们自己实现了一个双向链表

4,LinkedList的使用

4.1 什么是LinkedList

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

【说明】:

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)

这里时间复杂度O(1)指的是删除的时候不需要移动元素,但是在找删除元素位置的时候,需要遍历链表,时间复杂度为O(N)。

5. LinkedList比较适合任意位置插入的场景

4.2 LinkedList的使用

写法:

进入LinkedList的源码:实现了这些接口

代表此时我们是以双向链表的形式去使用的

如果是Queue去引用LinkedList,是当作队列去使用(后序会讲的)

1,LinkedList的构造

带参数的构造方法:

在顺序表中讲过,这个?称为通配符,要么为E,要么为E的子类。这个E就是你当前List所指定的泛型类型

还可以用ArrayList来进行传递,因为ArrayList,LinkedList都实现了Collection接口

2. LinkedList的其他常用方法介绍

add:进入add的源码

默认是一个尾插法

3,LinkedList的遍历

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

5,ArrayList和LinkedList的区别

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部