数据结构—单向链表

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

单向链表

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

首先创建一个类用于存放节点的数据
/**
* 用于存放节点的数据
*/
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;
     }
 }

接着创建一个节点，封装节点数据和实现节点的功能（增加节点、删除节点、遍历节点）
/**
* 数据结构--单向链表
*/
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);
     }
 }