实现自己的单链表

单链表的定义

1. 单链表是由节点组成

2. 每个节点由值域和指针域组成

3. 头节点就是链表中第一个节点，初始值为null

4. 尾节点就是链表中的最后一个节点

具体代码

import java.util.ArrayList;

public class MyList {
    private class Node {
        int val;
        Node next = null;

        Node(int n) {
            this.val = n;
        }
    }

    //构造函数创建新的链表
    MyList() {
    }

    private Node head;
    private Node last;
    private int length = 0;

    /**
     * 增加节点
     *
     * @param n
     */
    public void add(int n) {
        Node node = new Node(n);
        if (head == null) {
            head = node;
            last = node;
            length++;
        } else {
            last.next = node;
            last = node;
            length++;
        }
    }

    /**
     * 链表的长度
     *
     * @return length
     */
    public int size() {
        return length;
    }

    /**
     * 遍历链表
     */
    public ArrayList<Integer> traverse() {
        ArrayList<Integer> arr = new ArrayList<>();
        if (head != null) {
            Node temp = head;
            while (temp != null) {
                arr.add(temp.val);
                temp = temp.next;
            }
        }
        return arr;
    }

    /**
     * 修改链表的值
     */
    public void changeNode(int index, int value) {
        Node temp = head;
        while (index > 0 && temp != null) {
            temp = temp.next;
            index--;
        }
        temp.val = value;
    }

    /**
     * 删除该节点 index
     */
    public void deleteNode(int index) {
        Node prev = head;
        if (index == 1) {
            head = null;
        } else {
            //找到删除节点的前一个结点，使其指向删除节点的下一个节点
            while (index > 2 && prev != null) {
                prev = prev.next;
                index--;
            }
            Node next = prev.next.next;
            prev.next = next;
        }
        length--;
    }

    /**
     * 增加节点
     */
    public void insert(int index, int value) {
        Node temp = head;
        while (index > 1 && temp != null) {
            temp = temp.next;
            index--;
        }
        temp.val = value;
        length++;
    }

    /**
     * 反转链表
     */
    public void reverseList() {
        if (head == null) {
            return;
        }
        Node prev = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        head = prev;
    }
}

参考资料:

单链表-维基百科

Q.E.D.