用Java写单向链表

数据结构—单向链表

为了巩固自己的基础知识,这次就用 Java 来写一个单向链表。
问:什么是单向链表?
首先链表是数据结构中的其中一种结构,是链表结构。链表结构有单向链表(单链表)和双向链表(双链表)。这次要实现的就是单向链表,单向链表是什么样子的?看下图:

单向链表

这个单向链表有5个节点,其中第一个节点被称为头节点(Head),它指向下一个节点。
这里的Data 不是Data节点,Data 是保存在节点中一些数据,链表中除了 Head 节点和 Tail 节点之外,其余的节点我们不作称呼。
在链表的最后被称为尾节点(Tail)它指向Null,就是没有任何节点了。
指针就是指向当前节点的位置(地址),可以把它当做是索引或书签来看待。

  1. 首先创建一个类用于存放节点的数据
    /**
    * 用于存放节点的数据
    */
    public class NodeData
    {
    private int id;
    private String data;

         public NodeData(int id, String data)
         {
             this.id = id;
             this.data = data;
         }
    
         @Override
         public String toString()
         {
             return "NodeData{" +
                     "id=" + id +
                     ", data='" + data + '\'' +
                     '}';
         }
    
         public int getId()
         {
             return id;
         }
    
         public void setId(int id)
         {
             this.id = id;
         }
    
         public String getData()
         {
             return data;
         }
    
         public void setData(String data)
         {
             this.data = data;
         }
     }
    
  2. 接着创建一个节点,封装节点数据和实现节点的功能(增加节点、删除节点、遍历节点)
    /**
    * 数据结构--单向链表
    */
    public class NodeDemo
    {
    private NodeData nodeData;
    private NodeDemo nodeNext;

         /**
          * 在链尾添加一个节点
          * @param head     传入一个链表节点
          * @param nodeData 传入一个数据对象,它会被节点封装起来
          * @return head 返回一个单向链表
          */
         public NodeDemo addNode(NodeDemo head, NodeData nodeData)
         {
             if (head == null || nodeData == null) return null;
    
             //1.内存不足无法添加节点
             NodeDemo node;
             if ((node = new NodeDemo()) == null)
             {
                 System.out.println("内存不足无法添加节点");
                 return head;
             }
    
             //2.保存节点
             node.nodeData = nodeData;
             node.nodeNext = null;
    
             /**
              * 3.添加节点
              * 如果当前节点是链尾,则直接在链尾添加节点
              * 否侧循环找到当前节点的链尾,然后在链尾添加节点
              */
             if (head.nodeNext == null)
             {
                 head.nodeNext = node;
                 return head;
             }
    
             while (head.nodeNext != null)
                 head = head.nodeNext;
    
             head.nodeNext = node;
    
             return head;
         }
    
         /**
          * 用于删除一个指定的节点
          *
          * @param head 传入一个链表节点
          * @param no   传入一个序号,删除这个序号的节点
          * @return 返回一个单向链表
          */
         public NodeDemo delNode(NodeDemo head, int no)
         {
             if (head == null || no == 0) return null;
    
             NodeDemo tmp = null;
             while (head.nodeNext != null)
             {
                 /**
                  * tmp 存放上次遍历到的节点
                  * head 存放当前遍历到的节点
                  */
                 tmp = head;
                 head = head.nodeNext;
    
                 /**
                  * 如果找到要删除的节点
                  * 上次变量到的节点 tmp 指向 head.nodeNext
                  * 删除 head 节点
                  */
                 if (head.nodeData.getId() == no)
                 {
                     tmp.nodeNext = head.nodeNext;
                     head = null;
                     break;
                 }
             }
    
             return tmp;
         }
    
         /**
          * 用于打印每个节点的数据
          *
          * @param head 传入一个单向链表
          */
         public void print(NodeDemo head)
         {
             if (head == null) return;
    
             if (head.nodeNext == null)
                 System.out.println("这是空链表");
             else
             {
                 while (head.nodeNext != null)
                 {
                     head = head.nodeNext;
                     System.out.println(head.nodeData.toString());
                 }
             }
         }
    
         public static void main(String[] args)
         {
             NodeDemo demo = new NodeDemo();
    
             //1.向链表添加节点
             for (int i = 1; i <= 10; i++)
                 demo.addNode(demo, new NodeData(i, "第" + i + "个节点"));
    
             demo.print(demo);
             System.out.println();
    
             //2.删除链表中的节点
             demo.delNode(demo, 5);
             demo.print(demo);
         }
     }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,767评论 18 399
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,986评论 19 139
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • 一. Java基础部分.................................................
    wy_sure阅读 3,838评论 0 11
  • //leetcode中还有花样链表题,这里几个例子,冰山一角 求单链表中结点的个数----时间复杂度O(n)这是最...
    暗黑破坏球嘿哈阅读 1,540评论 0 6