数据结构（单向链表的增删改查）数据结构：单向链表的增删改

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

文章图片

上图可以看出结构了，即每一个节点的Next变量，都指向了下一个节点，而最后一个节点指向了null
数据结构：

package LinkListTest; public class LinkList { private Integer date; private LinkList next; public Integer getDate() { return date; } public void setDate(Integer date) { this.date = date; } public LinkList getNext() { return next; } public void setNext(LinkList next) { this.next = next; } @Override public String toString() { return "LinkList [date=" + date + ", next=" + next + "]"; }}

其中第一个是链表存储的值（用Integer类型可以直接判断该该值是否为null，如果是int类型，由由于int类型是基本类型，不能这样判断），而第二个和链表类型一样的变量next是只想下一个节点的引用
单向链表的增删改查（包含有序、无序、重复和不重复）

package linklisttest; public class NodeTest { public static Node node = new Node(); //全局变量链表头节点 public static void main(String[] args) { // TODO 自动生成的方法存根 int[] arr = {4,5,9,6,3,1,7}; for(int i = 0; i < arr.length; i++) { //add(arr[i]); ADD(arr[i]); } System.out.println(node); //del(4); //Del(1); //Del(7); del(8); search(8); update(8,9); System.out.println(node); } //有序链表的插入，按从小到大的顺序排列 public static void ADD(int date) { if(node.getDate() == null) //判断头节点有没有进行赋值 { node.setDate(date); return ; } else if(node.getDate() > date) //如果要插入的数据比头节点的小，则直接变成表头 { Node newNode = new Node(); newNode.setDate(date); newNode.setNext(node); node = newNode; return ; } Node temp = node.getNext(); Node newNode = new Node(); //要插入的节点 Node pre = node; while(temp != null) { if(date < temp.getDate()) //若两数相等，则直接默认后来插入的date较大 { newNode.setDate(date); newNode.setNext(temp); pre.setNext(newNode); return ; } pre = temp; temp = temp.getNext(); } newNode.setDate(date); pre.setNext(newNode); } //无序链表的插入（头插法） public static void add(int date) { if(node.getDate() == null) //判断头节点有没有进行赋值 { node.setDate(date); return ; } Node temp = new Node(); temp.setDate(date); //设置新节点的数 temp.setNext(node); //设置新节点的下一个个点就是头节点， node = temp; //将新插入的节点作为新节点，实现头插法 } //链表的插入（尾插法） public static void Add(int date) { if(node.getDate() == null) //判断头节点有没有赋值 { node.setDate(date); return ; } Node pre = node; for(Node temp = node.getNext(); temp != null; temp = temp.getNext()) { //局部变量temp是pre节点的下一个节点，当pre的下一个节点即temp为空时， //循环结束，此时pre节点就是链表的最后一个节点 pre = temp; } Node temp = new Node(); pre.setNext(temp); temp.setDate(date); //将新节点插入到最后一个节点的后面，实现尾插法 } //链表的删除未声明前驱结点 public static void del(int date) { if(node.getDate() == null) //链表为空 System.out.println("链表中不存在数：" + date); else { if(node.getDate() == date) //如果头节点就是要删除的数 { node = node.getNext(); //直接将头节点等于头节点的下一个节点，实现删除 } else { Node temp = node; while(temp.getNext() != null) { if(temp.getNext().getDate() == date) //temp.getNext()就是要删除的节点 { if(temp.getNext().getNext() == null) //判断删除的节点是不是最后一个节点 { //要删除节点是最后一个节点，直接将被删除节点的前一个节点的Next设置为空，实现删除 temp.setNext(null); return ; } else //如果不是 { //将要删除节点的前一个节点指向被删除节点的后一个节点，实现删除 temp.setNext(temp.getNext().getNext()); //continue ; //有重复节点时，用continue return ; //无重复节点时，用return } } else if(temp.getNext().getNext() == null || temp.getNext().getNext().getDate() > date)//如果是无序链表，这里可以删除 { //当前数小于date，下一个或者为空，或者下一个数比date大，因为时有序的，说明链表里面没有该数 System.out.println("链表中不存在数：" + date); return; } temp = temp.getNext(); } //表明已经便利完了链表也没有要删除的值，直接结束 System.out.println("链表中不存在数：" + date); } } } //链表的删除声明前驱节点 public static void Del(int date) { if(node.getDate() == null) //链表为空 System.out.println("链表中不存在数：" + date); else { if(node.getDate() == date) //如果头节点就是要删除的数 { node = node.getNext(); //直接将头节点等于头节点的下一个节点，实现删除 } else { /*以上代码和为声明前驱节点的方法代码一样*/ Node pre = node; Node temp = node.getNext(); while(temp != null) { if(temp.getDate() == date) //已经找到节点 { pre.setNext(temp.getNext()); //将节点的前驱节点的next设置为被删除节点的下一个节点 return ; //已删除，直接结束方法，不用再执行，如果将return 则是有重复节点的算法 } else if(temp.getNext() == null || temp.getNext().getDate() > date)//如果是无序链表，这里可以删除 { //当前数小于date，下一个或者为空，或者下一个数比date大，因为时有序的，说明链表里面没有该数 System.out.println("链表中不存在数：" + date); return; } pre = temp; temp = temp.getNext(); } //表明已经便利完了链表也没有要删除的值，直接结束 System.out.println("链表中不存在数：" + date); } } } //链表的查询 public static void search(int date) { Node temp = node; if(temp.getNext() == null) //链表为空 { System.out.println("链表为空"); return ; } while(temp != null) { if(temp.getDate() == date) { System.out.println("链表存在数：" + date); return ; } else if(temp.getNext() == null || temp.getNext().getDate() > date) { System.out.println("链表不存在数：" + date); return ; } temp = temp.getNext(); } System.out.println("链表中不存在数：" + date); } //链表的修改 public static void update(int oldDate,int newDate) { Node temp = node; if(temp.getNext() == null) //链表为空 { System.out.println("链表为空"); return ; } while(temp != null) { if(temp.getDate() == oldDate) { temp.setDate(newDate); return ; //如果去掉return 则为有重复数据的算法 } else if(temp.getNext() == null || temp.getNext().getDate() > oldDate) { System.out.println("****链表不存在数：" + oldDate); return ; } temp = temp.getNext(); } System.out.println("链表中不存在数：" + oldDate); } }

双向链表 【数据结构（单向链表的增删改查）】定义：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个引用，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。