Java实现--单链表

 
       在链表的环境中，很容易堆“引用”产生混淆。在Link的类定义中定义以个Link类型的域，这看起来很奇怪。
编译器怎样才能不混淆呢？编译器在不知道一个Link对象占多大空间的情况下，如何能知道一个包含了相同对象的Link对象占用多大空间呢？
其实，Link对象并没有真正包含另外一个Link对象，学过C语言或者C++的同学知道，其实这就类似于指针，该引用只是一个堆某个对象的参照数值，
它是一个计算机内存中的对象地址，没错，它是一个地址，它告诉对象在哪里，你只需要引用这个地址就可以找到这个对象了。

 

以下为代码，有详细注释：

/**
 * 定义一个结点类
 * @author Administrator
 *
 */
public class Link {
	public int data;	//数据域
	public Link next;	//指向下一个结点
	
	public Link(int data) {
		super();
		this.data = data;
	}
	
	//打印结点的数据域
	public void diaplayLink() {
		System.out.print("{"+ data + "} ");
	}
}

/**
 * 定义一个单链表（头插法）
 * @author Administrator
 *
 */
public class LinkList {
	private Link first;
	
	public LinkList() {
		first = null;
	}
	
	public boolean isEmpty() {
		return (first==null);
	}
	
	//在头部插入结点
	public void Insert(int data) {
		Link newNode = new Link(data);
		newNode.next = first;		//新结点的next指向原先的first结点 比如第一个：newNode.next--->null;
		first = newNode;			//first指向新的结点 即first--->newNode--->...--->null
	}
	
	//删除第一个数据结点,并且返回删除数据
	public Link delete() {
		Link temp = first;
		first = first.next;  //first--->first.next （first指向第二个数据结点）
		return temp;
	}
	
	//查找指定数据的结点
	public Link find(int key) {
		Link current = first;			//获取第一个数据结点
		while(current.data!=key) {		//只要当前结点current的数据不是key就一直遍历下去
			if(current.next==null) {	//若current.next==null，表示当前结点是最后一个结点，意味着链表没有这个值，返回null
				return null;			
			}else {
				current = current.next;//若上述情况不成立，那么将current.next赋给current
			}
		}
		return current;//可以执行到这一步，说明找到了一个结点的data==key，返回该结点
	}
	
	//删除指定数据的结点
	public Link delete(int key) {
		Link current = first;			//获取当前结点
		Link previous = first;			//获取当前结点，方便删除结点
		while(current.data!=key) {		//只要当前数据不等于key，则一直遍历下去
			if(current.next == null) {	//如果current.next==null表示当前结点是最后一个结点或者链表为空，意味着找不到key，返回null
				return null;
			}else {
				previous = current;		//否则将当前结点赋给previous表示上一个结点
				current = current.next  ;	//然后将当前结点的下一个结点赋给当前结点，即current = current.next
			}
		}
		if(current==first) {		//如果current==first，表示第一个结点的data与key是相等的，为了删除该结点，first指向first.next（即第二个结点）
			first = first.next;		//和delete操作相同
		}else {
			previous.next = current.next;	//否则将current即当前结点的上一个结点previous.next和下一个结点current.next相连
		}
		return current;		//返回删除的结点
	}
	
	
	//演绎链表
	public void displayList() {
		System.out.print("List(first--->last): ");
		Link current = first;	//first不能去动它，如果动了first再插入的时候就不是在头部插入了
		while(current!=null) {
			current.diaplayLink();	//打印数据
			current = current.next ;	//获取下一个结点
		}
		System.out.println();
	}
}

/**
 * 测试刚刚创建的链表
 * @author Administrator
 *
 */
public class TestLink {
	public static void main(String[] args) {
		LinkList theList = new LinkList();
		theList.Insert(22);
		theList.Insert(44);
		theList.Insert(66);
		theList.Insert(88);
		
		theList.displayList();
		while(!theList.isEmpty()) {
			Link aLink = theList.delete();
			System.out.print("Deleted: ");
			aLink.diaplayLink();
			System.out.println();
		}
		theList.displayList();
		System.out.println("-----------------------------------------------------------------\n");
		System.out.println("Add find(key) and delete(key):\n");

		
		theList.Insert(33);
		theList.Insert(55);
		theList.Insert(77);
		theList.Insert(99);
		theList.displayList();
		Link f = theList.find(77);
		if(f!=null) {
			System.out.println("Find link with key: "+f.data);
		}else {
			System.out.println("Can't find link");
		}
		
		Link d = theList.delete(77);
		if(d!=null) {
			System.out.println("Delete link with key: "+d.data);
		}else {
			System.out.println("Can't Delete link.");
		}
		theList.displayList();
	}
}

运行结果：

 

List(first--->last): {88} {66} {44} {22} 
Deleted: {88} 
Deleted: {66} 
Deleted: {44} 
Deleted: {22} 
List(first--->last): 
-----------------------------------------------------------------

Add find(key) and delete(key):

List(first--->last): {99} {77} {55} {33} 
Find link with key: 77
Delete link with key: 77
List(first--->last): {99} {55} {33}