數(shù)據(jù)結(jié)構(gòu)—單向鏈表

為了鞏固自己的基礎(chǔ)知識，這次就用 Java 來寫一個(gè)單向鏈表。
問：什么是單向鏈表？
首先鏈表是數(shù)據(jù)結(jié)構(gòu)中的其中一種結(jié)構(gòu)，是鏈表結(jié)構(gòu)。鏈表結(jié)構(gòu)有單向鏈表（單鏈表）和雙向鏈表（雙鏈表）。這次要實(shí)現(xiàn)的就是單向鏈表，單向鏈表是什么樣子的？看下圖：

這個(gè)單向鏈表有5個(gè)節(jié)點(diǎn)，其中第一個(gè)節(jié)點(diǎn)被稱為頭節(jié)點(diǎn)（Head），它指向下一個(gè)節(jié)點(diǎn)。
這里的Data 不是Data節(jié)點(diǎn)，Data 是保存在節(jié)點(diǎn)中一些數(shù)據(jù)，鏈表中除了 Head 節(jié)點(diǎn)和 Tail 節(jié)點(diǎn)之外，其余的節(jié)點(diǎn)我們不作稱呼。
在鏈表的最后被稱為尾節(jié)點(diǎn)（Tail）它指向Null，就是沒有任何節(jié)點(diǎn)了。
指針就是指向當(dāng)前節(jié)點(diǎn)的位置（地址），可以把它當(dāng)做是索引或書簽來看待。

1. 首先創(chuàng)建一個(gè)類用于存放節(jié)點(diǎn)的數(shù)據(jù)
   /**
   * 用于存放節(jié)點(diǎn)的數(shù)據(jù)
   */
   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. 接著創(chuàng)建一個(gè)節(jié)點(diǎn)，封裝節(jié)點(diǎn)數(shù)據(jù)和實(shí)現(xiàn)節(jié)點(diǎn)的功能（增加節(jié)點(diǎn)、刪除節(jié)點(diǎn)、遍歷節(jié)點(diǎn)）
   /**
   * 數(shù)據(jù)結(jié)構(gòu)--單向鏈表
   */
   public class NodeDemo
   {
   private NodeData nodeData;
   private NodeDemo nodeNext;

        /**
         * 在鏈尾添加一個(gè)節(jié)點(diǎn)
         * @param head     傳入一個(gè)鏈表節(jié)點(diǎn)
         * @param nodeData 傳入一個(gè)數(shù)據(jù)對象，它會被節(jié)點(diǎn)封裝起來
         * @return head 返回一個(gè)單向鏈表
         */
        public NodeDemo addNode(NodeDemo head, NodeData nodeData)
        {
            if (head == null || nodeData == null) return null;
   
            //1.內(nèi)存不足無法添加節(jié)點(diǎn)
            NodeDemo node;
            if ((node = new NodeDemo()) == null)
            {
                System.out.println("內(nèi)存不足無法添加節(jié)點(diǎn)");
                return head;
            }
   
            //2.保存節(jié)點(diǎn)
            node.nodeData = nodeData;
            node.nodeNext = null;
   
            /**
             * 3.添加節(jié)點(diǎn)
             * 如果當(dāng)前節(jié)點(diǎn)是鏈尾，則直接在鏈尾添加節(jié)點(diǎn)
             * 否側(cè)循環(huán)找到當(dāng)前節(jié)點(diǎn)的鏈尾，然后在鏈尾添加節(jié)點(diǎn)
             */
            if (head.nodeNext == null)
            {
                head.nodeNext = node;
                return head;
            }
   
            while (head.nodeNext != null)
                head = head.nodeNext;
   
            head.nodeNext = node;
   
            return head;
        }
   
        /**
         * 用于刪除一個(gè)指定的節(jié)點(diǎn)
         *
         * @param head 傳入一個(gè)鏈表節(jié)點(diǎn)
         * @param no   傳入一個(gè)序號，刪除這個(gè)序號的節(jié)點(diǎn)
         * @return 返回一個(gè)單向鏈表
         */
        public NodeDemo delNode(NodeDemo head, int no)
        {
            if (head == null || no == 0) return null;
   
            NodeDemo tmp = null;
            while (head.nodeNext != null)
            {
                /**
                 * tmp 存放上次遍歷到的節(jié)點(diǎn)
                 * head 存放當(dāng)前遍歷到的節(jié)點(diǎn)
                 */
                tmp = head;
                head = head.nodeNext;
   
                /**
                 * 如果找到要?jiǎng)h除的節(jié)點(diǎn)
                 * 上次變量到的節(jié)點(diǎn) tmp 指向 head.nodeNext
                 * 刪除 head 節(jié)點(diǎn)
                 */
                if (head.nodeData.getId() == no)
                {
                    tmp.nodeNext = head.nodeNext;
                    head = null;
                    break;
                }
            }
   
            return tmp;
        }
   
        /**
         * 用于打印每個(gè)節(jié)點(diǎn)的數(shù)據(jù)
         *
         * @param head 傳入一個(gè)單向鏈表
         */
        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.向鏈表添加節(jié)點(diǎn)
            for (int i = 1; i <= 10; i++)
                demo.addNode(demo, new NodeData(i, "第" + i + "個(gè)節(jié)點(diǎn)"));
   
            demo.print(demo);
            System.out.println();
   
            //2.刪除鏈表中的節(jié)點(diǎn)
            demo.delNode(demo, 5);
            demo.print(demo);
        }
    }