3.链表

链表是有序的列表，在内存的存储方式凌乱的，不需要占用一整块内存。他是以节点的方式存储，每一个节点除了需要自身的哪一个数据，还需要存储下一个节点的内存。它不一定是连续的存储结构，链表分为带节点的链表和没有头结点的链表。

带头结点的

使用带头结点的单项链表，实现增删改查。

1.增加节点

• 第一种方法在添加的时候在尾部

public class LianBiaoHaveHead {
    static class Node<T>{
        public T data;
        public Node<T> next;
        public Node(T data){
            this.data = data;
            next = null;
        }
    }
    private Node head  = new Node(-1);
    public void addNode(int num){
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        Node node = new Node(num);
        temp.next = node;
    }

    public static void main(String[] args) {
        LianBiaoHaveHead biao = new LianBiaoHaveHead();
        biao.addNode(0);
        biao.addNode(1);
        biao.addNode(2);
        biao.addNode(3);
        biao.addNode(4);
        biao.addNode(5);
        biao.addNode(6);
        System.out.println("===============================");
    }
}

• 第二种方式添加到时候将数据插入在指定的位置

    public void addNode(int num,int posi){
        int xx = 0;
        Node node = head;
        while (node.next!=null){

            if (xx == posi){
                break;
            }
            node = node.next;
            xx++;
        }
        Node nodeNext = node.next;
        node.next = new Node(num);
        node.next.next = nodeNext;
    }

2.修改节点

• 找到节点，然后将节点的值修改掉

    public void editNodeVal(int value,int targetVlaue){
        Node<Integer> node = head;
        while (node.next!=null){
            node = node.next;
            if (value == node.data){
                node.data = targetVlaue;
                break;  //加上就是只修改第一次 出现的，不修改就是所有的都修改
            }
        }
    }

3.删除节点

• 找到节点，但是我们需要记住前一个节点，前一个节点的下一个节点，是下一个的下一个。

    public void deleteNode(int value){
        Node<Integer> node = head;
        while (node.next!=null){
            if (value == node.next.data){
                break;
            }
            node = node.next;
        }
        node.next = node.next.next;
    }

不带头结点的

public class LianBiao {
    static class Node<T>{
        public T data;
        public Node<T> next;
        public Node(T data){
            this.data = data;
            next = null;
        }
    }

    private Node head;
    public void addNode(int num){
        if (this.head != null) {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            Node node = new Node(num);
            temp.next = node;
        }else {
            this.head = new Node(num);
        }
    }
}