[数据结构与算法]数据结构-单向链表-Java版

单向链表（Java实现）

什么是链表?

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。（来源：百度百科）

什么是单向链表？

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点； （来源：百度百科）

• 链表数据结构图示

逻辑结构：链表的每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的头部不存放数据，只存放下一个节点地址的指针域。

存储结构

• 手动实现单向链表

FieldNode 是链表的节点，链表的数据结构是：（节点数据，下一个节点的引用）
所以在FieldNode 中，(id,name)是数据域，next是存放下一个节点的引用地址域。

class FieldNode {
    public Integer id;
    public String name;
    public FieldNode next;

    public FieldNode() {
    }

    public FieldNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public FieldNode(Integer id, String name, FieldNode next) {
        this.id = id;
        this.name = name;
        this.next = next;
    }

    @Override
    public String toString() {
        return "FiledNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

链表的类
包含属性：head(头结点)
包含方法：增（普通增加，按顺序增加）删改查
需要注意的点是:每次在while中操作节点时，需要使用temp属性代替，因为head不可更改。

public class FieldLinkedList {

    // 链表的头节点：不存放数据，主要存放next
    private FieldNode head;

    /**
     * 向链表添加节点
     */
    public void add(FieldNode node){
        // temp是辅助变量
        FieldNode temp = head;
        while (true){
            // 如果temp.next为空，说明下一个节点为空，此时temp是链表的尾结点，则可跳出循环
            if (temp.next==null){
                break;
            }else{
                temp = temp.next;
            }
        }
        temp.next = node;
    }

    /**
     * 按顺序插入
     * @param data
     */
    public void addOrder(FieldNode data){
        FieldNode temp = head;
        while (true){
            // 如果头结点的下一个节点为空，则证明到了链表尾，直接跳出循环去添加
            if (temp.next==null) {
                // break是为了执行循环外的赋值操作
                break;
            }
            // 从中间添加的话只能切断链表，在两个节点之间插入一个节点，
            // 需要有（当前节点，被插入节点，原当前节点的原本下一个节点），所以为了temp保持在当前节点上，需要使用temp.next.id >= data.id判断
            if (temp.next.id >= data.id){
                break;
            }
            temp = temp.next;
        }
        // 原本的链表：()-> (1)-> (5)
        // 要插入的节点:(3)->
        // 当前节点temp:(1)->     通过上边的if跳出循环后，temp保持在(1)->
        // 插入操作：(3)->的下一个节点是temp的下一个节点，也就是(3)->(5)
        //         temp的下一个节点是被插入节点  （1）->(3)   此时(3)->的下一个节点已经是(5)
        data.next = temp.next;
        temp.next = data;
    }

    /**
     * 输出链表
     */
    public void list(){
        FieldNode temp = head.next;
        while (true){
            if (temp==null){
                break;
            }else{
                System.out.println(temp.toString());
                temp = temp.next;
            }
        }
    }

    public void update(FieldNode node){
        if (head.next==null){
            System.out.println("链表为空，无法修改");
            return;
        }
        /**
         * 头结点-> (1,'小红')-> (3,’小明‘)-> (5，’小绿‘)->
         * node:(3，'小兰')->
         * if( (3,’小明‘)==(3，'小兰')){
         *     break;  // 此时temp是3 ，直接跳出循环修改3的name就好
         * }
         */
        FieldNode temp = head.next;
        boolean flag = false; // 是否有相同的ID （有相同ID证明需要修改）
        while (true){
            if (temp.next==null){
                System.out.println("未找到ID为'"+node.id+"'的节点，修改失败");
                break;
            }
            if (temp.id == node.id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 找到了相同数据 此时temp就是被修改的元素
        if (flag){
            temp.name = node.name;
            System.out.println("修改成功");
        }
    }

    /**
     * 删除
     */
    public void delete(Integer id){
        if (head.next==null){
            System.out.println("链表为空，无法修改");
            return;
        }
        boolean flag = false;
        FieldNode temp = head;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.id.equals(id)){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
            System.out.println("删除成功");
        }else{
            System.out.println("删除失败：未找到"+id);
        }

    }

    /**
     * 链表初始化
     */
    public FieldLinkedList() {
        this.head = new FieldNode();
    }
}