数据结构1、栈及其Java实现2、队列及其Java实现3、链表3.1、链表的特点3.2、单向链表的操作及其Java实现3.2.1、单向链表的操作3.2.2、单向链表的Java实现3.3、双向链表及其Java实现3.4、循环链表4、散列表4.1、常用的构造散列函数4.2、Hash的应用数据结构指数据的存储、组织方式。有人认为“程序数据结构算法”。因此良好的数据结构对于程序的运行至关重要尤其是在复杂的系统中设计优秀的数据结构能够提高系统的灵活性和性能。在程序的设计和开发过程中难免需要使用各种各样的数据结构比如有时需要根据产品的特点定义自己的数据结构因此数据结构对于程序设计至关重要。本章将详细介绍常用的数据结构具体包括栈、队列、链表、二叉树、红黑树、散列表和位图。每种数据结构都有其特点下表便列举了常用的数据结构及其优缺点。1、栈及其Java实现栈Stack又名堆栈是允许在同一端进行插入和删除操作的特殊线性表。其中允许进行插入和删除操作的一端叫作栈顶Top另一端叫作栈底Bottom栈底固定栈顶浮动。栈中的元素个数为零时该栈叫作空栈。插入一般叫作进栈Push删除叫作退栈Pop。栈也叫作后进先出FILO-First In Last Out的线性表。具体的数据结构如图所示。要实现一个栈需要先实现以下核心方法。push()向栈中压入一个数据先入栈的数据在最下边。pop()弹出栈顶数据即移除栈顶数据。peek()返回当前的栈顶数据。栈的具体实现过程如下。1定义栈的数据结构packagehello.java.datastructure;/ 基于数组实现的顺序栈 paramE/publicclassStackE{privateObject[]datanull;privateintmaxSize0;//栈的容量privateinttop-1;//栈顶的指针//构造函数根据指定的size初始化栈Stack(){this(10);//默认的栈大小为10}Stack(intinitialSize){if(initialSize0){this.maxSizeinitialSize;datanewObject[initialSize];top-1;}else{thrownewRuntimeException(初始化大小不能小于0:initialSize);}}}以上代码定义了一个Stack的类用来存储栈的数据结构定义了一个数组data用来存储栈中的数据定义了maxSize表示栈的最大容量定义了top表示栈顶数据的指针定义了两个栈的构造函数在构造函数没有参数时默认构造一个大小为10的栈。2数据入栈向栈顶压入一个数据//进栈第1个元素top0publicbooleanpush(Ee){if(topmaxSize-1){thrownewRuntimeException(栈已满无法将元素入栈)}else{data[top]e;returntrue;}}以上代码定义了方法push()来向栈中压入数据在数据入栈前首先判断栈是否满了具体的判断依据为栈顶元素的指针位置等于栈的最大容量。注意这里使用maxSize -1是因为栈顶元素的指针是从0开始计算的。在栈有可用空间时使用data[top]e在栈顶top位置上方新压入一个元素并为top加1。3数据出栈从栈顶移除一个数据//弹出栈顶的元素publicEpop(){if(top-1){thrownewRuntimeException(栈为空);}else{return(E)data[top--];}}以上代码定义了方法pop()来从栈顶移除一个数据移除前先判断栈顶是否有数据如果有则通过data[top–]将栈顶数据移出并给top减1。4数据查询//查看栈顶元素但不移除publicEpeek(){if(top-1){thrownewRuntimeException(栈为空);}else{return(E)data[top];}}以上代码定义了方法peek()来取出栈顶的数据在取出栈顶的数据前先判断栈顶的元素是否存在如果存在则直接返回栈顶元素注意这里没有对栈顶的元素进行删除否则抛出异常。2、队列及其Java实现队列是一种只允许在表的前端进行删除操作且在表的后端进行插入操作的线性表。其中执行插入操作的端叫作队尾执行删除操作的端叫作队头。没有元素的队列叫作空队列在队列中插入一个队列元素叫作入队从队列中删除一个队列元素叫作出队。因为队列只允许在队头插入在队尾删除所以最早进入队列的元素将最先从队列中删除所以队列又叫作先进先出FIFO-first in first out线性表。具体的数据结构如图所示。要实现一个队列需要先实现以下核心方法。add()向队列的尾部加入一个元素入队先入队列的元素在最前边。poll()删除队列头部的元素出队。peek()取出队列头部的元素。队列的简单实现如下。1定义队列的数据结构packagehello.java.datastructure;publicclassQueueE{privateObject[]datanull;privateintmaxSize;//队列的容量privateintfront;//队列头允许删除privateintrear;//队列尾允许插入//构造函数默认的队列大小为10publicQueue(){this(10);}publicQueue(intinitialSize){if(initialSize0){this.maxSizeinitialSize;datanewObject[initialSize];frontrear0;}else{thrownewRuntimeException(初始化大小不能小于0:initialSize);}}}以上代码定义了一个名为Queue的队列数据结构并定义了用于存储队列数据的data数组、队列头位置标记front、队列尾位置标记rear、队列的容量maxSize。队列的默认长度为10在初始化时front的位置等于rear的位置都为0在有新的数据加入队列时front的值加1。2向队列插入数据//在队列的尾部插入数据publicbooleanadd(Ee){if(rearmaxSize){thrownewRuntimeException(队列已满无法插入新的元素);}else{data[rear]e;returntrue;}}以上代码定义了方法add()来向队列中插入数据在插入前先判断队列是否满了如果队列有空间则通过data[rear]e向队列的尾部加入数据并将队尾的指针位置加1。3取走队列中的数据//删除队列头部的元素出队publicEpoll(){if(empty()){thrownewRuntimeException(空队列异常);}else{Evalue(E)data[front];//临时保存队列front端的元素的值data[front]null;//释放队列front端的元素returnvalue;}}以上代码定义了方法poll()来取出队列头部的数据并将队列头部的数据设置为null以释放队列头部的位置最后返回队列头部的数据。4队列数据查询//取出队列头部的元素但不删除publicEpeek(){if(empty()){thrownewRuntimeException(空队列异常);}else{return(E)data[front];}}以上代码定义了方法peek()来访问并返回队列头部的数据。3、链表链表是由一系列节点链表中的每一个元素都叫作一个节点组成的数据结构节点可以在运行过程中动态生成。每个节点都包括两部分内容存储数据的数据域存储下一个节点地址的指针域。由于链表是随机存储数据的因此在链表中插入数据的时间复杂度为O(1)比在线性表和顺序表中插入的效率要高但在链表中查找一个节点时需要遍历链表中所有元素因此时间复杂度为O(n)而在线性表和顺序表中查找一个节点的时间复杂度分别为O(logn)和O(1)。链表有3种不同的类型单向链表、双向链表及循环链表。下面将以Java语言为基础分别介绍这3种不同的链表结构。3.1、链表的特点链表通过一组存储单元存储线性表中的数据元素这组存储单元可以是连续的也可以是不连续的。因此为了表示每个数据元素与其直接后继数据元素之间的逻辑关系对数据元素来说除了存储其本身的信息还需要存储直接后继数据元素的信息即直接后继数据元素的存储位置。由这两部分信息组成一个“节点”。链表数据结构的优点是插入快缺点是数据查询需要遍历整个链表效率慢。链表的具体数据结构如图所示。链表根据具体的实现又分为单向链表、双向链表和循环链表。3.2、单向链表的操作及其Java实现单向链表又称单链表是链表的一种其特点是链表的链接方向是单向的访问链表时要从头部开始顺序读取。单向链表是链表中结构最简单的。一个单向链表的节点Node可分为两部分第1部分为数据区data用于保存节点的数据信息第2部分为指针区用于存储下一个节点的地址最后一个节点的指针指向null。具体的数据结构如图所示。3.2.1、单向链表的操作1查找单向链表只可向一个方向遍历一般在查找一个节点时需要从单向链表的第1个节点开始依次访问下一个节点一直访问到需要的位置。2插入对于单向链表的插入只需将当前插入的节点设置为头节点将Next指针指向原来的头节点即可。插入后的结果如图所示。3删除对于单向链表的删除我们只需将该节点的上一个节点的Next指针指向该节点的下一个节点然后删除该节点即可。具体过程如图所示。3.2.2、单向链表的Java实现单向链表的Java实现如下。1定义单向链表的数据结构publicclassSingleLinkedList{privateintlength;//链表节点的个数privateNodehead;//头节点publicSingleLinkedList(){size0;headnull;}//链表的每个节点的数据结构描述类privateclassNode{privateObjectdata;//每个节点的数据privateNodenext;//每个节点指向下一个节点的连接publicNode(Objectdata){this.datadata;}}}以上代码定义了名为SingleLinkedList的单向链表并定义了length表示链表的大小head表示链表的头部名为Node的内部类表示链表的节点数据结构在Node中有data和next两个属性分别表示该链表节点的数据和下一个节点的连接。这样就完成了对链表数据结构的定义。2插入单向链表数据//在链表头添加元素publicObjectaddHead(Objectobj){NodenewHeadnewNode(obj);//step 1 定义新节点if(length0){//step 2 如果链表为空则将该节点设置为头部节点headnewHead;}else{//step 3: 设置当前节点为头部节点并将当前节点的下一个节点指向原来的头部节点headnewHead;newHead.nexthead;}length;//step 4链表长度1returnobj;}以上代码定义了方法addHead()来向链表的头部加入节点。具体操作为首先定义一个节点接着判断链表的长度是否为0如果为0则表示链表为空链表直接将该节点设置为链表的头部节点如果节点的长度不为0则将当前插入的节点设置为头节点将当前插入节点的Next指针指向原头节点即可最后给链表的长度加1。3删除单向链表数据//删除指定的元素删除成功则返回truepublicbooleandelete(Objectvalue){if(length0){returnfalse;}Nodecurrenthead;Nodeprevioushead;while(current.data!value){if(current.nextnull){returnfalse;}else{previouscurrent;currentcurrent.next;}}//如果删除的节点是头节点if(currenthead){headcurrent.next;length--;}else{//删除的节点不是头节点previous.nextcurrent.next;length--;}returntrue;}以上代码定义了方法delete()来删除单向链表中的数据具体的删除操作为首先判断链表的长度如果链表长度为0则说明链表为空即不包含任何元素直接返回false如果链表不为空则通过while循环找到要删除的元素如果要删除的节点是头节点则需要把要删除的节点的下一个节点指定为头节点删除该节点把节点长度减1如果删除的节点不是头节点则将该节点的上一个节点的Next指针指向该节点的下一个节点删除该节点并把节点长度减1。4单向链表数据查询//查找指定的元素若找到了则返回节点Node找不到则返回nullpublicNodefind(Objectobj){Nodecurrenthead;inttempSizelength;while(tempSize0){if(obj.equals(current.data)){returncurrent;}else{currentcurrent.next;}tempSize--;}returnnull;}以上代码定义了名为find()的单向链表节点查询方法。该方法很简单定义了一个while循环来查找数据如果当前数据和要查找的数据相同则返回该数据如果不同则将当前节点的下一个节点设置为当前节点沿着当前节点向前继续寻找。这里将tempSize减1的目的是控制while循环的条件在tempSize为0时表示遍历完了整个链表还没找到该数据这时返回null。3.3、双向链表及其Java实现在双向链表的每个数据节点中都有两个指针分别指向其直接后继和直接前驱节点。所以从双向链表中的任意一个节点开始都可以很方便地访问它的直接前驱节点和直接后继节点。具体的数据结构如图所示。双向链表和单向链表的不同之处在于单向链表除数据项外只定义了一个Next指针指向下一个节点而双向链表定义了Prev和Next两个指针分别指向上一个节点和下一个节点这样我们便可以从两个方向遍历并处理节点的数据了。双向链表的Java实现代码如下1定义双向链表的数据结构publicclassTwoWayLinkedList{privateNodehead;//表示链表头privateNodetail;//表示链表尾privateintlength;//表示链表的长度privateclassNode{privateObjectdata;privateNodenext;privateNodeprev;publicNode(Objectdata){this.datadata;}}publicTwoWayLinkedList(){size0;headnull;tailnull;}}以上代码定义了一个名为TwoWayLinkedList的双向链表的数据结构其中定义了head表示链表头tail表示链表尾length表示链表长度Node表示链表的节点链表的节点包含data、prev、next分别表示节点数据、上一个节点和下一个节点。这样双向链表的数据结构就定义好了。2在链表头部增加节点//在链表头部增加节点publicvoidaddHead(Objectvalue){NodenewNodenewNode(value);if(length0){headnewNode;tailnewNode;length;}else{head.prevnewNode;newNode.nexthead;headnewNode;length;}}以上代码定义了addHead()来向链表的头部加入数据具体操作为首先新建一个节点然后判断链表的长度如果链表的长度为0则说明链表是空链表将链表的头部和尾部均设置为当前节点并将链表长度加1即可如果链表不是空链表则将原链表头部的上一个节点设置当前节点将当前节点的下一个节点设置为原链表头的节点将链表的头部节点设置为当前节点这样就完成了双向链表的头部节点的插入最后需要将链表的长度加1。3在链表尾部增加节点//在链表尾部增加节点publicvoidaddTail(Objectvalue){NodenewNodenewNode(value);if(length0){headnewNode;tailnewNode;length;}else{newNode.prevtail;tail.nextnewNode;tailnewNode;length;}}以上代码定义了名为addTail()的方法来给链表尾部加入数据具体操作为首先新建一个节点然后判断链表的长度如果链表的长度为0则说明链表是空链表将链表的头部和尾部均设置为当前节点并将链表长度加1即可如果链表长度不为空则将当前节点的上一个节点设置为原尾部节点将原来的尾部节点的下一个节点设置为当前节点将尾部节点设置为新的节点这样就完成了双向链表尾部的插入最后需要把链表的长度加1。4删除链表的头部节点//删除链表的头部节点publicNodedeleteHead(){Nodetemphead;if(length!0){headhead.next;head.prevnull;length--;returntemp;}else{returnnull}}以上代码定义了一个名为deleteHead()的方法来删除链表的头部节点具体操作为首先定义一个临时节点来存储当前头部节点然后判断节点的长度如果节点的长度为0则直接返回null如果节点的长度不为0则将当前头部节点设置为原头部节点的下一个节点将头部节点的上一个节点设置为null然后删除该节点最后将节点的长度减1。5删除链表的尾部节点//删除链表的尾部节点publicNodedeleteTail(){Nodetemptail;if(length!0){tailtail.prev;tail.nextnull;length--;returntemp;}else{returnnull}}以上代码定义了一个deleteTail()方法来删除链表尾部的节点具体操作为首先定义一个临时节点来存储当前尾部节点然后判断节点的长度如果节点的长度为0则直接返回null如果节点的长度不为0则将当前尾部节点设置为原尾部节点的上一个节点将尾部节点的下一个节点设置为null然后删除该节点最后将节点的长度减1。3.4、循环链表循环链表的链式存储结构的特点是表中最后一个节点的指针域指向头节点整个链表形成一个环。具体的数据结构如图所示。循环节点的实现和单向链表十分相似只是在链表中尾部元素的Next指针不再是null而是指向头部节点其他实现和单向链表相同。4、散列表散列表Hash Table也叫作哈希表是根据数据的关键码值Key-Value对对数据进行存取的数据结构。散列表通过映射函数把关键码值映射到表中的一个位置来加快查找。这个映射函数叫作散列函数存放记录的数组叫作散列表。给定表M存在函数f(key)对任意给定的关键字key代入函数后若能得到包含该关键字的记录在表中的地址则称表M为散列表称函数f(key)为散列函数。具体的数据结构如图所示。散列表算法通过在数据元素的存储位置和它的关键字可用key表示之间建立一个确定的对应关系使每个关键字和散列表中唯一的存储位置相对应。在查找时只需根据这个对应关系找到给定关键字在散列表中的位置即可真正做到一次查找命中。4.1、常用的构造散列函数常用的构造散列函数如下。直接定址法取关键字或关键字的某个线性函数值为散列地址即h(key) key或h(key) a×key b其中a和b为常数。平方取值法取关键字平方后的中间几位为散列地址。折叠法将关键字分割成位数相同的几部分然后取这几部分的叠加和作为散列地址。除留余数法取关键字被某个不大于散列表长度m的数p除后所得的余数为散列地址即h(key) key/p (p≤m)。随机数法选择一个随机函数取关键字的随机函数值作为其散列地址即h(key)random(key)。Java HashCode实现在Java中计算HashCode 的公式为f(key) s[0]× 31n-1s[1]× 31n-2…s[n-1]。具体实现如下publicinthashCode(){inthhash;if(h0value.length0){charval[]value;for(inti0;ivalue.length;i){h31 hval[i];}hashh;}returnh;}4.2、Hash的应用Hash主要用于用信息安全加密和快速查询的应用场景。信息安全Hash主要被用于信息安全领域的加密算法中它把一些不同长度的信息转化成杂乱的128位编码这些编码的值叫作Hash值。也可以说Hash就是找到一种数据内容和数据存放地址之间的映射关系。快速查找散列表又叫作散列是一种更加快捷的查找技术。基于列表集合查找的一般做法是从集合中拿出一个元素看它是否与当前数据相等如果不相等则缩小范围继续查找。而散列表是完全另外一种思路在知道key值以后就可以直接计算这个元素在集合中的位置不需要一次又一次的遍历查找。
Java面试——数据结构（一）
数据结构1、栈及其Java实现2、队列及其Java实现3、链表3.1、链表的特点3.2、单向链表的操作及其Java实现3.2.1、单向链表的操作3.2.2、单向链表的Java实现3.3、双向链表及其Java实现3.4、循环链表4、散列表4.1、常用的构造散列函数4.2、Hash的应用数据结构指数据的存储、组织方式。有人认为“程序数据结构算法”。因此良好的数据结构对于程序的运行至关重要尤其是在复杂的系统中设计优秀的数据结构能够提高系统的灵活性和性能。在程序的设计和开发过程中难免需要使用各种各样的数据结构比如有时需要根据产品的特点定义自己的数据结构因此数据结构对于程序设计至关重要。本章将详细介绍常用的数据结构具体包括栈、队列、链表、二叉树、红黑树、散列表和位图。每种数据结构都有其特点下表便列举了常用的数据结构及其优缺点。1、栈及其Java实现栈Stack又名堆栈是允许在同一端进行插入和删除操作的特殊线性表。其中允许进行插入和删除操作的一端叫作栈顶Top另一端叫作栈底Bottom栈底固定栈顶浮动。栈中的元素个数为零时该栈叫作空栈。插入一般叫作进栈Push删除叫作退栈Pop。栈也叫作后进先出FILO-First In Last Out的线性表。具体的数据结构如图所示。要实现一个栈需要先实现以下核心方法。push()向栈中压入一个数据先入栈的数据在最下边。pop()弹出栈顶数据即移除栈顶数据。peek()返回当前的栈顶数据。栈的具体实现过程如下。1定义栈的数据结构packagehello.java.datastructure;/ 基于数组实现的顺序栈 paramE/publicclassStackE{privateObject[]datanull;privateintmaxSize0;//栈的容量privateinttop-1;//栈顶的指针//构造函数根据指定的size初始化栈Stack(){this(10);//默认的栈大小为10}Stack(intinitialSize){if(initialSize0){this.maxSizeinitialSize;datanewObject[initialSize];top-1;}else{thrownewRuntimeException(初始化大小不能小于0:initialSize);}}}以上代码定义了一个Stack的类用来存储栈的数据结构定义了一个数组data用来存储栈中的数据定义了maxSize表示栈的最大容量定义了top表示栈顶数据的指针定义了两个栈的构造函数在构造函数没有参数时默认构造一个大小为10的栈。2数据入栈向栈顶压入一个数据//进栈第1个元素top0publicbooleanpush(Ee){if(topmaxSize-1){thrownewRuntimeException(栈已满无法将元素入栈)}else{data[top]e;returntrue;}}以上代码定义了方法push()来向栈中压入数据在数据入栈前首先判断栈是否满了具体的判断依据为栈顶元素的指针位置等于栈的最大容量。注意这里使用maxSize -1是因为栈顶元素的指针是从0开始计算的。在栈有可用空间时使用data[top]e在栈顶top位置上方新压入一个元素并为top加1。3数据出栈从栈顶移除一个数据//弹出栈顶的元素publicEpop(){if(top-1){thrownewRuntimeException(栈为空);}else{return(E)data[top--];}}以上代码定义了方法pop()来从栈顶移除一个数据移除前先判断栈顶是否有数据如果有则通过data[top–]将栈顶数据移出并给top减1。4数据查询//查看栈顶元素但不移除publicEpeek(){if(top-1){thrownewRuntimeException(栈为空);}else{return(E)data[top];}}以上代码定义了方法peek()来取出栈顶的数据在取出栈顶的数据前先判断栈顶的元素是否存在如果存在则直接返回栈顶元素注意这里没有对栈顶的元素进行删除否则抛出异常。2、队列及其Java实现队列是一种只允许在表的前端进行删除操作且在表的后端进行插入操作的线性表。其中执行插入操作的端叫作队尾执行删除操作的端叫作队头。没有元素的队列叫作空队列在队列中插入一个队列元素叫作入队从队列中删除一个队列元素叫作出队。因为队列只允许在队头插入在队尾删除所以最早进入队列的元素将最先从队列中删除所以队列又叫作先进先出FIFO-first in first out线性表。具体的数据结构如图所示。要实现一个队列需要先实现以下核心方法。add()向队列的尾部加入一个元素入队先入队列的元素在最前边。poll()删除队列头部的元素出队。peek()取出队列头部的元素。队列的简单实现如下。1定义队列的数据结构packagehello.java.datastructure;publicclassQueueE{privateObject[]datanull;privateintmaxSize;//队列的容量privateintfront;//队列头允许删除privateintrear;//队列尾允许插入//构造函数默认的队列大小为10publicQueue(){this(10);}publicQueue(intinitialSize){if(initialSize0){this.maxSizeinitialSize;datanewObject[initialSize];frontrear0;}else{thrownewRuntimeException(初始化大小不能小于0:initialSize);}}}以上代码定义了一个名为Queue的队列数据结构并定义了用于存储队列数据的data数组、队列头位置标记front、队列尾位置标记rear、队列的容量maxSize。队列的默认长度为10在初始化时front的位置等于rear的位置都为0在有新的数据加入队列时front的值加1。2向队列插入数据//在队列的尾部插入数据publicbooleanadd(Ee){if(rearmaxSize){thrownewRuntimeException(队列已满无法插入新的元素);}else{data[rear]e;returntrue;}}以上代码定义了方法add()来向队列中插入数据在插入前先判断队列是否满了如果队列有空间则通过data[rear]e向队列的尾部加入数据并将队尾的指针位置加1。3取走队列中的数据//删除队列头部的元素出队publicEpoll(){if(empty()){thrownewRuntimeException(空队列异常);}else{Evalue(E)data[front];//临时保存队列front端的元素的值data[front]null;//释放队列front端的元素returnvalue;}}以上代码定义了方法poll()来取出队列头部的数据并将队列头部的数据设置为null以释放队列头部的位置最后返回队列头部的数据。4队列数据查询//取出队列头部的元素但不删除publicEpeek(){if(empty()){thrownewRuntimeException(空队列异常);}else{return(E)data[front];}}以上代码定义了方法peek()来访问并返回队列头部的数据。3、链表链表是由一系列节点链表中的每一个元素都叫作一个节点组成的数据结构节点可以在运行过程中动态生成。每个节点都包括两部分内容存储数据的数据域存储下一个节点地址的指针域。由于链表是随机存储数据的因此在链表中插入数据的时间复杂度为O(1)比在线性表和顺序表中插入的效率要高但在链表中查找一个节点时需要遍历链表中所有元素因此时间复杂度为O(n)而在线性表和顺序表中查找一个节点的时间复杂度分别为O(logn)和O(1)。链表有3种不同的类型单向链表、双向链表及循环链表。下面将以Java语言为基础分别介绍这3种不同的链表结构。3.1、链表的特点链表通过一组存储单元存储线性表中的数据元素这组存储单元可以是连续的也可以是不连续的。因此为了表示每个数据元素与其直接后继数据元素之间的逻辑关系对数据元素来说除了存储其本身的信息还需要存储直接后继数据元素的信息即直接后继数据元素的存储位置。由这两部分信息组成一个“节点”。链表数据结构的优点是插入快缺点是数据查询需要遍历整个链表效率慢。链表的具体数据结构如图所示。链表根据具体的实现又分为单向链表、双向链表和循环链表。3.2、单向链表的操作及其Java实现单向链表又称单链表是链表的一种其特点是链表的链接方向是单向的访问链表时要从头部开始顺序读取。单向链表是链表中结构最简单的。一个单向链表的节点Node可分为两部分第1部分为数据区data用于保存节点的数据信息第2部分为指针区用于存储下一个节点的地址最后一个节点的指针指向null。具体的数据结构如图所示。3.2.1、单向链表的操作1查找单向链表只可向一个方向遍历一般在查找一个节点时需要从单向链表的第1个节点开始依次访问下一个节点一直访问到需要的位置。2插入对于单向链表的插入只需将当前插入的节点设置为头节点将Next指针指向原来的头节点即可。插入后的结果如图所示。3删除对于单向链表的删除我们只需将该节点的上一个节点的Next指针指向该节点的下一个节点然后删除该节点即可。具体过程如图所示。3.2.2、单向链表的Java实现单向链表的Java实现如下。1定义单向链表的数据结构publicclassSingleLinkedList{privateintlength;//链表节点的个数privateNodehead;//头节点publicSingleLinkedList(){size0;headnull;}//链表的每个节点的数据结构描述类privateclassNode{privateObjectdata;//每个节点的数据privateNodenext;//每个节点指向下一个节点的连接publicNode(Objectdata){this.datadata;}}}以上代码定义了名为SingleLinkedList的单向链表并定义了length表示链表的大小head表示链表的头部名为Node的内部类表示链表的节点数据结构在Node中有data和next两个属性分别表示该链表节点的数据和下一个节点的连接。这样就完成了对链表数据结构的定义。2插入单向链表数据//在链表头添加元素publicObjectaddHead(Objectobj){NodenewHeadnewNode(obj);//step 1 定义新节点if(length0){//step 2 如果链表为空则将该节点设置为头部节点headnewHead;}else{//step 3: 设置当前节点为头部节点并将当前节点的下一个节点指向原来的头部节点headnewHead;newHead.nexthead;}length;//step 4链表长度1returnobj;}以上代码定义了方法addHead()来向链表的头部加入节点。具体操作为首先定义一个节点接着判断链表的长度是否为0如果为0则表示链表为空链表直接将该节点设置为链表的头部节点如果节点的长度不为0则将当前插入的节点设置为头节点将当前插入节点的Next指针指向原头节点即可最后给链表的长度加1。3删除单向链表数据//删除指定的元素删除成功则返回truepublicbooleandelete(Objectvalue){if(length0){returnfalse;}Nodecurrenthead;Nodeprevioushead;while(current.data!value){if(current.nextnull){returnfalse;}else{previouscurrent;currentcurrent.next;}}//如果删除的节点是头节点if(currenthead){headcurrent.next;length--;}else{//删除的节点不是头节点previous.nextcurrent.next;length--;}returntrue;}以上代码定义了方法delete()来删除单向链表中的数据具体的删除操作为首先判断链表的长度如果链表长度为0则说明链表为空即不包含任何元素直接返回false如果链表不为空则通过while循环找到要删除的元素如果要删除的节点是头节点则需要把要删除的节点的下一个节点指定为头节点删除该节点把节点长度减1如果删除的节点不是头节点则将该节点的上一个节点的Next指针指向该节点的下一个节点删除该节点并把节点长度减1。4单向链表数据查询//查找指定的元素若找到了则返回节点Node找不到则返回nullpublicNodefind(Objectobj){Nodecurrenthead;inttempSizelength;while(tempSize0){if(obj.equals(current.data)){returncurrent;}else{currentcurrent.next;}tempSize--;}returnnull;}以上代码定义了名为find()的单向链表节点查询方法。该方法很简单定义了一个while循环来查找数据如果当前数据和要查找的数据相同则返回该数据如果不同则将当前节点的下一个节点设置为当前节点沿着当前节点向前继续寻找。这里将tempSize减1的目的是控制while循环的条件在tempSize为0时表示遍历完了整个链表还没找到该数据这时返回null。3.3、双向链表及其Java实现在双向链表的每个数据节点中都有两个指针分别指向其直接后继和直接前驱节点。所以从双向链表中的任意一个节点开始都可以很方便地访问它的直接前驱节点和直接后继节点。具体的数据结构如图所示。双向链表和单向链表的不同之处在于单向链表除数据项外只定义了一个Next指针指向下一个节点而双向链表定义了Prev和Next两个指针分别指向上一个节点和下一个节点这样我们便可以从两个方向遍历并处理节点的数据了。双向链表的Java实现代码如下1定义双向链表的数据结构publicclassTwoWayLinkedList{privateNodehead;//表示链表头privateNodetail;//表示链表尾privateintlength;//表示链表的长度privateclassNode{privateObjectdata;privateNodenext;privateNodeprev;publicNode(Objectdata){this.datadata;}}publicTwoWayLinkedList(){size0;headnull;tailnull;}}以上代码定义了一个名为TwoWayLinkedList的双向链表的数据结构其中定义了head表示链表头tail表示链表尾length表示链表长度Node表示链表的节点链表的节点包含data、prev、next分别表示节点数据、上一个节点和下一个节点。这样双向链表的数据结构就定义好了。2在链表头部增加节点//在链表头部增加节点publicvoidaddHead(Objectvalue){NodenewNodenewNode(value);if(length0){headnewNode;tailnewNode;length;}else{head.prevnewNode;newNode.nexthead;headnewNode;length;}}以上代码定义了addHead()来向链表的头部加入数据具体操作为首先新建一个节点然后判断链表的长度如果链表的长度为0则说明链表是空链表将链表的头部和尾部均设置为当前节点并将链表长度加1即可如果链表不是空链表则将原链表头部的上一个节点设置当前节点将当前节点的下一个节点设置为原链表头的节点将链表的头部节点设置为当前节点这样就完成了双向链表的头部节点的插入最后需要将链表的长度加1。3在链表尾部增加节点//在链表尾部增加节点publicvoidaddTail(Objectvalue){NodenewNodenewNode(value);if(length0){headnewNode;tailnewNode;length;}else{newNode.prevtail;tail.nextnewNode;tailnewNode;length;}}以上代码定义了名为addTail()的方法来给链表尾部加入数据具体操作为首先新建一个节点然后判断链表的长度如果链表的长度为0则说明链表是空链表将链表的头部和尾部均设置为当前节点并将链表长度加1即可如果链表长度不为空则将当前节点的上一个节点设置为原尾部节点将原来的尾部节点的下一个节点设置为当前节点将尾部节点设置为新的节点这样就完成了双向链表尾部的插入最后需要把链表的长度加1。4删除链表的头部节点//删除链表的头部节点publicNodedeleteHead(){Nodetemphead;if(length!0){headhead.next;head.prevnull;length--;returntemp;}else{returnnull}}以上代码定义了一个名为deleteHead()的方法来删除链表的头部节点具体操作为首先定义一个临时节点来存储当前头部节点然后判断节点的长度如果节点的长度为0则直接返回null如果节点的长度不为0则将当前头部节点设置为原头部节点的下一个节点将头部节点的上一个节点设置为null然后删除该节点最后将节点的长度减1。5删除链表的尾部节点//删除链表的尾部节点publicNodedeleteTail(){Nodetemptail;if(length!0){tailtail.prev;tail.nextnull;length--;returntemp;}else{returnnull}}以上代码定义了一个deleteTail()方法来删除链表尾部的节点具体操作为首先定义一个临时节点来存储当前尾部节点然后判断节点的长度如果节点的长度为0则直接返回null如果节点的长度不为0则将当前尾部节点设置为原尾部节点的上一个节点将尾部节点的下一个节点设置为null然后删除该节点最后将节点的长度减1。3.4、循环链表循环链表的链式存储结构的特点是表中最后一个节点的指针域指向头节点整个链表形成一个环。具体的数据结构如图所示。循环节点的实现和单向链表十分相似只是在链表中尾部元素的Next指针不再是null而是指向头部节点其他实现和单向链表相同。4、散列表散列表Hash Table也叫作哈希表是根据数据的关键码值Key-Value对对数据进行存取的数据结构。散列表通过映射函数把关键码值映射到表中的一个位置来加快查找。这个映射函数叫作散列函数存放记录的数组叫作散列表。给定表M存在函数f(key)对任意给定的关键字key代入函数后若能得到包含该关键字的记录在表中的地址则称表M为散列表称函数f(key)为散列函数。具体的数据结构如图所示。散列表算法通过在数据元素的存储位置和它的关键字可用key表示之间建立一个确定的对应关系使每个关键字和散列表中唯一的存储位置相对应。在查找时只需根据这个对应关系找到给定关键字在散列表中的位置即可真正做到一次查找命中。4.1、常用的构造散列函数常用的构造散列函数如下。直接定址法取关键字或关键字的某个线性函数值为散列地址即h(key) key或h(key) a×key b其中a和b为常数。平方取值法取关键字平方后的中间几位为散列地址。折叠法将关键字分割成位数相同的几部分然后取这几部分的叠加和作为散列地址。除留余数法取关键字被某个不大于散列表长度m的数p除后所得的余数为散列地址即h(key) key/p (p≤m)。随机数法选择一个随机函数取关键字的随机函数值作为其散列地址即h(key)random(key)。Java HashCode实现在Java中计算HashCode 的公式为f(key) s[0]× 31n-1s[1]× 31n-2…s[n-1]。具体实现如下publicinthashCode(){inthhash;if(h0value.length0){charval[]value;for(inti0;ivalue.length;i){h31 hval[i];}hashh;}returnh;}4.2、Hash的应用Hash主要用于用信息安全加密和快速查询的应用场景。信息安全Hash主要被用于信息安全领域的加密算法中它把一些不同长度的信息转化成杂乱的128位编码这些编码的值叫作Hash值。也可以说Hash就是找到一种数据内容和数据存放地址之间的映射关系。快速查找散列表又叫作散列是一种更加快捷的查找技术。基于列表集合查找的一般做法是从集合中拿出一个元素看它是否与当前数据相等如果不相等则缩小范围继续查找。而散列表是完全另外一种思路在知道key值以后就可以直接计算这个元素在集合中的位置不需要一次又一次的遍历查找。