#单链表

单链表

1.单链表的定义

由于顺序表的插入删除操作需要移动大量的元素，影响了效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

2.单链表的实现

单链表每个节点由一个指针域和数据域组成
数据域中储存元素信息，指针域存放下一个节点低的地址，指向下一个节点
将每个节点连接起来组成链表

实现
.定义一个Node节点类，类中value存放元素的值，next存放地址
用类定义head头指针，指向为空
在此基础上添加构造方法

``public class linklist1 {
    Node head = null;

    private static class Node {
        int value;
        Node next;

        private Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
}

3.单链表插入

3.1前插

//前插
    public void addfirst(int value) {
        if (head == null) {
            head = new Node(value, null);
        }
        head = new Node(value, head);
    }

3.2后插

//后插
    public void addlast(int value) {
        Node p = findlast();
        if (p == null) {
            head = new Node(value, null);
        } else {
            p.next = new Node(value, null);
        }

    }

3.3元素任意位置的插入

//元素任意位置的插入
    public void insert(int index, int value) {

        Node p2 = findNode(index - 1);
        if (p2 == null) {
            System.out.println("有异常");
        }
        p2.next = new Node(value, p2.next);
    }

4单链表查找

4.1查找最后一个元素

//查找最后一个元素
    public Node findlast() {
        if (head == null) {
            return null;
        }
        Node p;
        for (p = head; p.next != null; p = p.next) {

        }
        return p;
    }

4.2查找下标为index的节点

//查找下标为index的节点
 public Node findNode(int index) {
        int i = 0;
        for (Node p1 = head; p1 != null; p1 = p1.next, i++) {
            if (i == index) {
                return p1;
            }
        }
        return null;
    }

5单链表删除

5.1删除第一个节点

//删除第一个节点
    public void removeFrirst() {
        if (head == null) {
            System.out.println("链表为空");
        }
        head = head.next;
    }

5.2删除特定下标的链表元素

//删除特定下标的链表元素
    public void remove(int index) {
        if (index == 0) {
            removeFrirst();//删除第一个元素
            return;
        }
        Node prev = findNode(index - 1);
        if (prev == null) {//前驱节点为空
            System.out.println("下标" + index + "异常");
        }
        Node removed = prev.next;
        if (removed == null) {//删除结点为空
            System.out.println("下标" + index + "异常");
        }
        prev.next = removed.next;
    }