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

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

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