java链表在链表的头部添加一个学生的记录

来源：蜘蛛抓取(WebSpider) 时间：2018-10-06 14:47 标签： java链表

自定义实现链表很简单，只需要明白链表是什么样子的数据结构。

下图表示一种单向列表。其中指针first指向队头，last指向队尾，curr指向当前读的数据。

下面是我的实现代码，很简单，明白上述结构后，关键是构造一个内部类，里面包含一个指向下一个元素的对象（指向下一个元素的指针）

* 指向list中最后一个元素 * 指向list中第一个元素 * 指向当前读取的元素 * 往链表中添加数据（队尾添加数据） * 移除链表中的数据（队头移除） * 再次从头开始读取数据

实践一下，看能不能使用

 链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。链表在数据结构中是基础，也是重要的知识点，这里讲下Java 中链表的实现，

JAVA 链表操作：单链表和双链表

二、链表实现原理和必要性

　　链表是一种比较常用的数据结构，链表虽然保存比较复杂，但是在查询时候比较便捷，在多种计算机语言都相应的应用，链表有多种类别，文章针对单链表和双链表进行分析。链表中数据就像被一个链条串联一起，轻易的可以实现数据的访问。

二、链表实现原理和必要性

　　这里只分析单链表和双链表。链表的实现过程是有些许复杂的，但是会带来许多好处。比如现在网购时代到来，商家发快递一般会将商品包装在盒子里并写上地址信息，快递公司就可以通过盒子上的信息找到买家，商品完整到达。如果没有盒子的保护，有可能在途中商品受损。而链表就好比那个写了地址信息的盒子，既保护了商品信息，同时又写好了物流信息。链表之中存在一个HEAD节点，类似“火车头”，只要找到相应HEAD节点，就可以对链表进行操作。此次分析中，HEAD节点只是做数据头，不保存有效数据。

