2019-05-22：请用 Java 实现一个简单的单链表？

[Moosphan]

结点类代码如下：

public class Node {
    public Node next;
    // 存放的数据
    public int data;
    public Node(int data) {
        this.data = data;
    }
}

补充：要求可以实现该单链表的 CRUD 操作。好了，show us your code😄

[whatshappen]

哦？给你个链接，嘿嘿
https://github.com/whatshappen/leetcode-practice/blob/master/code/5001-%E5%AE%9E%E7%8E%B0%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84.md

[guosen]

定义链表：
public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

基本操作：
public class SingleLinkedList {
    /**链表的头结点*/
    ListNode head = null;

    /**
     * 链表添加结点:
     * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
     * @param data
     */
    public void addNode(int data){
        ListNode newNode = new ListNode(data);
        if(head == null){
            head = newNode;
            return;
        }
        ListNode temp = head;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = newNode;
    }

    /**
     * 链表删除结点:
     * 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
     * @param index
     * @return
     */
    public boolean deleteNode(int index){
        if(index<1 || index>length()){//待删除结点不存在
            return false;
        }
        if(index == 1){//删除头结点
            head = head.next;
            return true;
        }
        ListNode preNode = head;
        ListNode curNode = preNode.next;
        int i = 1;
        while(curNode != null){
            if(i==index){//寻找到待删除结点
                preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
                return true;
            }
            //当先结点和前结点同时向后移
            preNode = preNode.next;
            curNode = curNode.next;
            i++;
        }
        return true;
    }


    /**
     * 求链表的长度
     * @return
     */
    public int length(){
        int length = 0;
        ListNode curNode = head;
        while(curNode != null){
            length++;
            curNode = curNode.next;
        }
        return length;
    }

    /**
     * 打印结点
     */
    public void printLink(){
        ListNode curNode = head;
        while(curNode !=null){
            System.out.print(curNode.val+" ");
            curNode = curNode.next;
        }
        System.out.println();
    }

    /**
     * 查找正数第k个元素
     */
    public ListNode findNode(int k){
        if(k<1 || k>length()){//不合法的k
            return null;
        }
        ListNode temp = head;
        for(int i = 0; i<k-1; i++){
            temp = temp.next;
        }
        return temp;
    }
    public static  void  main(String[]args){
        SingleLinkedList myLinkedList = new SingleLinkedList();
        //添加链表结点
        myLinkedList.addNode(9);
        myLinkedList.addNode(8);
        myLinkedList.addNode(6);
        myLinkedList.addNode(3);
        myLinkedList.addNode(5);
        //打印链表
        myLinkedList.printLink();
        System.out.println("链表结点个数为：" + myLinkedList.length());
        myLinkedList.deleteNode(3);
        myLinkedList.printLink();
    }
}

[gabyallen]

收获了

[LvKang-insist]

学习

[yangfanggang]

正好最近在看LinkedList的源码

可参考 LinkedList源码分析

[Moosphan]

单链表的结点类：

public class Node {
    // 当前节点的下一个结点变量
    public Node next;
    // 存放的数据
    public int data;
    // 构造器
    public Node(int data) {
        this.data = data;
    }
}

单链表的简单实现：

/**
 * 我是一只贪吃蛇
 */
public class SimpleLinkedList {
    private Node head;
    private static final int HEAD_NODE_DATA = -1;

    public SimpleLinkedList() {
        head = new Node(HEAD_NODE_DATA);
    }

    /**
     * 获取当前单链表的长度
     * @return 链表的长度
     */
    public int length() {
        Node temp = head;
        if (temp == null) {
            return 0;
        }
        int size = 1;
        while (temp.next != null) {
            temp = temp.next;
            size = size + 1;
        }
        return size;
    }

    /**
     * 直接在链表内插入一个结点
     * 插入位置：链表最后面
     * @param node 插入的结点
     */
    public void addNode(Node node) {
        Node currentNode = head;
        if (currentNode == null) {
            throw new IllegalArgumentException("the SimpleLinkedList is null, it should have nodes at least one.");
        }
        // 遍历单链表，找到当前链表的最后一个结点
        while (currentNode.next != null) {
            currentNode = currentNode.next;
        }
        // 将目标结点插入到末位结点的后面
        currentNode.next = node;
    }

