1、链表介绍

数据结构整理目录

1. 链表是以节点的方式来存储的
2. 每个节点包含data域，next域：指向下一个节点
3. 链表的各个节点不一定是连续存放的
4. 链表分带头节点的链表和没有头结点的链表（根据实际需求确定.有头结点操作更简便)

2、单链表

添加节点到队列末尾

1. 先创建一个Head头节点，作用就是表示单链表的t

2. 后面我们每添加一个节点，就直接加入到链表的最后

   ---

遍历

通过一个辅助变量，帮助遍历整个链表

思考：为什么要添加辅助变量？？因为头结点往往不能动（一旦移动找不到这个链表)，因此需要使用一个辅助变量遍历链表，这也是对于链表这种数据类型的常规思路

---

在某个位置添加节点（在链表内部添加节点)

按照编号的顺序添加节点

​ 思路：

1. 首先找到新添加节点的位置，是通过辅助变量（指针），通过遍历来搞定(要找到加入位置的前一个节点）,

2. 新的节点的.next = temp.next

3. temp.next = 新的节点

   关键就是第一步，通过辅助变量，遍历链表的过程

   ---

修改单链表

思路:

关键还是用到前面的指针遍历的方法

1. 通过遍历找到该节点，通过遍历
2. 修改

---

删除节点

思路:

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

---

小结

1. 对于链表，很重要的一种操作就是通过临时指针temp，遍历整个链表，进行操作（例如按照顺序添加节点，删除节点，修改节点，查看所有节点）
2. 对于删除节点，在指定位置增加节点，遍历指针要旨在待操作节点的前一个节点处
3. 进行实现时，要分布进行，先找到节点（或者判断没有符合要求的节点），再进行对应的删除或者增加

---

代码

package C链表;import com.sun.org.apache.xpath.internal.SourceTree;/*** @Author Zhou  jian* @Date 2019 ${month}  2019/12/24 0024  18:22*/
public class SingleLinkedListDemo {public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();HeroNode heroNode1 = new HeroNode(1,"宋江","及时雨");HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟");HeroNode heroNode3 = new HeroNode(3,"吴用","智多星");HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);singleLinkedList.addByOrder(heroNode1);singleLinkedList.addByOrder(heroNode4);singleLinkedList.addByOrder(heroNode2);singleLinkedList.addByOrder(heroNode3);singleLinkedList.list();System.out.println("================================");HeroNode heroNode5 = new HeroNode(1,"皇帝","赵构");singleLinkedList.update(heroNode5);singleLinkedList.list();singleLinkedList.delete(1);singleLinkedList.delete(4);singleLinkedList.delete(2);singleLinkedList.delete(3);System.out.println("================================");singleLinkedList.list();}
}class SingleLinkedList{//先初始化一个头结点，头结点不要动,不存放具体的数据private HeroNode head = new HeroNode(0,"","");//添加节点到单向链表:添加到链表的最后//思路：当不考虑编号的顺序时//1、找到当前链表的最后节点//2、将最后这个节点的next指向新的节点public void add(HeroNode heroNode){//因为head节点不能动，因此需要一个辅助变量tempHeroNode temp = head;//遍历链表，找到最后while(true){//找到链表的最后if(temp.next==null){break;}else{//如果没有找到最后，将temp后移temp = temp.next;}}//当退出while循环时，temp指向了链表的最后//将最后这个节点的next指向新的节点temp.next = heroNode;}//显示链表[遍历]public void list(){//判断链表是否为空if(head.next==null){System.out.println("链表为哦空");return;}else{//因为头结点不能动，因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while(temp!=null){System.out.println(temp);temp = temp.next;}}}//第二种方式在添加英雄时，根据排名将英雄插入到指定位置//如果有这个排名，则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助我们找到添加的位置//因为是单链表，因此我们找的temp是位于添加位置的前一个节点，否则插入不了HeroNode temp = head; //辅助指针boolean flag = false; //标志添加的英雄的编号是否存在，默认为falsewhile(true){if(temp.next==null){//说明temp已经在链表的最后break;}else if(temp.next.no>heroNode.no){//位置找到，就在temp的后面插入（找到带插入节点的前一个节点)break;}else if(temp.no==heroNode.no){//说明希望添加的herooNode的编号依然存在flag = true;//说明编号存在break;}else{temp = temp.next;//指针后移，遍历}}if(flag){//不能添加，说明编号已经存在System.out.printf("准备插入的英雄编号%d已经存在\n",heroNode.no);}else{//插入到链表中heroNode.next=temp.next;temp.next=heroNode;}}//修改节点的信息，根据no修改，即no编号不能改变public void update(HeroNode heroNode){//先定义一个辅助变量HeroNode temp = head;while(temp.next!=null){if(temp.no==heroNode.no){temp.name=heroNode.name;temp.nickname=heroNode.nickname;break;}else{temp=temp.next;}}}//删除节点public void delete(int no){//思路：//1heaHeroNode temp = head;boolean flag = false;//标志是否找到待删除节点while(true){if(temp.next==null){//已经到链表的左后break;}else if(temp.next.no==no){//找到待删除节点的前一个节点flag=true;break;}temp = temp.next;//遍历}if(flag){temp.next=temp.next.next;}else{//否则没有找到要删除的节点System.out.printf("要删除的节点%d不存在\n",no);}}}//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next; //指向下一个节点public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNickname() {return nickname;}public void setNickname(String nickname) {this.nickname = nickname;}public HeroNode getNext() {return next;}public void setNext(HeroNode next) {this.next = next;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

练习

1、求单链表中节点的个数

/*** 求链表中节点个数问题:遍历链表即可*/public int size() {HeroNode temp = head.next;int length = 0;while (true) {if (temp != null) {length++;temp = temp.next;} else {break;}}return length;}

2、查找单链表中的倒数第k个节点

/*** 查找单链表中的倒数第k个节点:* 若链表中有n个节点则求链表中的倒数k各个节点，* 也就是求链表中正数的 第n-k+1个节点*/public HeroNode findByReverse(int no){//1、求链表中的节点的个数int length = size();//2、反向数的第no个节点也就是正向数的第 length-no节点int place = length-no+1; //思考为什么要加1，可以考虑倒数第一个节点的情况//3、通过遍历的方式获取节点HeroNode temp = head;for(int i=0;i<place;i++){temp=temp.next;}return temp;}

3、单链表的反转

 /*** 、单链表的反转** 可以通过栈数据结构将所欲节点先存入到栈中；* 然后再从栈中取出数据（利用栈的先进后出的特性实现链表的反转）*/public void reverse(){//1、定义栈Stack<HeroNode> stack = new Stack<>();//2、遍历链表将节点加入到栈中HeroNode temp = head.next;while(temp!=null){stack.push(temp);temp=temp.next;}//3、从栈中取出数据，利用栈的先进后出特性实现链表的反转head.next = stack.pop();temp = head.next;while(stack.size()!=0){temp.next = stack.pop();temp = temp.next;}//最后要将temp.next设置为null，思考为什么temp.next=null;}/*** 单链表的反转方式2:* 遍历链表:读取链表没读取一个数据将数据放入到链表的首*/public void reverse2(){HeroNode temp = head.next;head = new HeroNode(0,"",null);while(temp!=null){temp.next=head.next;head.next=temp;temp=temp.next;}}

4、从尾到头打印单链表（要求：方式1：反向遍历；方式2：Stack栈)

 /*** 从尾到头打印单链表（要求：方式1：反向遍历；方式2：Stack栈)*/public void printReverse1(){int sum = size();for(int i=1;i<=sum;i++){System.out.println(findByReverse(i));}}public void printReverse2(){//1、将数据存入栈中Stack<HeroNode> stack = new Stack<>();HeroNode temp = head.next;while(temp!=null){stack.push(temp);temp=temp.next;}//2、从栈中取出数据并将数据打印while(stack.size()!=0){System.out.println(stack.pop());}}

5、合并两个有序单链表，合并之后的链表依然有序

 /*** 合并两个有序单链表，合并之后的链表依然有序:* 例如：合并链表1和链表2，* 因为在链表1和链表2内部数据已经有序，因此关键是找到切合点* 1、将链表2的第一个元素一次和链表1的数据进行比较找到插入点2、将元素插入问题是如何判断 重复元素的问题？？？因为前面已经有按照元素大小插入链表内部的方法，因此实现比较简单。遍历链表2：将链表2中的每个元素按照顺序插入到链表1中*/public void join(LinkedList insertList){
//        //获取待合并链表的头节点HeroNode head1 = insertList.head;System.out.println(head1);//遍历待合并链表HeroNode temp1 = head1.next;while(temp1!=null){insert(temp1);temp1=temp1.next;}}

3、双向链表

单向链表存在的问题

1. 查找的方向只能是一个方向，而双向链表可以向前或向后查找
2. 单向链表不能自我删除，需要依靠辅助节点，而双向链表，则可以自我删除(所以前面单链表删除节点时，总是找到temp,temp是待删除节点的前一个节点来删除)

遍历

​ 遍历和单链表一样，只是可以向前，也可以向后

添加（添加到双向链表的最后

1. 先找到双向链表的最后这个点
2. temp.next = newHeroNode;
3. newHeroNode.prev=temp;

修改

修改思路和原来的单向链表一样

删除

1. 因为是双向链表，因此我们可以实现自我删除某个节点
2. 直接找到要删除就这个节点
3. temp.prev.next = temp.next;
4. temp.next.prev=temp.prev;

在双向链表的某个位置处添加

注意要动四个指针：这四个指针的操作顺序很重要

1. 先遍历链表找到对应的位置
2. heroNode2.prev = temp.prev
3. temp.prev.next = heroNode2
4. temp.prev = heroNode2
5. heroNode2.next = temp

代码

//创建一个双向链表类
class DoubleLinkedList{//先顶还有一一个头结点，头节点不要动，不存放具体的数据private HeroNode2 head = new HeroNode2(0,"","");//遍历双向链表的方法（和遍历单向链表的方法是一样的）public void list(){HeroNode2 temp = head.next;while(temp!=null){System.out.println(temp);temp=temp.next;}}//向链表的尾部添加数据public void add(HeroNode2 heroNode2){//因为head节点不能动，因此我们需要一个辅助变量tempHeroNode2 temp = head;//遍历链表找到最后while(temp.next!=null){temp = temp.next;}//退出while循环时，temp就指向了链表的最后//在链表的尾部添加数据temp.next=heroNode2;heroNode2.prev=temp;}//双向修改链表：和原来的单向链表的思路是一样的//修改节点的信息，根据no修改，即no编号不能改变public void update(HeroNode2 heroNode2){//先定义一个辅助变量HeroNode2 temp = head;while(temp!=null){if(temp.no==heroNode2.no){temp.name=heroNode2.name;temp.nickname=heroNode2.nickname;break;}else{temp=temp.next;}}}//从双向链表中删除节点/*** 单向链表中需要找到待删除节点的前一个节点* 而在双向链表中不需要这样操作，因为它是双向的，直接找到待删除的节点即可* @param no*/public void delete(int no){//1heaHeroNode2 temp = head;boolean flag = false;//标志是否找到待删除节点while(true){if(temp==null){//已经到链表的左后break;}else if(temp.no==no){//直接找到待删除节点（注意与单链表的区别）flag=true;break;}temp = temp.next;//遍历}if(flag){//找到待删除的节点//若删除的是最后的一个节点，会有问题//如果是最后一个节点，就不需要执行下面这句话，否则就出现空指针异常if(temp.next!=null){temp.next.prev = temp.prev;}temp.prev.next = temp.next;}else{//否则没有找到要删除的节点System.out.printf("要删除的节点%d不存在\n",no);}}//按照编号添加public void addByOrder(HeroNode2 heroNode2){HeroNode2 temp = head;boolean flag = false; //在链表中是否已经存在该编号//遍历链表获取对象while(true){if(temp.next==null){break;}if(temp.no>heroNode2.no){break;}if(temp.no==heroNode2.no){flag=true;break;}temp = temp.next;}//已经存在编号if(flag){System.out.println("待添加的编号已经存在");}else{//如果为头结点则if(temp==head){temp.next = heroNode2;heroNode2.prev = temp;}else{heroNode2.prev = temp.prev;temp.prev.next=heroNode2;temp.prev=heroNode2;heroNode2.next = temp;}}}
}//定义HeroNode2,每个HeroNode对象就是一个节点
class HeroNode2{public int no;public String name;public String nickname;public HeroNode2 next; //指向下一个节点，默认为nullpublic HeroNode2 prev; //指向前一个节点,默认为nullpublic HeroNode2(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNickname() {return nickname;}public void setNickname(String nickname) {this.nickname = nickname;}public HeroNode2 getNext() {return next;}public void setNext(HeroNode2 next) {this.next = next;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

4、环形链表（单向）

约瑟夫问题

设编号为1,2,3…n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，依次类推，知道所有人出列为止，由此产生一个出队编号的序列

约定:

​ n=5:有5个人

​ k=1：从第一个人开始报数

​ m=2:数2下

​ 出队列的顺序：2->4->1->5->3

构建环形链表

对于只有一个节点的环形链表，其next域指向自身

first:指向链表的第一个节点

currentBoy：指向当前环形队列之前添加的最后一个对象:也就是链表的最后一个元素（错略的说），方便之后添加元素

• 比如之后添加元素的操作： currentBoy.next = newBoy
• newBoy.next = first
• currentBoy = newBoy

​ 创建单向环形链表的思路

1. 先创建第一个节点，让first指向该节点，并形成环形

2. 后面当我们没创建一个新的节点，就把该节点加入到已有的环形

   ​

遍历环形链表

1. 先让一个辅助变量(指针)curBoy，指向first节点
2. 然后通过一个while循环遍历链表即可 （当curBoy.next =first结束遍历）

出队列的问题

生成小孩出圈的顺序

1. 需要创建一个辅助指针（变量)helper，事先应该指向环形链表最后节点

2. 报数前：先让first和helper移动k-1次

3. 当小孩报数时，让first和helper指针同时移动m-1次(m为数几次出圈)

4. 这时可以将first指向的小孩节点除权

      first = first.next;helper.next = first;
   

   代码

   package C链表;/*** @Author Zhou  jian* @Date 2019 ${month}  2019/12/27 0027  00:53* 约瑟夫问题*/
   public class JosePfu {public static void main(String[] args) {CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();//创建环形链表circleSingleLinkedList.addBoy(10);circleSingleLinkedList.list();//出圈的位置circleSingleLinkedList.countBoy(1,2,5);}}//环形单向链表
   class CircleSingleLinkedList{//创建一个first节点，当前没有编号private Boy first = new Boy(-1);//添加小孩节点public void addBoy(int number){//对nmber做数据校验if(number<1){System.out.println("numvber的值不正确");return;}else{//辅助变量帮助构建环形链表Boy currentBoy=null;//使用for循环创建环型链表for(int i=0;i<number;i++){//根据编号创建一个小孩Boy newBoy = new Boy(i+1);//如果是第一个小孩，比较特殊if(first.getNext()==null){first=newBoy;first.setNext(first);//构成环currentBoy=first;}else{//构建环 currentBoy就是为了方便添加元素currentBoy.setNext(newBoy);newBoy.setNext(first);currentBoy=newBoy;}}}}//遍历环形链表public void list(){//辅助指针Boy currentBoy = first;if(first==null){System.out.println("链表为空");return;}else{while(true){System.out.printf("小孩的编号为%d\n",currentBoy.getNo());currentBoy=currentBoy.getNext(); //遍历指针if(currentBoy.getNext()==first){//遍历完链表的条件break;  //跳出循环}}}}//根据用户输入，计算出小孩除权的顺序/**** @param startNo 从第几个小孩开始数数* @param countNo 表示数几下* @param nums  有多少小孩在圈*/public void countBoy(int startNo,int countNo,int nums){//数据校验if(first==null||startNo<1||startNo>nums){System.out.println("您输入的数据有误");}//1、创建辅助指针帮助小孩、出圈（指向链表的末尾)Boy helper = first;for(int i=1;i<nums;i++) {helper = helper.getNext();}//2、报数前，先让helper和firts移动startNo-1次for(int j=0;j<startNo-1;j++){helper = helper.getNext();first = first.getNext();}//只要圈中有大于1个节点即不停取while(true){if(helper==first){//说明圈中只有一个节点break;}//3、定位:将first与helper指针移动m-1个位置for(int i=0;i<countNo-1;i++){helper = helper.getNext();first = first.getNext();}//找到小孩出圈的位置：first指向的节点就是要出圈小孩的节点System.out.printf("出圈小孩的编号为%d\n",first.getNo());//4、将该节点出圈first=first.getNext();helper.setNext(first);}//将链表中唯一的节点除出圈System.out.printf("最后留在圈中的小孩编号为为%d\n",first.getNo());}}//孩子类
   class Boy{private int no; //编号private Boy next;//指向下一个节点public Boy(int no) {this.no = no;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}@Overridepublic String toString() {return "Boy{" +"no=" + no +'}';}
   }

   5、链表小结

   1. 链表的优势：要求物理存储空间不一定连续；存储数据的大小只要内存够即可；可不断动态扩称其内容；相比数组数据结构有优势；

   2. 链表增加、删除数据比较方便；但是查找数据需要借助指针（辅助变量）遍历整个链表才能得到结果，查找性能较差

   3. 链表分为单向链表，双向链表，循环链表（单向循环，双向循环）

   4. 链表中一些常用方法思路的小结

      • ​ 对于链表有的有头指针，有的没有，最好有头指针，同一操作，（环形链表可以没有)

      • 对链表的操作，主要就是通过指针，辅助变量遍历链表先找到合适位置然后再进行操作

      • 遍历完整个链表的条件：（单向链表就是 temp.next=null;循环链表temp.next=first)

      • 对每种链表抓住，有几个指针（前向和后向)

      • 尤其注意头结点与尾结点（经常报空指针异常错误）

      • 对于增加元素：对单向和双向都要注意有几种添加位置，在队尾，在链表的首部，在链表的其余位置,

      • 对于修改元素：通过辅助指针遍历整个链表查找到位置，然后更新

      • 对于删除元素: 通过辅助指针找到位置（对于单链表要注意找到的为待删除节点的前一个指针；而对于双像链表可直接找到待删除节点的位置

      • 对于遍历打印整个链表：通过辅助指针从前往后遍历

        ​

        5、一些变形

        • 求链表的长度

        • 反转链表

        • 打印反转链表

        • 求倒数k个链表

        • 拼接链表

   ---

参考:
链表的技巧
··················································································································2019年12月27日02:10:53