1. 全栈程序员必看首页

Java基础–单链表的实现[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 26

Java基础–单链表的实现[通俗易懂]Java内部也有自己的链表–LinkedList，但是我们今天不是讨论LinkedList，而是自己来实现一个单链表，包括简单的增删查改，以及使用链表来实现栈和队列这两种数据结构，涉及的方面如下： 单链表的结构 单链表的基本操作 使用虚拟头结点的单链表 单链表实现栈 单链表实现队列 单链表的结构 一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点…

大家好，又见面了，我是你们的朋友全栈君。

Java内部也有自己的链表–LinkedList，但是我们今天不是讨论LinkedList，而是自己来实现一个单链表，包括简单的增删查改：

  • 单链表的结构
  • 单链表的基本操作
  • 虚拟头结点的使用

整个类的设计如下：

public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
}

单链表的结构

一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的，这也是为什么根据索引无法像数组那样直接就能查询到数据元素。

[单链表结构图]
Java基础--单链表的实现[通俗易懂]

链表存储的结点

private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
}

链表的基本操作

包括链表的增删查改，以及判别某结点是否存在链表中

链表结点的增加

进行结点的添加的时候，是根据索引来进行操作的，由于成员变量size记录了当前链表的元素个数，进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点，记录为pre，把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next；再把pre.next指向node结点。如果先进行pre.next指向要插入的结点，再进行node.next指向pre.next的话，无疑是要插入的结点自己指向了自己，无法连接上整个链表，在链表的操作中，有时候顺序的执行会带来不一样的结果。

//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		//this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}

链表结点的删除

//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}

在进行链表的结点删除时候，要分情况讨论：

当要删除的结点位于头结点的时候：
如下图要删除的元素1的结点位于头结点，先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素，如果是把head指向head.next即可，直接跳过头结点，直到头结点不是要删除的元素就结束循环。

[要删除的元素1位于头结点]Java基础--单链表的实现[通俗易懂]

当要删除的结点不在头结点的时候：如下图删除元素为3的结点，由于上面已经判断了头结点不是要删除的元素，所以我们从头结点的下一个结点开始循环，即cur.next，当cur.next是要被删除的元素时，直接cur.next = curr.next.next就能直接跳过cur.next，断开。
[要删除结点的元素为3的结点]
Java基础--单链表的实现[通俗易懂]

删除链表的头结点的元素和删除链表的尾结点的元素

//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}

经过上面在进行链表的结点删除的时候，会发现在删除的过程中很麻烦，还得考虑头结点（因为我们在删除结点的时候，都是先找到待删除结点del的前一个结点pre，然后直接进行跳过操作，即pre.next = pre.next.next，但是删除结点头结点的时候就无法操作），给我们添加了麻烦，为此我们可以给链表添加一个虚拟的头结点，说白了就是重新new一个结点对象，该结点对象的下一个结点指向了我们之前的头结点，让我们在删除结点的时候，无须再考虑之前的头结点了！

虚拟头结点删除链表元素的实现

//加入虚拟头结点的链表进行删除
	public void removeElt(T t){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(t,this.head);
		//声明结点指向虚拟头结点
		Node cur = dummy;
		//从虚拟头结点的下一个结点开始遍历
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				cur.next = cur.next.next;
				this.size--;
			}
			else cur = cur.next;
		}
		//去除虚拟头结点
		this.head = dummy.next;
	}

使用虚拟头结点进行链表的插入

刚开始那部分的结点添加是基于索引的情况实现，当我们无法知道一个结点的位于链表的哪个位置时候，只知道要插入在某个元素的前面，下面的代码基于上述情况实现。

	/**
	 * 
	 * @param t:插入在t元素的位置
	 * @param des：要插入的元素
	 */
	public void insert(T t,T des){
		//构造虚拟头结点，并且下一个结点指向head
		Node dummy = new Node(null,this.head);
		//构造要插入的结点
		Node dNode = new Node(des);
		//声明变量cur指向虚拟头结点
		Node cur = dummy;
		while(cur.next != null){
			if(cur.next.t.equals(t)){ 
				dNode.next = cur.next;
				cur.next = dNode;
				this.size++;
				break;
			}
			else cur = cur.next;
		}
		this.head = dummy.next;
	}

查找某个元素是否在链表的结点上

//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}

完整的代码实现：

package LinkedList;

public class Linked <T>{
	
