java实现单链表的增删改查与排序

深藏阁楼爱情的钟 2022-07-12 08:24 214阅读 0赞

LinkNode

package LinkList;
    
    class Node{
    	public Node next;
    	public int data;
    	public Node(int data){
    		this.data=data;
    	}
    }
    public class LinkList{
    	public Node head;
    	public int length=0;
    	//打印链表
    	public void printLinkList()
    	{
    		Node p=head;
    		while(p!=null)
    		{
    			System.out.println(p.data);
    			p=p.next;
    		}
    		System.out.println("长度为 ："+length);
    	}
    	//判断链表是否为空
    	public Boolean isEmpty()
    	{
    		if(head==null)
    			return true;
    		return false;
    	}
    	//尾插法添加结点
    	public void addLastNode(int data)
    	{
    		Node x=new Node(data);
    		if(head==null)
    		{
    			head=x;length++;
    			return;
    		}
    		Node q=head;
    		while(q.next!=null)
    			q=q.next;
    		q.next=x;
    		length++;
    	}
    	//头插法添加结点
    	public void addHeadNode(int data)
    	{
    		Node x=new Node(data);
    		if(head==null){
    			head =x;length++;
    			return;
    		}
    		x.next=head;
    		head=x;
    		length++;
    	}
    	//删除结点
    	public Boolean deleteNode(int index)
    	{
    		if(index<1||index>length)
    			return false;
    		int i=1;
    		Node p=head;
    		while(i!=(index-1))
    		{
    			p=p.next;
    			i++;
    		}
    		
    		(p.next)=(p.next.next);
    		length--;
    		return true;
    	}
    	//修改结点
    	public Boolean updateNode(int index,int data)
    	{
    		if(index<1||index>length)
    			return false;
    		int i=1;
    		Node p=head;
    		while(i<index)
    			{p=p.next;i++;}
    		p.data=data;
    		return true;
    	}
    	//向前冒泡，因为冒泡是相邻俩俩进行比较，所以容易知道，当一轮排序发现顺序没有发生改变则数列已经有序 这样可以提高效率
    	public void SortLinkList()
    	{
    		Boolean flag=false;
    		Node p=head;
    		Node q=null;
    		for(int i=0;i<length-1;i++)
    		{	
    			q=p.next;
    			for(int j=i;j<length-1;j++)
    			{
    				if(p.data>q.data)
    				{
    					int t=p.data;
    					p.data=q.data;
    					q.data=t;
    					flag=true;
    				}
    				q=q.next;
    			}
    			if(flag==false)
    				break;
    			flag=false;
    			p=p.next;
    		}
    	}
    }

测试：

package LinkList;
    public class MyLinkedList {
    	public LinkList linkList=new LinkList();
    	public void testaddLastNode(){
    		linkList.addLastNode(1);
    		linkList.addLastNode(2);
    		linkList.addLastNode(3);
    		linkList.addLastNode(4);
    		linkList.printLinkList();
    	}
    	public void testaddHeadNode()
    	{
    		linkList.addHeadNode(1);
    		linkList.addHeadNode(2);
    		linkList.addHeadNode(3);
    		linkList.addHeadNode(4);
    		linkList.printLinkList();
    	}
    	public void testdaleteNode()
    	{
    		if(linkList.deleteNode(3)==false)
    			System.out.println("删除位置有误");
    		linkList.printLinkList();
    	}
    	public void testUpateNode()
    	{
    		if(linkList.updateNode(2, 10)==false)
    			System.out.println("修改位置有误");
    		linkList.printLinkList();
    	}
    	public void testSortLinkList()
    	{
    		linkList.SortLinkList();
    		linkList.printLinkList();
    	}
    	
    	public static void main(String[] args) {
    		MyLinkedList main=new MyLinkedList();
    		main.testaddHeadNode();
    		System.out.println("================================");
    		main.testSortLinkList();
    	}
    }

补充：对于冒泡排序，由于是相邻俩俩进行比较的，所以当一次循环查找发现顺序没有改变，则可以判断，序列已有序

对于删除结点，java与c/c++最大的不同在于java不用手动进行删除结点的释放空间，这是由于Java有自动处理垃圾的机制gc

在这里补充一下Java的GC处理机制：

对对象而言，如果没有任何变量去引用它，那么该对象将不可能被程序访问，因此可以认为他是垃圾信息，可以被回收，只要有一个以上的变量引用该对象，该对象就不会被回收。所以也就很好解释在这里为什么我不用手动释放空间了。

垃圾回收都是依据一定的算法进行的，下面介绍其中几种常用的垃圾回收算法

（1）引用计数法（Reference Counting Collerctor）

引用计数作为一种简单但是效率较低的方法，其主要原理如下：在堆中对每个对象都有一个计数器；当对象被引用时，引用计数器+1；当引用被置为空或离开作用域的时候，引用计数-1，由于这种方法无法解决相互引用的问题，因此JVM没有采用这个算法

（2）追踪回收算法（Tracing Collector）

追踪回收算法利用JVM维护的对象引用图，从根节点开始遍历对象的应用图，同时标记遍历到的对象，当遍历结束后，未被标记的对象就是目前已不被使用的对象，可以回收。

（3）压缩回收算法（Compacting Collector）

压缩回收算法的思路如下：把堆中活动的对象移动到堆中一端，这样就会在堆中另外一端留出很大的一块空闲区间，相当于对堆中的碎片进行了处理。虽然这种方法可以大大消除堆碎片的工作，但是每次处理都会带来性能的损失。

（4）复制回收算法（Coping Collector）

复制回收算法的思路：把堆分为俩个大小相同的区域，在任何时刻，只有其中一个区域被使用，直到这个区域被消耗完为止，此时垃圾回收期就会中断程序的执行，通过遍历的方式把所有活动的对象复制到另外一个区域中，在复制的过程中它们是紧挨着布置的，从而可以消除内存碎片。当复制过程结束后程序会接着运行，知道这块区域被使用完，然后再采用上面的方法继续进行垃圾回收。

（5）按代回收算法（Generational Collector）

复制回收算法主要的缺点如下：每次算法执行时，所有出于活动状态的对象都要被复制，这样效率很低。由于程序有生命周期长短之分而大部分都是生命周期比较短的，因此可以根据这个特点对算法进行优化。按代回收算法的主要思路如下：把堆分为俩个或多个子堆，每一个子堆被视为一代。算法在运行的过程中优先收集那些“年幼”的对象，如果一个对象经过多次收集仍然“存活”，那么就可以把这个对象转移到高一级的堆里，减少对其的扫描次数。