数据结构（Java实现）之单向链表的节点表示、插入、删除、单向链表反转和串联

曾经终败给现在 2022-05-25 03:24 114阅读 0赞

单向链表是列表中常用的一种，所有节点串成一列，而且指针所指的方向一样。列表中每个数据除了要存储原本的数据，还必须存储下一个数据的存储地址。下面的程序示例演示了如何构建链表节点，向单向链表插入节点、删除节点、反转单向链表和串联两个单向链表：

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Random;
    
    class Node {
    	int data;
    	int np;
    	String names;
    	Node next;
    
    	public Node(int data,String names,int np) {
    		this.np=np;
    		this.names=names;
    		this.data=data;
    		this.next=null;
    	}
    }
    
    class LinkedList {
    	public Node first;
    	public Node last;
    	public boolean isEmpty()
    	{
    		return first==null;
    	}
    	
    	public void print()
    	{
    		Node current=first;
    		while(current!=null)
    		{
    		System.out.println("["+current.data+" "+current.names+" "+current.np+"]");
    		current=current.next;
    		}
    		System.out.println();
    	}
    	
    	public void insert(int data,String names,int np) {  //向链表中插入节点
    		Node newNode=new Node(data,names,np);
    		if(this.isEmpty())
    		{
    			first=newNode;
    			last=newNode;
    		}
    		else
    		{
    			last.next=newNode;
    			last=newNode;
    		}
    	}
    
    	public void delete(Node delNode) {   //删除单向链表的节点
    		Node newNode;
    		Node tmp;
    		if(first.data==delNode.data)
    		{
    			first=first.next;
    		}
    		else if(last.data==delNode.data) {
    			System.out.println("I am here\n");
    			newNode=first;
    			while(newNode.next!=last) newNode=newNode.next;
    			newNode.next=last.next;
    			last=newNode;
    	           }
    		else {
    			newNode=first;
    			tmp=first;
    			while(newNode.data!=delNode.data) {
    				tmp=newNode;
    				newNode=newNode.next;
    			}
    			tmp.next=delNode.next;
    		}
    	}
    	public void reverse(){   //单向链表的反转
    		Node current=first;
    		Node before=null;
    		Node nnext;
    		System.out.println("反转后的列表数据:");
    		while(current!=null){
    			nnext=current.next;
    			current.next=before;
    			before=current;
    			current=nnext;
    		}	
    		/*while(current!=null)
    		{
    			last=before;
    			before=current;
    			current=current.next;
    			before.next=last;
    		}*/
    		current=before;
    		while(current!=null) {
    			System.out.println("["+current.data+" "+current.names+" "+current.np+"]");
    			current=current.next;
    		}
    		System.out.println();
    	}
    	public static LinkedList connection(LinkedList head, LinkedList tail) {
    		while(head.last.next !=null)    //可能单向链表的last并不指向最后一个节点，所以需要找到head的最后一个节点
    			head.last=head.last.next;
    		head.last.next=tail.first;
    		return head;
    	}
    }
    
    public class ReverseLinkedListTest {
    	public static void main(String args[]) throws IOException {
    		BufferedReader buf;
    		buf=new BufferedReader(new InputStreamReader(System.in));
    		Random rand=new Random();
    		LinkedList list =new LinkedList();
    		LinkedList list2 =new LinkedList();
    	    int i,j,findword=0,data[][]=new int[12][10];
    	    String name[]=new String[] {"Allen","Scott","Marry","Jon","Mark","Ricky","Lisa","Jasica","Hanson","Amy","Bob","Jack"};
    	    String name2[]=new String[] {"Blake","Paul","Peter","Poppy","Pony","Brenda","Bruce","Rey","Rehona","Remo","Wilson","Van"};
    	    System.out.println("学号\t成绩\t学号\t成绩\t学号\t成绩\t学号\t成绩\n ");
    	    System.out.println("单向链表1:");
    	    for (i=0;i<12;i++)
    	    {
    	    	data[i][0]=i+1;
    			data[i][1]=(Math.abs(rand.nextInt(50)))+50;
    			list.insert(data[i][0],name[i],data[i][1]);
    		}
    	    for (i=0;i<3;i++)
    		{
    			for(j=0;j<4;j++)
    			System.out.print("["+data[j*3+i][0]+"]  ["+data[j*3+i][1]+"]  ");
    			System.out.println();
    		}
    	    
    	    System.out.println("单向链表2:");
    	    for (i=0;i<12;i++)
    	    {
    	    	data[i][0]=i+13;
    			data[i][1]=(Math.abs(rand.nextInt(50)))+50;
    			list2.insert(data[i][0],name[i],data[i][1]);
    		}
    	    for (i=0;i<3;i++)
    		{
    			for(j=0;j<4;j++)
    			System.out.print("["+data[j*3+i][0]+"]  ["+data[j*3+i][1]+"]  ");
    			System.out.println();
    		}
    	    
    	    LinkedList.connection(list,list2).print(); //两个单向链表的串联
    	    
    	    while(true)     //测试删除单向链表节点
    	    {
    	    	System.out.print("输入要删除成绩的学号，结束输入-1： ");
    	    	findword=Integer.parseInt(buf.readLine());
    	    	if(findword==-1)
    	    		break;
    	    	else
    	    	{
    	    		Node current=new Node(list.first.data,list.first.names,list.first.np);
    	    		current.next=list.first.next;
    	    		while(current.data!=findword) current=current.next;
    	    		list.delete(current);
    	    	}
    	    	System.out.println("删除后成绩列表，请注意！要删除的成绩其学号必须在此列表中\n");
    	    	list.print();
    	    }
    	    list.reverse();    //测试反转单向链表
    	}
    }

上面程序中connection方法还可以修改为如下：

public LinkedList connection(LinkedList tail) {
    		LinkedList head;
    		head=this;
    		while(head.last.next !=null)    //可能单向链表的last并不指向最后一个节点，所以需要找到head的最后一个节点
    			head.last=head.last.next;
    		head.last.next=tail.first;
    		return head;
    	}

调用时则变为list.connection(list2).print