【数据结构与算法 3】单链表

叁歲伎倆 2021-08-29 15:14 509阅读 0赞

## **一、链表的特点** ##

1、链表是一种非线性、非顺序的物理结构，是由多个节点组成。

2、链表采用的是“见缝插针”的存储方法，不要求内存连续，靠next指针关联起来。

3、链表的物理存储方式为随机存储，访问方式为顺序访问。

4、查找节点的时间复杂度为O(n)，插入、删除节点的时间复杂度为O(1)。

5、链表适用于写操作多，读操作少的场景。

## **二、单链表** ##

链表是有序的列表，但是它在内存中存储如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70][]

上图小结：

1、链表是以节点的方式来存储，是链式存储

2、每个节点包含data域，next域：指向下一个节点

3、如图发现链表的各个节点不一定是连续存储

单链表的逻辑结构示意图：

![20200513133039592.png][]

## **三、关于头结点** ##

链表可以有头节点，也可以没有头节点。

区别在于链表有头节点虽然浪费空间，但易理解，边界好处理，不易出错，代码简单；

相反无头节点，省空间，难理解，边界不易处理，代码稍复杂。

头节点是为了对链表建立、删除、逆向的时候操作更统一，不用专门对第一个元素或最后一个元素进行单独处理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1][]

## **四、为什么要使用链表呢？** ##

1、数组的物理内存上连续的、顺序的空间，如果数组太大或没有连续大小的空间时就需要使用链表了。

2、如果我们要对一组数据进行删除操作时，用数组的话，我们就需要将要删除的那个数据所在的位置后面的所有数据都向前移动一个位置，当我们添加数据时，同样也要让后面的向后挪动一个位置。

如果使用链表的话，就是把那个节点的指针域所指向地址指向下一个节点的地址就可以了。而添加呢，也是类似的指针操作。

当然链表也有劣势，就是查找，如果想要查找某个数据，就必须要从第一个节点开始依次查找。

那么综上所述，可以知道为什么要用到链表，数组和链表存在的意义了。

那什么又是单向链表？什么又是循环链表？就用一个结构图来表明它们的关系吧。

线性表：一种最简单、常用的数据结构，数据元素之间是一对一的关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2][]

## ** 五、代码实例** ##

使用带head头的单向链表实现水浒英雄排行管理完成对英雄人物的增删改查操作。

### 定义英雄实例 ###

package com.atguigu.linkedlist;
    
    public class HeroNode {
    	public int no;
    	public String name;
    	public String nickname;
    	public HeroNode next;//指向下一个节点
    	
    	public HeroNode(int hNo,String hName,String hNickname) {
    		this.no = hNo;
    		this.name = hName;
    		this.nickname = hNickname;
    	}
    
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname+"]";
    	}
    }

### 增删改查 ###

