数据结构：单链表

用（带头节点）单链表完成图书统计。节点结构包括书籍编号，书籍名以及对应作者。功能包括增加（尾插法和指定位置插入法）、删除、修改、查看。

---

一、定义节点结构

每一个节点都包括这些变量，构造器复杂将传入的数据赋值给类本身的变量。

    public static class BookNode{
        public int bookNumber;
        public String bookName;
        public String bookAuthor;
        public BookNode next;
        //构造器
        public BookNode(int no, String book, String author){
            bookNumber = no;
            bookName = book;
            bookAuthor = author;
        }
    }

二、定义一个SingleLinkList类

该类用于管理链表，因为使用的是带头节点的单链表，因此在定义类的时候就应该把头节点定义好并初始化。

    public static class SingleLinkList{
        private BookNode head = new BookNode(0," "," ");
        //......
    }

三、添加元素

（1）尾插法

入参为一个新建的节点，用temp找到temp.next为null，以为着已经到达了链表尾部。将新节点node赋值给temp.next即已经将新节点连接上链表尾部。

        //尾插法
        public void add1(BookNode node){
            BookNode temp = head;
            while(true){
                if(temp.next == null){
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }

测试结果：

 因为手动添加的顺序是1-3-2，用尾插法会默认将新节点放在尾部，所以最后输出的时候仍然保持着1-3-2的顺序。

（2）指定位置插入

制定位置插入是根据书本的编号来安排每个节点之间的关系。

何为合适的位置？就是在链表中找到某一个位置，上一个节点的书本编号小于新节点的书本编号，而下一个节点的书本编号又大于新节点的书本编号，这意味着该位置就是新节点的最佳位置。前一个节点就是为temp，而后一个节点就为temp2。若满足条件，则需要断开此处的聊表链接，将新节点插入，再完成链接。

如果寻至尾部，仍未找到满足条件的位置，则在链表最后插入即可。

        //中间插入
        public void add2(BookNode node) {
            BookNode temp = head;
            while (true) {
                if (temp.next == null) {
                    temp.next = node;
                    break;
                }
                if (node.bookNumber > temp.bookNumber) {
                    BookNode temp2 = temp.next;
                    if (node.bookNumber < temp2.bookNumber) {
                        BookNode temp3 = temp.next;
                        temp.next = node;
                        node.next = temp3;
                        break;
                    }
                }
                temp = temp.next;
            }
        }

测试结果：

 手动添加的顺序仍然是1-3-2，用制定位置插入法会按照图书标号将新节点放在编号所对应的位置，所以最后输出的顺序为1-2-3。

 

三、展示链表

首先判断链表是否为空，若为空则提示用户并直接return就可以了；若不为空，则用show遍历链表，并将链表中的数据打印出来即可。

        //展示链表
        public void list(){
            if(head.next == null){
                System.out.println("链表为空~没东西可看了......");
                return;
            }
            BookNode show = head.next;
            while(show != null){
                System.out.println("（" +show.bookNumber+ "）" +"《"+show.bookName+"》"+"作者："+show.bookAuthor);
                show = show.next;
            }
        }

四、修改链表

传入一个新的节点，新节点的bookNumber应该与目标节点保持一致。通过对比新节点和目标节点号，寻找要修改的节点。用flag记录是否找到，如找到则将flag设为true，否则false。完成遍历后，根据flag值进行下一步操作。若为true，则意味着在链表中找到了目标节点，把链表中目标节点的数据更新为新节点的数据；若为false，意味着没有找到，则提示用户。

        //修改
        public void updata(BookNode bookdata){
            BookNode temp = head;
            boolean flag = false;
            while(true){
                if(temp.bookNumber == bookdata.bookNumber){
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
 
            if(flag){
                temp.bookName = bookdata.bookName;
                temp.bookAuthor = bookdata.bookAuthor;
            }else{
                System.out.println("没有找到该元素~");
            }
        }

测试结果：

根据新节点的信息修改链表中节点的信息。将第二本图书，更改为无名氏写的《十万个为什么》，但序号不变。

 

五、删除节点

传入一个需要删除的编号，通过对比每个节点的bookNumber进行删除操作，同样用flag记录找寻结果。当找到需要删除的节点时，temp会指向需要删除的节点，而front则会指向需要删除节点的前一个节点。front变量的存在，就是为了方便删除操作，将front.next的值直接更改为temp.next值（意味着已经跳过temp节点），在java中temp节点则被视为弃用的节点会被自动回收。如果没有找到需要删除的节点，则提示用户。

        //删除
        public void del(int n){
            BookNode front = head;
            BookNode temp = head.next;
            Boolean flag = false;
            while (true){
                if(n == temp.bookNumber){
                    flag = true;
                    break;
                }
                temp = temp.next;
                front = front.next;
            }
            if(true){
                front.next = temp.next;
            }else{
                System.out.println("没有找到需要删除的数据......");
            }
        }

测试结果：

将第一本书鲁迅的《狂人日记》从链表中删除。最后输出仅剩两本书了。

 

---

全部代码：

import org.omg.Messaging.SyncScopeHelper;
 
public class LineList {
 
    public static void main(String[] args){
        //书籍数据
        BookNode test = new BookNode(1,"狂人日记","鲁迅");
        BookNode test2 = new BookNode(2,"社会性动物","E.阿伦森");
        BookNode test3 = new BookNode(3,"时间简史","史蒂芬.霍金");
 
        //创建一个单链表
        SingleLinkList testlist = new SingleLinkList();
 
        //添加
        //头插法
//        testlist.add1(test);
//        testlist.add1(test3);
//        testlist.add1(test2);
//        //指定位置插入
        testlist.add2(test);
        testlist.add2(test3);
        testlist.add2(test2);
 
//        //删除
        testlist.del(1);
//
//        //修改
        BookNode updata = new BookNode(2,"十万个为什么","无名氏");
        testlist.updata(updata);
 
        //展示链表
        testlist.list();
    }
 
 
    //节点
    public static class BookNode{
        public int bookNumber;
        public String bookName;
        public String bookAuthor;
        public BookNode next;
        //构造器
        public BookNode(int no, String book, String author){
            bookNumber = no;
            bookName = book;
            bookAuthor = author;
        }
    }
 
    //管理
    public static class SingleLinkList{
        private BookNode head = new BookNode(0," "," ");
 
        //尾插法
        public void add1(BookNode node){
            BookNode temp = head;
            while(true){
                if(temp.next == null){
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }
 
        //中间插入
        public void add2(BookNode node) {
            BookNode temp = head;
            while (true) {
                if (temp.next == null) {
                    temp.next = node;
                    break;
                }
                if (node.bookNumber > temp.bookNumber) {
                    BookNode temp2 = temp.next;
                    if (node.bookNumber < temp2.bookNumber) {
                        BookNode temp3 = temp.next;
                        temp.next = node;
                        node.next = temp3;
                        break;
                    }
                }
                temp = temp.next;
            }
        }
 
        //展示链表
        public void list(){
            if(head.next == null){
                System.out.println("链表为空~没东西可看了......");
                return;
            }
            BookNode show = head.next;
            while(show != null){
                System.out.println("（" +show.bookNumber+ "）" +"《"+show.bookName+"》"+"作者："+show.bookAuthor);
                show = show.next;
            }
        }
 
        //修改
        public void updata(BookNode bookdata){
            BookNode temp = head;
            boolean flag = false;
            while(true){
                if(temp.bookNumber == bookdata.bookNumber){
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
 
            if(flag){
                temp.bookName = bookdata.bookName;
                temp.bookAuthor = bookdata.bookAuthor;
            }else{
                System.out.println("没有找到该元素~");
            }
        }
 
        //删除
        public void del(int n){
            BookNode front = head;
            BookNode temp = head.next;
            Boolean flag = false;
            while (true){
                if(n == temp.bookNumber){
                    flag = true;
                    break;
                }
                temp = temp.next;
                front = front.next;
            }
            if(true){
                front.next = temp.next;
            }else{
                System.out.println("没有找到需要删除的数据......");
            }
        }
    }
}