基本介绍

链表是有序列表，但是在内存中是存储如下。

如上图：

1）链表是以节点的方式来存储，是链式存储。
2）每个节点包含data域，next域：指向下一个节点。
3）链表的各个节点不一定是连续存储。
4）链表分带头节点的链表和没有头节点的链表。

单链表（带头节点）逻辑结构示意图如下

增删改查

增

方法一：

先创建一个head头节点。
后面每添加一个节点，就直接加入到链表的最后。
通过一个辅助节点变量，帮助遍历整个链表。

方法二：

根据编号的顺序添加：
    首先找到新添加节点的位置，通过辅助节点完成添加

删

先找到需要删除节点的前一个节点temp；
temp.next = temp.next.next;
被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收；

改

通过遍历找到要修改的节点进行修改

案例代码

package com.linkedlist;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        Node nodeOne = new Node(1, "张三");
        Node nodeTwo = new Node(2, "李四");
        Node nodeThree = new Node(3, "王五");

        SingleLinkedList linkedList = new SingleLinkedList();
//        linkedList.add(nodeOne);
//        linkedList.add(nodeThree);
//        linkedList.add(nodeTwo);

//        linkedList.addOrderByAsc(nodeThree);
//        linkedList.addOrderByAsc(nodeTwo);
//        linkedList.addOrderByAsc(nodeOne);
//        linkedList.list();
//        System.out.println("-------------------");
//        linkedList.update(new Node(2,"黄"));
//        linkedList.list();

        linkedList.addOrderByAsc(nodeThree);
        linkedList.addOrderByAsc(nodeTwo);
        linkedList.addOrderByAsc(nodeOne);

        linkedList.del(1);
        linkedList.del(2);
        linkedList.del(3);

        linkedList.list();

    }
}

class SingleLinkedList{
    public static Node head = new Node();

    /**
     * 向链表结尾添加节点
     * @param node
     */
    public void add(Node node){
        Node temp = head;
        while(true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }


    /**
     * 根据标志位升序插入节点
     * @param node
     */
    public void addOrderByAsc(Node node){
        Node temp = head;
        boolean flag = false; //添加的节点标志是否存在
        while(true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no > node.no){
                break;
            }else if(temp.next.no == node.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.println("添加的节点已经存在！");
        }else{
            node.next = temp.next;
            temp.next = node;
        }
    }


    /**
     * 更新节点信息
     * @param node
     */
    public void update(Node node){
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }
        boolean flag = false;  //是否存在该节点
        Node temp = head.next;
        while(true){
            if(temp == null){
                break;
            }
            if(temp.no == node.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.name = node.name;
        }else{
            System.out.println("没有该节点的信息！");
        }
    }

    /**
     * 根据标志位删除节点
     * @param no
     */
    public void del(int no){
        boolean flag = false;
        Node temp = head;
        while (true){
            if(temp.next == null){
                break;
            }
            if (temp.next.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }else{
            System.out.println("没有该节点！");
        }
    }
    public void list(){
        if(head.next == null){
            System.out.println("该链表为空！");
            return;
        }
        Node temp = head.next;
        while(true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Node{
    public int no;
    public String name;
    public Node next;
    public Node(int no,String name){
        this.no = no;
        this.name = name;
    }
    public Node(){}

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name +
                '}';
    }
}