单向链表介绍

单向链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素，其节点主要由元素和指向下一节点的指针组成。本文仅为个人学习的记录，仅供参考。

相关操作介绍

本文主要实现以下操作：

• 链表的生成
• 判断链表是否为空
• 链表的清空

• 节点的插入

  • 头插法
  • 尾插法
• 节点的删除
• 返回第i个结点
• 返回链表的节点个数
• 根据给定值，返回该值在链表出现的第一个位置

代码

节点类

package linklist;

class SingleNode {
    public Integer data;
    public SingleNode next;

    public SingleNode() {
    }

    public SingleNode(int data) {
        this.data = data;
    }

    public SingleNode(int data, SingleNode next) {
        this.data = data;
        this.next = next;
    }
}

测试类

package linklist;

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(arr);
        System.out.println(mySingleLinkedList);
        mySingleLinkedList.addLastNode(10);
        System.out.println(mySingleLinkedList);
        mySingleLinkedList.addFirstNode(0);
        System.out.println(mySingleLinkedList);
        System.out.println(mySingleLinkedList.getNodeCount());
        System.out.println(mySingleLinkedList.findNodeIndex(6));
        System.out.println(mySingleLinkedList.getValue(1));
        mySingleLinkedList.delNode(9);
        System.out.println(mySingleLinkedList);
        System.out.println(mySingleLinkedList.isNull());
        mySingleLinkedList.clear();
        System.out.println(mySingleLinkedList.isNull());
    }
}

链表类

package linklist;

public class MySingleLinkedList {

    private SingleNode head;//头节点


    public MySingleLinkedList() {
        head = new SingleNode();
    }

    /**
     * 通过数组创建链表
     *
     * @param arr 数组
     */
    public MySingleLinkedList(int[] arr) {
        head = new SingleNode();
        for (int a : arr) {
            addLastNode(a);
        }
    }

    /**
     * 尾插法添加节点
     *
     * @param value 值
     */
    public void addLastNode(int value) {
        SingleNode node = head;
        //遍历链表
        while (node.next != null) {
            node = node.next;
        }
        node.next = new SingleNode(value);//添加节点
    }

    /**
     * 头插法添加节点
     *
     * @param value 值
     */
    public void addFirstNode(int value) {
        SingleNode node = head;
        node.next = new SingleNode(value, node.next);
    }

    /**
     * 判断链表是否为空
     *
     * @return 是否为空
     */
    public boolean isNull() {
        return head.next == null;
    }

    /**
     * 清空链表
     */
    public void clear() {
        head.next = null;
    }

    /**
     * 删除节点
     *
     * @param index 要删除的节点索引
     * @return 是否删除成功
     */
    public boolean delNode(int index) {
        SingleNode node = head;
        //当索引不满足条件时直接返回失败
        if (index < 1) {
            return false;
        } else if (index == 1) {
            head.next = head.next.next;
            return true;
        }
        int i = 0;
        //遍历链表，查找要删除的节点并删除
        while (node.next != null) {
            i++;
            if (i == index) {
                node.next = node.next.next;
                return true;
            }
            node = node.next;
        }
        return false;
    }

    /**
     * 获取某个节点数据
     *
     * @param index 索引
     * @return 该节点数据，不存在返回null
     */
    public Integer getValue(int index) {
        SingleNode node = head.next;
        int i = 0;
        while (node.next != null) {
            i++;
            if (i == index) {
                return node.data;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 获取节点个数
     *
     * @return 节点个数
     */
    public int getNodeCount() {
        SingleNode node = head.next;
        int count = 1;
        while (node.next != null) {
            node = node.next;
            count++;
        }
        return count;
    }

    /**
     * 获取某个值的第一个所在节点索引
     *
     * @param value 值
     * @return 节点索引，不存在返回-1
     */
    public int findNodeIndex(int value) {
        SingleNode node = head.next;
        if (node.data == value) {
            return 1;
        }
        int index = 1;
        while (node.next != null) {
            index++;
            node = node.next;
            if (node.data == value) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        if (head.next == null) {
            return "null";
        }
        SingleNode node = head.next;
        String str = "";
        while (node.next != null) {
            str += node.data.toString() + ",";
            node = node.next;
        }
        str += node.data.toString();
        return "MySingleLinkedList{" +
                str +
                '}';
    }
}