Java数据结构和算法-5-单链表方法

男娘i 2022-03-09 01:16 151阅读 0赞

先了解下什么是链表？通过火车的多节车厢我们来下形容链表。每节车厢都有两个信息，头节点和尾节点，当然有两头我们叫双链表。我们先来看看单向链表，就是链表中节点与节点之间只考虑头节点。

用图来表示一个简单的单向链表。

![20190326202732154.png][]

上面这个图就是一个单链表（list），一个节点（node）中分成两部分，一个用来存储数据，一个是存储下一个节点的内存地址，其实就是指针。根据指针寻找下一个节点，从而找到下一个节点的数据。本篇，我们就来学习一个单链表的基本操作。我们封装的自定义类和方法就是Java JDK中自带的ArrayList的效果。

链表基本方法封装

我们需要两个类，一个类Node.java是定义一个节点，结点有数据和指向下一个结点的内存地址。第二个是我们单链表的方法封装，我们先来看看如何插入一个结点的代码实现过程。先理解插入结点代码和打印结点方法的代码，其他删除，插入就变得容易理解。

Node.java内容

package list;
    
    /*
     * 链结点，相当于一个火车车厢
     */
    public class Node {
    	//数据域
    	public long data;
    	//结点域（指针）
    	public Node next;
    	
    	public Node(long value) {
    		this.data = value;
    	}
    	
    	/*
    	 * 显示结点的值
    	 */
    	public void display() {
    		System.out.print(data + " "); //加一个空格，打印效果好看
    	}
    }

LinkList.java内容

先看看插入结点的方法，因为我们每次插入都是在新的链表的头结点之后去插入数据。我们这里，暂时不考虑指定结点后面插入结点，我们先每次插入都是在第一个结点之后插入结点。

public void insertFirst(long value) {
    	Node node = new Node(value);
    	node.next = first;
    	first = node;
    }

第一行是实例化一个Node对象，这个结点的数据值是value, 也就是要把新插入的结点先实例化出来。然后这个新结点指向原来存在的第一个结点。所以上面第二行把first的内存地址赋值给了node.next。第三行，因为插入了新结点，所以把新插入的结点重置为链表的头结点。下面画图来演示一下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

上面图，本来我们头结点是一个32，接下来我们在头结点之后插入一个新结点，就是上面48这个数据，插入之后的效果是这样的：48在32的后边，看箭头顺序来决定前后顺序。

下面看看链表中打印链表的方法代码

public void display() {
    	Node current = first;
    	while(current != null) {
    		current.display();
    		current = current.next;
    	}
    	System.out.println();
    }

假如当前结点从头结点开始，开始while循环，如果当前结点不为空，就调用结点本身的display()方法，打印这个结点本身的数据。打印完一个结点之后，把当前结点指向下一个结点重置为当前结点，继续判断是否为空和打印。

下面，我们来写一个测试LinkList.java的代码，插入五个结点，并打印结点看看效果。

运行效果

19 57 48 32 24

这个打印效果和对应插入的顺序，确实是每次都在头结点之后插入新结点。

根据上面的基础，我们来写删除结点方法和查找结点方法。

package list;
    
    /*
     * 链表 相当于火车
     */
    public class LinkList {
    	//头结点
    	private Node first;
    	
    	public LinkList() {
    		first = null;
    	}
    	
    	/*
    	 * 插入一个结点方法,是在头结点之后插入
    	 */
    	public void insertFirst(long value) {
    		Node node = new Node(value);
    		node.next = first;
    		first = node;
    	}
    	
    	/*
    	 * 打印链表结点内容
    	 */
    	public void display() {
    		Node current = first;
    		while(current != null) {
    			current.display();
    			current = current.next;
    		}
    		System.out.println();
    	}
    	
    	/*
    	 * 查找方法
    	 */
    	public Node find(long value) {
    		// 从头结点开始循环判断
    		Node current = first;
    		while(current.data != value) {
    			// 如果结点中的值不匹配，需要判断当前结点下一个是否为空，如果为空就说明查找不到改数据
    			if(current.next == null) {
    				return null; //查找不到
    			}
    			// 继续查找下一个节点
    			current = current.next;
    		}
    		//上面把不等于的结点都循环和查找不到情况都写了，剩下退出循环就是要查找的
    		return current;
    	}
    	
    	/*
    	 * 删除结点，在头结点之后进行删除
    	 */
    	public Node deleteFirst() {
    		Node tmp = first.next;
    		first.next = tmp.next;
    		return tmp;
    	}
    
    }

测试类代码

package list;
    
    public class TestLinkList {
    
    	public static void main(String[] args) {
    		LinkList ll = new LinkList();
    		ll.insertFirst(24);
    		ll.insertFirst(32);
    		ll.insertFirst(48);
    		ll.insertFirst(57);
    		ll.insertFirst(19);
    		ll.display();
    		
    		//查找48这个结点
    		Node node = ll.find(48);
    		node.display();
    		System.out.println();
    		//删除结点
    		ll.deleteFirst();
    		ll.display();
    	}
    
    }

测试结果

19 57 48 32 24 
    48 
    19 48 32 24

下面继续写一个删除方法，根据data的值去删除这个结点。

/*
    	 * 删除方法，根据数据来删除结点
    	 */
    	public Node delete(long value) {
    		//当前结点从头结点开始
    		Node current = first;
    		//表示当前结点的前面一个结点
    		Node previous = first;
    		//删除也是根据查找的逻辑先去找到才能删除
    		while(current.data != value) {
    			// 如果结点中的值不匹配，需要判断当前结点下一个是否为空，如果为空就说明查找不到改数据
    			if(current.next == null) {
    				return null; //查找不到
    			}
    			//找到了就进行删除，删除的逻辑是当前找到这个结点是要删除
    			//只需要把当前结点前面一个结点.next指向了当前结点后面一个结点
    			previous = current;
    			current = current.next;
    		}
    		
    		//如果一开始就找到了
    		if(current == first) {
    			first = first.next;
    		}else {
    			previous.next = current.next;
    		}
    		return current;
    	}

[20190326202732154.png]: /images/20220309/9b23f1f662b744daa94d65098419ea18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220309/8782261a7c4e4cccbae4039e2fd8fc4f.png