　　单链表的实现原理如图： 

 

 
 
 * 链表插入，每次往末端插入
 
 * 插入链表指定位置pos，从1开始,而pos大于size则插入链表末端
 
 // 1、找到要插入pos位置节点和前节点
 
 
 * 指定链表的节点pos，删除对应节点。方式：找到要删除节点的前后节点，进行删除。从1开始
 // 1、找到要删除节点的前后节点
 
 
 * 指定链表的节点pos，修改对应节点。 从1开始
 * 找到指定链表的节点pos，从1开始
 
 
 
 
 
 
 
 

  

  

    
 


  

  

     双链表实现类：
  

  

    
 
 * 链表插入，每次往末端插入
 
 
 
 * 插入链表指定位置pos，从1开始,而pos大于size则插入链表末端
 
 // 1、找到要插入位置pos节点，插入pos节点当前位置
 
 
 * 指定链表的节点pos，删除对应节点，从1开始
 // 1、找到要删除位置pos节点
 * 指定链表的节点pos，修改对应节点。 从1开始
 
 * 找到指定链表的节点pos，从1开始
 
 
 
 
 
 
 


  

  

    感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
  



                            

                                                    

                                

  

    最近在回顾数据结构与算法，有部分的算法题用到了栈的思想，说起栈又不得不说链表了。数组和链表都是线性存储结构的基础，栈和队列都是线性存储结构的应用～
  

  

    本文主要讲解单链表的基础知识点，做一个简单的入门～如果有错的地方请指正
  

  

  

    说起链表，我们先提一下数组吧，跟数组比较一下就很理解链表这种存储结构了。
  

  

  

    数组我们无论是C、Java都会学过：
  

  
    
    
  • 数组是一种连续存储线性结构，元素类型相同，大小相等
    
    • 
  

  
    
    
  • 事先必须知道数组的长度
    
    • 
    
  • 插入删除元素的效率很低
    
    • 
  

  

  

    看完了数组，回到我们的链表：
  

  
    
    
  • 链表是离散存储线性结构
    
    • 
  

  

    

      n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。
    

  

  

    链表相关术语介绍，我还是通过上面那个图来说明吧：
  

  

    确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推导出来了～
  

  
    
    
      
      
    • 一个节点指向下一个节点
      
      • 
    
    
    
      
      
    • 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
      
      • 
    
    
  

  

    操作链表要时刻记住的是：
  

  
    
    
  • 
      节点中指针域指向的就是一个节点了！
    
    • 
  

  

  

    首先，我们定义一个类作为节点
  

  

    为了操作方便我就直接定义成public了。
  

  

 
 //指针域，指向下一个节点
 

  

    3.1创建链表(增加节点)
  

  
 
 

 
 

  
    
    
  • 
      即使头节点.next为null，不走while循环，也是将头节点与新节点连接的(我已经将head节点初始化过了，因此没必要判断头节点是否为null)～
    
    • 
  

  
 

  

 //初始化要加入的节点
 // 已经包括了头节点.next为null的情况了～


  
 

  

  
 

 上面我们已经编写了增加方法，现在遍历一下看一下是否正确～～～
 
 

 从首节点开始，不断往后面找，直到后面的节点没有数据：
 
 

  

 
 //临时节点，从首节点开始
 

 


 

 
 


 

  

  
 

  
    
    
  1. 
      插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入～
    
    2. 
    
  2. 
      找到想要插入的位置的上一个节点就可以了～
    
    3. 
  

  
 

  

 //首先需要判断指定位置是否合法，
 //临时节点，从头节点开始
 //记录遍历的当前位置
 //初始化要插入的节点
 //找到上一个节点的位置了
 //temp表示的是上一个节点
 //将原本由上一个节点的指向交由插入的节点来指向
 //将上一个节点的指针域指向要插入的节点
 

  

  
 

 获取链表的长度就很简单了，遍历一下，每得到一个节点+1即可～
 
 

  

 //临时节点，从首节点开始
 

  

  
 

 删除某个位置上的节点其实是和插入节点很像的， 同样都要找到上一个节点。将上一个节点的指针域改变一下，就可以删除了～
 
 

  

 //首先需要判断指定位置是否合法，
 //临时节点，从头节点开始
 //记录遍历的当前位置
 //找到上一个节点的位置了
 //temp表示的是上一个节点
 //将想要删除的节点存储一下
 //想要删除节点的下一个节点交由上一个节点来控制
 //Java会回收它，设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦～)
 

  

  
 

 前面已经讲过了8种的排序算法了【】，这次挑简单的冒泡排序吧(其实我是想写快速排序的，尝试了一下感觉有点难.....)
 
 

  

 

  

    3.7找到链表中倒数第k个节点
  

  
 
 

 这个算法挺有趣的：设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
 
 

  

 * 找到链表中倒数第k个节点(设置两个指针p1、p2，让p2比p1快k个节点，同时向后遍历，当p2为空，则p1为倒数第k个节点
 // 只要p2为null，那么p1就是倒数第k个节点了
 

  

    3.8删除链表重复数据
  

  
 
 

 跟冒泡排序差不多，只要它相等，就能删除了～
 
 

  

 * 删除链表重复数据(跟冒泡差不多，等于删除就是了)
 //临时节点，(从首节点开始-->真正有数据的节点)
 //当前节点(首节点)的下一个节点
 //将下一个节点删除(当前节点指向下下个节点)
 

  

    3.9查询链表的中间节点
  

  
 
 

 这个算法也挺有趣的：一个每次走1步，一个每次走两步，走两步的遍历完，然后走一步的指针，那就是中间节点
 
 

  

 * 查询单链表的中间节点
 // 一个走一步，一个走两步，直到为null，走一步的到达的就是中间节点
 

  

    3.10通过递归从尾到头输出单链表
  

  
 
 

  

 * 通过递归从尾到头输出单链表
 

  

  
 

  

 

 
 


 

 


 

  
 

  

    

      理解链表本身并不难，但做相关的操作就弄得头疼，head.next next next next ....(算法这方面我还是薄弱啊..脑子不够用了.....)写了两天就写了这么点东西...
    

  

  
 

 操作一个链表只需要知道它的头指针就可以做任何操作了
 
 

 PS：每个人的实现都会不一样，所以一些小细节难免会有些变动，也没有固定的写法，能够实现对应的功能即可～
 
 

 
 

  
 

  

    

      如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y
    

  

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 java链表 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