一、链表
（一）链表介绍
1) 链表是有序存储，以节点的方式来存储，是链式存储结构
2) 每个节点包含 data 域（用来存储数据）， next 域： 指向下一个节点（next中存储了要指向节点的内存地址）
3) 如图： 链表的各个节点不一定是连续存储.
4) 链表分带头节点的链表和没有头节点的链表， 根据实际的需求来确定
。头结点是指data域为空的节点，只有指向下一个节点的next域。
链表在内存中的存储形式： 链表的逻辑形式：
（二）单向链表的应用
在以下应用中，涉及到对链表的遍历时，需要将头结点赋值给一个辅助节点temp（因为头结点不能动），使用temp=temp.next来后移节点
1、向链表中添加节点。分为两种情况：
1）按添加语句的输入顺序添加节点：直接将节点添加到链表尾部。只需要使链表尾节点的next指向要添加的节点即可
代码实现如下
1 /** 2 * 将新节点加入链表 3 * 当不考虑编号时 4 * 思路：1、遍历链表，找到next=null的尾节点 5 * 2、将尾节点的next指向新节点 6 * @param heroNode 需要添加的新节点 7 */ 8 public void addNode(HeroNode heroNode){ 9 //遍历链表，找到结尾，在结尾处加入新的节点 10 HeroNode temp=headNode;//头结点不能动，需要辅助变量来遍历 11 while (true){ 12 if (temp.next == null) { 13 break; 14 } 15 //将节点后移 16 temp=temp.next; 17 } 18 //将新节点加到尾部 19 temp.next=heroNode; 20 }
2）按节点中的数据顺序添加节点：需要按照编号的顺序进行添加。
思路：遍历链表，将本节点的下个节点的编号（no1）（因为单向链表只有一个指向下个节点的next，无法指向上一个节点）与要添加节点的编号（no2）进行比较，
若no1>no2（按升序进行添加）则添加。
添加方式：新节点.next=temp.next
temp.next=新节点
代码实现如下：
1 /** 2 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名， 则添加失败， 并给出提示 3 * @param heroNode 4 */ 5 public void addNodeSort(HeroNode heroNode){ 6 //对链表进行遍历 7 HeroNode temp=headNode; 8 boolean flag=false; 9 while (true){ 10 if (temp.next == null) { 11 break; 12 } 13 //如果有这个排名， 则添加失败， 并给出提示 14 if (temp.next.no==heroNode.no){ 15 flag=true; 16 break; 17 } 18 if ( heroNode.no<temp.next.no){ 19 break; 20 } 21 temp=temp.next; 22 } 23 if (flag){ 24 System.out.printf("已有此编号%d，无法加入\n",heroNode.no); 25 }else { 26 heroNode.next=temp.next; 27 temp.next=heroNode; 28 } 29 }
2、删除节点
若当前节点的next指向的节点为要删除的节点，则执行
//使当前节点的next指向下下个节点，完成对下个节点的删除 temp.next=temp.next.next;
代码实现如下：
1 /** 2 * 根据no删除节点 3 */ 4 public void deleteNode(int no){ 5 HeroNode temp=headNode; 6 boolean flag=false; 7 if (temp.next==null){ 8 return; 9 } 10 while (true){ 11 //已经到达尾节点，跳出循环 12 if (temp.next == null) { 13 break; 14 } 15 //如果当前节点的next指向的下个节点为要删除的节点 16 if (no==temp.next.no){ 17 flag=true; 18 break; 19 } 20 temp=temp.next; 21 } 22 if (flag){ 23 //使当前节点的next指向下下个节点，完成对下个节点的删除 24 temp.next=temp.next.next; 25 }else { 26 throw new RuntimeException("该节点不存在"); 27 } 28 }
3、遍历链表
代码实现如下
1 /** 2 * 遍历链表 3 */ 4 public void showLists(){ 5 //先判断链表是否为空 6 if (headNode.next == null) { 7 System.out.println("链表为空"); 8 return; 9 } 10 HeroNode temp=headNode.next;// 11 while (true){ 12 //当前节点为链表尾 13 if (temp== null) { 14 break; 15 } 16 //输出当前节点的信息 17 System.out.println(temp); 18 //节点后移 19 temp=temp.next; 20 } 21 }
（三）双向链表的应用
管理单向链表的缺点分析:
双向链表中的节点由三部分构成：pre域（指向上一个节点的内存地址）+data域（存储数据）+next域（指向下一个节点的内存地址）。
单双向列表应用的差异主要体现在删除节点上
//完成对当前节点的删除
temp1.pre.next=temp1.next;
//当前节点为尾节点时，不能执行下句，否则会出现空指针异常
if (temp1.next!=null) { temp1.next.pre = temp1.pre;}
1 /** 2 * 根据no删除节点 3 * 双向链表可以实现当前节点的自我删除，不需要通过上一个节点删除 4 */ 5 public void deleteNode(int no){ 6 HeroNode1 temp1=headNode1.next; 7 boolean flag=false; 8 if (temp1==null){ 9 return; 10 } 11 while (true){ 12 if (temp1 == null) { 13 break;//temp节点为尾节点 14 } 15 //如果当前节点为要删除的节点 16 if (no==temp1.no){ 17 flag=true; 18 break; 19 } 20 temp1=temp1.next;//当前节点temp为尾节点时，则有temp=temp.next==null，所以下次循环时会退出循环 21 } 22 if (flag){ 23 //完成对当前节点的删除 24 temp1.pre.next=temp1.next; 25 //当前节点为尾节点时，不能执行下句，否则会出现空指针异常 26 if (temp1.next!=null) { 27 temp1.next.pre = temp1.pre; 28 } 29 30 }else { 31 throw new RuntimeException("该节点不存在"); 32 } 33 }
原文：https://www.cnblogs.com/Cong-l/p/12715225.html