	private class Node{
		private T t;
		private Node next;
		public Node(T t,Node next){
			this.t = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private Node head;    		//头结点
	private int size;			//链表元素个数
	//构造函数
	public Linked(){
		this.head = null;
		this.size = 0;
	}
	
	//获取链表元素的个数
	public int getSize(){
		return this.size;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		return this.size == 0;
	}
	//链表头部添加元素
	public void addFirst(T t){
		Node node = new Node(t);	//节点对象
		node.next = this.head;
		this.head = node;
		// this.head = new Node(e,head);等价上述代码
		this.size++;
	}
	//向链表尾部插入元素
	public void addLast(T t){
		this.add(t, this.size);
	}
	//向链表中间插入元素
	public void add(T t,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
		if (index == 0){
			this.addFirst(t);
			return;
		}
		Node preNode = this.head;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index-1; i++){
			preNode = preNode.next;
		}
		Node node = new Node(t);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
	}
	//删除链表元素
	public void remove(T t){
		if(head == null){
			System.out.println("无元素可删除");
			return;
		}
		//要删除的元素与头结点的元素相同
		while(head != null && head.t.equals(t)){
			head = head.next;
			this.size--;
		}
		/**
		 * 上面已经对头节点判别是否要进行删除
		 * 所以要对头结点的下一个结点进行判别
		 */
		Node cur = this.head;
		while(cur != null && cur.next != null){
			if(cur.next.t.equals(t)){
				this.size--;
				cur.next = cur.next.next;
			}
			else cur = cur.next;
		}
		
	}
	//删除链表第一个元素
	public T removeFirst(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		Node delNode = this.head;
		this.head = this.head.next;
		delNode.next =null;
		this.size--;
		return delNode.t;
	}
	//删除链表的最后一个元素
	public T removeLast(){
		if(this.head == null){
			System.out.println("无元素可删除");
			return null;
		}
		//只有一个元素
		if(this.getSize() == 1){
			return this.removeFirst();
		}
		Node cur = this.head;	//记录当前结点
		Node pre = this.head;	//记录要删除结点的前一个结点
		while(cur.next != null){
			pre = cur;
			cur = cur.next;
		}
		pre.next = cur.next;
		this.size--;
		return cur.t;
	}
	//链表中是否包含某个元素
	public boolean contains(T t){
		Node cur = this.head;
		while(cur != null){
			if(cur.t.equals(t)){
				return true;
			}
			else cur = cur.next;
		}
		return false;
	}
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Node cur = this.head;
		while(cur != null){
			sb.append(cur.t+"->");
			cur = cur.next;
		}
		sb.append("NULL");
		return sb.toString();
	}
	
	public static void main(String[] args) {
		Linked<Integer> linked = new Linked();
		for(int i = 0; i < 10; i++){
			linked.addFirst(i);
			System.out.println(linked);
		}
		linked.addLast(33);
		linked.addFirst(33);
		linked.add(33, 5);
		System.out.println(linked);
		linked.remove(33);
		System.out.println(linked);
		System.out.println("删除第一个元素："+linked.removeFirst());
		System.out.println(linked);
		System.out.println("删除最后一个元素："+linked.removeLast());
		System.out.println(linked);
	}
}

总结：学链表是一种痛苦，但是痛苦并快乐着，希望能够坚持下去，把链表的全家桶都学习了，而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正！下篇文章将进行用链表实现栈和队列。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/130306.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 图像数字化的两种方式是_图像是如何数字化的

    图像数字化的两种方式是_图像是如何数字化的

    图像数字化的两种方式是_图像是如何数字化的将图片存储为数据有两种方案。其一为位图，也被称为光栅图。即是以自然的光学的眼光将图片看成在平面上密集排布的点的集合。每个点发出的光有独立的频率和强度，反映在视觉上，就是颜色和亮度。这些信息有不同的

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月1日
    5
  • Macbook OBS 录制系统声音

    Macbook OBS 录制系统声音

    Macbook OBS 录制系统声音安装好OBS软件下载并安装soundflower软件，也可以在GitHub中下载打开midi音频设置构建多输出设备例如，我现在是带着外置耳机，并且录制系统声音，那么多输出设备就勾选这两个配置完成后，我们可以右键选择该设备用于声音输出最后在OBS软件中选择桌面音频即可，点击Soundflower…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月27日
    56
  • C++ GetUserName()

    C++ GetUserName()

    C++ GetUserName()

    全栈程序员-站长的头像 全栈程序员-站长
    2022年3月12日
    42
  • Python新手进阶教程之1、海龟作图——用Python绘图（1）「建议收藏」

    Python新手进阶教程之1、海龟作图——用Python绘图（1）「建议收藏」

    Python新手进阶教程之1、海龟作图——用Python绘图（1）「建议收藏」1.1海龟的作用使用海龟作图，我们不仅能够只用几行代码就创建出令人影响深刻的视觉效果，而且还可以跟海龟看看几行代买如何影响到它的移动。者能够帮助我们理解代码的逻辑。1.2第一个海龟程序让我们使用海龟作图来编写第一个程序。在一个新的IDLE窗口中输入如下的代码并将其保存为Square.py#Square.py-画一个正方形importturtlet=turtle.Pen()foriinrange(100):t.forward(x)t.left(90)

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月28日
    32
  • 在java中jar与war和pom的区别

    在java中jar与war和pom的区别

    在java中jar与war和pom的区别

    全栈程序员-站长的头像 全栈程序员-站长
    2021年7月20日
    66
  • 如何制作离线tts?「建议收藏」

    如何制作离线tts?「建议收藏」

    如何制作离线tts?「建议收藏」tts->把文字转化为语音。先把中文转化为拼音。这个主要依靠1个字典，能把汉字和读音对应。下面提供字典:丂yu丄shang丅xia丆shi丏mian丗shi丟diu丠qiu両liang丣you並bing丩jiu丮ji丯jie丱kuang丳chan丵zhuo丷ba丼jing乀fu乁yi乂yi乆jiu乊hu乑yin乕hu乗sheng乚yin乛zhe乢gai乣jiu乨shi乪nang乴xue乵yan乸na乹qian乿luan

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月21日
    34

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号