[数据结构与算法]数据结构：java实现单链表的增删改查

?

? ? ? ? 与数组相似，链表也是一种线性数据结构。这里有一个例子：

? ? ? ? 正如你所看到的，链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

? ? ? ? 链表有两种类型：单链表和双链表。上面给出的例子是一个单链表，这里有一个双链表的例子：

? ? ? ? 代码实现：

package createlist;

class Node {
    int data;
    Node next = null;

    public Node() {
    }

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


public class CRUDList {

    private static Node head = null;
    private static Node tail = null;

    public static void main(String[] args) {
        for (int i = 1; i < 4; i++) {
            addList(i);
            //addFirstList(i);
        }
        System.out.println("链表的遍历：");
        printList(head);
        System.out.println("链表的长度：");
        System.out.println(getLength(head));
        System.out.println("查询链表(index = 1)：");
        System.out.println(getList(head, 1));
        System.out.println("修改链表（index =1）:");
        System.out.println(updateList(head, 1, 4));
        System.out.println("查看修改后的链表");
        printList(head);
        System.out.println("删除链表（index = 1）：");
        System.out.println(deleteList(1));
        printList(head);
        System.out.println("插入链表（index = 1）：");
        System.out.println(insertList(1, 6));
        printList(head);
    }

    //尾部插入法添加链表
    private static void addList(int data) {
        Node node = new Node(data);
        if (head == null) {//head为空时，把第一个节点作为头结点和尾结点
            head = node;
            tail = node;
        } else {//有了头结点之后，处理尾结点，把新增的节点放在尾结点的后面，尾结点向后移动一位（要一直处于链表的末尾处）
            tail.next = node;
            tail = tail.next;
        }
    }

    //头部插入法添加链表
    private static void addFirstList(int data){
        Node node = new Node(data);
        if(head == null){
            head = node;
        }else{
            node.next = head;
            head = node;
        }
    }

    //打印链表
    private static void printList(Node head) {
        if (head != null) {//链表不为空，循环遍历链表
            Node temp = head;//作为临时节点
            while (temp != null) {
                System.out.print(temp.data + "  ");
                temp = temp.next;//不断的后移，直到节点的下一位为空时，停止
            }
            System.out.println();
        } else {
            System.out.println("链表为空");
        }
    }

    //获取链表长度
    private static int getLength(Node head) {
        Node temp = head;//新增一个临时节点
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    //获取链表中第index个节点的值,索引无效返回-1
    private static int getList(Node head, int index) {
        if (index < 1 || index > getLength(head)) {
            System.out.print("索引无效：");
            return -1;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        return temp.data;
    }

    //修改链表中第index个节点的值,索引无效返回false
    private static boolean updateList(Node head, int index, int data) {
        if (index < 1 || index > getLength(head)) {
            System.out.print("索引无效：");
            return false;
        }
        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }
        temp.data = data;
        return true;
    }

    //删除链表中第index个节点的值,索引无效返回false
    private static boolean deleteList(int index) {
        if (index < 1 || index > getLength(head)) {
            System.out.print("索引无效：");
            return false;
        }
        if (index == 1) {
            //删除第一个节点时，首节点要后移
            head = head.next;
            return true;
        }
        Node temp = head;
        for (int i = 2; i < index; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return true;
    }

    //按索引插入一个节点
    private static boolean insertList(int index, int data) {
        if (index < 1 || index > getLength(head) + 1) {
            System.out.print("索引无效：");
            return false;
        }
        Node node = new Node(data);
        if (index == 1) {
            //插入的节点为首节点时
            node.next = head;
            head = node;
            return true;
        }
        Node temp = head;
        for (int i = 2; i < index; i++) {
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next = node;
        return true;
    }
}