CC双向链表,程序员的进阶之路 [复制链接]

1.概念的引入

相信大家都使用过各种集合来进行开发,但是较少的人会去研究其内部的存储原理和调用方法,今天我就来带大家一起学习数据结构算法:双向链表

首先我们先来了解什么是缓存,以及数据在内存中的存储方式.

1.缓存是什么

如果cup读取数据时,每次读取都是从内存再到硬盘读取,那么效率就太低了.所以可以预先把数据存到内存,然后cup下次从内存读取即可.

2.数据在内存中的存储方式

第1种.线性

所谓线性,就是内存是连续的举例ArrayList或者数组:我们知道,数组存储数据的时候,当你申请个大小,但是内存不足的时候就会导致内存不足而失败,或者即使你请求到了个,但是你只存3个数据,那么就浪费内存了=优点:查找数据快(好比几个好朋友乘火车,车票都连在一起就好找了)缺点:1,内存不足就失败;2.浪费内存(买了10张火车票,但是只有3个人乘车,那么就浪费了7张)

第2种.链接

内存是链接的(用于解决内存不足,解决线性(上面)问题的不足),比如不连续的空间也能存数据,比如买火车票,有火车票就卖给你,要几张卖几张,不连续位置的也卖.=优点:解决内存不足,解决内存浪费缺点:找人比较慢(票不连续,不一定在一个车厢)

节点的属性/p>

多个节点的内部构造/p>

代码思路

一.添加节点add(Objectobj)

1.Node节点属性:prev:存放前节点(相当于地址,地址就是指针,指针就是地址)data:Object各种数据next:存放下节点2.定义head,rear节点,当只有一个节点,那么head和rear同指一个节点3.节点添加的方法add(Objectobj)1.创建节点newNode(),即每加一个数据就创一个节点2.放数据3.把节点放入链表中1.如果头结点为空,那么头结点和尾节点都指向该节点2.如果头节点不为空1.往尾部添加原来的next指向新节点rear.next=note;新节点pre指向原节点,新节点也变成尾节点note.pre=rear(ps,有需求再设置往头部添加)4.toString方法[元素1,元素2,元素3]while(head!=null)if(head!=rear)append(head.data+,),***同temp代替head,否则会破坏head,影响后面的remove时head变才null了

添加节点过程图

二.删除节点数据remove(Objectobj)

注意判断该节点:1.是head2.还是rear3.还是中间某值1.查找数据所在节点find(Objectobj)1.从头结点开始遍历Notetemp=head2.while循环(temp!=null)如果找到是数据相同就停止判断数据相同的两标准equals和hashCode()否则temp=temp.next,下一个3.返回节点2.确实找到一个有该数据的节点if(delete!=null),然后有4种情况如果删的是以下的1.只有一个节点-既是头又是尾=头尾都设空2.是头结点=新节点变头节点,新节点的pre变null3.是尾节点=新节点变尾节点,新节点的next变null4.是其他=前一个节点的next=该节点的next后一个节点的pre=该节点的pre;

删除节点过程图

三.修改数据update(ObjectoldData,ObjectnewData)

1.找到data所在的节点find(oldData);2.如果找到的节点不为空,就把data变成newData.

四.容器中是否包含数据contains(Objectdata)

1.同理根据find(data)2.返回!note==null即可,不为空就是有包含

五.可以改成增强泛型版,把所有的Object改成T,就可以增强为选择和泛型非泛型了

双向链表的迭代器

直接增强for循环或者迭代就报错,因为没实现接口iterable,该接口是所有集合的顶级接口.

1.实现iterable

2.重写iterator方法

1.返回newIterator()

1.hasNext()方法

返回是否有数据Notetemp=head

temp==null;

2.next()方法

1.返回temp.data

2.temp指向下一个.temp=temp.next

3.remove()方法-不改变

3.ArrayList不给在增强for循环或者迭代器中做增删改,所以自己也可用设置,根据ArrayList的设计方法,同理,设置一个变量modCount.

1.在自己的链表类成员变量定义

2.在增删改的时候++;

3.在迭代器里面设置一个标记=modCount.(此时和前面的链表操作后的情况值的大小相同);

4.迭代过程中,如果再做了增删改的操作,就抛出异常.

写在next()方法的首位,if(标记改变),也抛出concurrentMotificationExaption(不能做增删改)