数据结构—单向链表

为了巩固自己的基础知识，这次就用 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);
        }
    }