    /**
     * 通过已知数据在链表内插入一个结点
     * 插入位置：链表最后面
     * @param data 结点中存储的数据
     */
    public void addNode(int data) {
        Node node = new Node(data);
        Node currentNode = head;
        if (currentNode == null) {
            throw new IllegalArgumentException("the SimpleLinkedList is null, it should have nodes at least one.");
        }
        while (currentNode.next != null) {
            currentNode = currentNode.next;
        }
        currentNode.next = node;
        //System.out.print(node.data);
    }

    /**
     * 在链表的指定位置插入一个结点
     * @param index 插入位置
     * @param data  结点数据
     */
    public void addNode(int index, int data) {
        Node node = new Node(data);
        // 如果链表不为空，至少需要有一个结点
        if (index < 1 || index > length() + 1) {
            throw new IllegalArgumentException("the node position inserted is invalid, please check it up again.");
        }
        // 从第1个位置开始(head位置为0)
        int count = 1;
        Node currentNode = head;
        while (currentNode.next != null) {
            if (index == count++) {
                // 找到插入点
                // 现将当前插入点的node的后续链排到目标node之后
                node.next = currentNode.next;
                // 再将目标node插入到当前node的后面
                currentNode.next = node;
                System.out.print(node.data);
                return;
            }
            currentNode = currentNode.next;
        }
        // 当前插入的位置是链表的末尾
        if (index == length()) {
            addNode(node);
        }
    }

    /**
     * 移除指定位置的结点
     * @param index 位置
     */
    public void removeNode(int index) {
        // 不能少于一个结点，并且不能超过总长度
        if (index < 1 || index > length() -1 ) {
            throw new IllegalArgumentException("the node position removed is invalid, please check it up again.");
        }
        int count = 1;
        Node current = head;
        while (current.next != null) {
            // 找到删除位置
            if (index == count++) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }

    }

    /**
     * 获取某个位置的结点
     * @param location 目标结点的位置
     * @return 目标结点
     */
    public Node get(int location) {
        Node node = null;
        if (location < 1 || location > length() -1 ) {
            throw new IllegalArgumentException("the node position queried is invalid, please check it up again.");
        }
        int count = 1;
        Node current = head;
        while (current.next != null) {
            // 找到目标位置
            if (location == count++) {
                node = current.next;
            }
            current = current.next;
        }
        return node;
    }


    /**
     * 打印链表内所有数据
     * @return 链表数据
     */
    public String toString() {
        Node temp = head.next;
        StringBuilder message = new StringBuilder();
        while (temp != null) {
            message.append(temp.data).append("\t");
            temp = temp.next;
        }
        return message.toString();
    }

}

简单测试：

public class Main {

    public static void main(String[] args) {

        SimpleLinkedList list = new SimpleLinkedList();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4, 8);
        System.out.println(list.toString());
        list.removeNode(2);
        System.out.println(list.toString());
        System.out.println(list.get(3).data);

    }
    
}

最终运行结果：

1	2	3	8	
1	3	8	
8

Process finished with exit code 0

[hy20160705]

哦？给你个链接，嘿嘿
https://github.com/whatshappen/leetcode-practice/blob/master/code/5001-%E5%AE%9E%E7%8E%B0%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84.md

public void addAtIndex(int index, int val) { if (size < index) {//角标越界 return; //throw new ArrayIndexOutOfBoundsException(); } Node newNode = new Node(val); if (index == 0) { addAtHead(val); return; } Node temp = this.node; for (int i = 1; i <= size; i++) { if (i == index) { newNode.next = temp.next; temp.next = newNode; /********************这里是不是可以加一个 break *******************/ } temp = temp.next; } size++; }

[Jeremy-linkt]

 /**
     * 查找正数第k个元素
     */
    public ListNode findNode(int k){
        if(k<1 || k>length()){//不合法的k
            return null;
        }
        ListNode temp = head;
        for(int i = 0; i<k-1; i++){
            temp = temp.next;
        }
        return temp;
    }

/**
     * 获取某个位置的结点
     * @param location 目标结点的位置
     * @return 目标结点
     */
    public Node get(int location) {
        Node node = null;
        if (location < 1 || location > length() -1 ) {
            throw new IllegalArgumentException("the node position queried is invalid, please check it up again.");
        }
        int count = 1;
        Node current = head;
        while (current.next != null) {
            // 找到目标位置
            if (location == count++) {
                node = current.next;
            }
            current = current.next;
        }
        return node;
    }

上面两份代码，参数都是1开始算吗？如果是，那应该是if (location < 1 || location > length())，但一般是下标是从0开始吧，if (location < 0 || location > length() - 1)