package com.atguigu.linkedlist;
    
    public class SingleLinkedList {
    	//先初始化一个头节点，头节点不要动,不存放具体数据
    	private HeroNode head = new HeroNode(0, "", "");
    	//添加节点到单向链表
    	//思路，当不考虑编号顺序时
    	//1、找到当前链表的最后节点
    	//2、将最后节点的next域指向新的节点
    	public void add(HeroNode heroNode) {
    		//因为head节点不能动，因此我们需要一个辅助变量
    		HeroNode temp = head;
    		//遍历链表，找到最后
    		while(true) {
    			//找到链表的最后了
    			if(temp.next == null) {
    				break;
    			}
    			//如果没找到，就将temp后移
    			temp = temp.next;
    		}
    		//当退出while循环时temp就指向了链表的最后
    		temp.next = heroNode;
    	}
    	
    	//第二种添加英雄方法，根据排名插入指定位置
    	//如果排名存在，则添加失败，并给出提示
    	public void addByOrder(HeroNode heroNode) {
    		//因为头节点不能动，我们仍然通过辅助变量来找到添加的位置
    		//因为是单链表，因此我们找的temp是位于添加位置的前一个节点，否者加入失败
    		HeroNode temp = head;
    		boolean flag = false;//标识添加的编号是否存在，默认为false
    		while(true) {
    			//说明temp在链表最后
    			if(temp.next == null) {
    				System.out.println("在链表最后");
    				break;
    			}
    			//位置找到，就在temp的后面插入
    			if(temp.next.no > heroNode.no) {
    				break;
    			}
    			//说明编号已经存在
    			if(temp.next.no == heroNode.no) {
    				flag = true;
    				break;
    			}
    			//后移，遍历当前链表
    			temp = temp.next;
    		}
    		//判断flag的值
    		if(flag) {//不能添加，说明编号存在
    			System.out.printf("插入英雄的编号%d已经存在，插入失败",heroNode.no);
    		}else {
    			//插入到链表中，temp的后面
    			heroNode.next = temp.next;
    			temp.next = heroNode;
    		}
    	}
    	
    	//修改节点的信息，根据编号no来修改，no不能修改
    	//根据新节点的编号来修改
    	public void update(HeroNode newHeroNode) {
    		//判断是否为空
    		if(head.next == null) {
    			System.out.println("链表为空");
    			return;
    		}
    		//找到需要修改的节点，根据no编号
    		//定义一个辅助变量
    		HeroNode temp = head.next;
    		boolean flag = false;//表示是否找到该节点
    		while(true) {
    			if(temp == null) {
    				//表示链表已经遍历结束
    				break;
    			}
    			if(temp.no == newHeroNode.no) {
    				flag = true;
    				break;
    			}
    			temp = temp.next;
    		}
    		//根据flag判断是否找到要修改的节点
    		if(flag) {
    			temp.name = newHeroNode.name;
    			temp.nickname = newHeroNode.nickname;
    		}else {
    			System.out.printf("没找到编号%d的节点，不能修改\n",temp);
    		}
    	}
    	
    	//删除节点
    	//思路
    	//1、head节点不能动，因此我们需要一个temp辅助节点，找到待删除节点的前一个节点
    	//2、说明我们在比较时，是让temp.next.no和需要删除的节点的no进行比较
    	public void del(int no) {
    		HeroNode temp = head;
    		boolean flag = false;//表示是否找到待删除节点的前一个节点
    		while(true) {
    			if(temp.next == null) {
    				System.out.println("已经遍历到最后了");
    				break;
    			}
    			if(temp.next.no == no) {
    				//找到了待删除节点的前一个节点temp
    				flag = true;
    				break;
    			}
    			temp = temp.next;//temp后移，才能实现遍历
    		}
    		if(flag){
    			temp.next = temp.next.next;
    		}else {
    			System.out.printf("要删除的节点%d不存在无法删除",no);
    		}
    	}
    	
    	//显示链表，通过遍历
    	public void list() {
    		//先判断链表是否为空
    		if(head.next == null) {
    			System.out.println("链表为空");
    			return;
    		}
    		//因为头节点不能动，因此需要一个辅助变量来遍历
    		HeroNode temp  = head.next;
    		while(true) {
    			//判断是否到链表最后
    			if(temp == null) {
    				break;
    			}
    			//输出节点的信息
    			System.out.println(temp);
    			//将next后移，一定小心，不然是死循环
    			temp = temp.next;
    		}
    	}
    }

###  测试类 ###

package com.atguigu.linkedlist;
    
    public class SingleLinkedListDemo {
    	public static void main(String[] args) {
    		//进行一个测试
    		//先创建节点
    		HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
    		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    		HeroNode hero4 = new HeroNode(4,"公孙胜","入云龙 ");
    		
    		//创建一个链表
    		SingleLinkedList singleLinkedList = new SingleLinkedList();
    		//加入
    //		singleLinkedList.add(hero1);
    //		singleLinkedList.add(hero4);
    //		singleLinkedList.add(hero3);
    //		singleLinkedList.add(hero2);
    		
    		//按照编号加入
    		singleLinkedList.addByOrder(hero1);
    		singleLinkedList.addByOrder(hero4);
    		singleLinkedList.addByOrder(hero3);
    		singleLinkedList.addByOrder(hero2);
    		singleLinkedList.list();
    		//测试修改节点的代码
    		HeroNode newHeroNode = new HeroNode(2,"小卢","*玉麒麟*");
    		singleLinkedList.update(newHeroNode);
    		System.out.println("修改之后的链表：");
    		singleLinkedList.list();
    		
    		//删除一个节点
    		System.out.println("删除一个节点：");
    		singleLinkedList.del(1);
    		singleLinkedList.del(2);
    		singleLinkedList.del(3);
    		singleLinkedList.del(4);
    		singleLinkedList.list();
    	}
    
    }

## **六、控制台输出** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70]: /images/20210813/153893dfd90b407aa890bcb9af6a9630.png
[20200513133039592.png]: /images/20210813/2459c959ce3544ebb10a1bc2d273b450.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 1]: /images/20210813/07fc1cea1d624b4787bd475b53fc8b23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 2]: /images/20210813/eef0d4f3b0644f9dba5779380a938e95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1b3J1aV9qYXZh_size_16_color_FFFFFF_t_70 3]: /images/20210813/fc510bdbeee749eea880870d420a645c.png