重走算法路之链表指定节点属性的删除和插入

      我们知道数组是我们很熟悉的一种存放数据的东西，但是它的问题我们也知道，一经创建它的大小也就固定了，固定存在着一个重要的问题“内存浪费”和“内存溢出”，也就是它不能动态的变换它的大小，而链表就很好的解决了这个问题，它是动态的，大小随着加入和删除节点而变化着自己的大小，java自带的垃圾回收也会处理被删除的节点。释放出内存。我们还知道，数组在查看元素上面是它的强项，同过它的下标，时间复杂度为O(1),就能定位到元素，链表在这个方面就差一点了，因为要想查看一个元素，必须遍历链表找到相应的元素，时间复杂度到了O(n)，各有长处，也各有短处，这也像我们人一样嘛，人无完人，各有长短。

       今天写了一下链表，实现链表“指定属性对比”的插入和删除。链表的节点是我们自己定义的类型，当然可一封装我们自己的属性，可一放一个人，放一辆车等等，类当然就可以封装自己的属性。

 

    先定义一个简单的Link类，用它来生成对象，放到链表的每个节点上。代码如下：

      

package 链表;

/*
 * 节点类，封装了属性
 * @author TMS
 *
 */
public class Link {
	public int id;
	public double data;
	public Link next;         //定义下一个节点
	
	/*
	 * 初始化节点的属性
	 */
	public Link(int id,double data) {  
		this.id = id;
		this.data = data;
	}
   
	/*
	 * 打印出每个节点的信息
	 */
    public void displayLink() {
    	System.out.println("id = "+id+" "+"data = "+data);
    }
}

    接下来就是定义的一个链表类，相应的代码如下，有详细的注释：

    

package 链表;

public class Linklist {

	private Link first;
	
	/*
	 * 构造函数初始化第一个节点为null
	 */
	public Linklist() {
		first = null;
	}

	/*
	 * 在链表的头部插入一个元素
	 */
	public void insertFirst(int id, double data) {
		Link newLink = new Link(id, data);
		newLink.next = first;
		first = newLink;
	}

	 /*
	 * 指定匹配属性key查找相应的节点
	 * 使用循环遍历整个链表
	 */
	public Link findLink(int key) {
		Link temp = first;
		while (temp.id != key) {
			if (temp.next == null) {
				return null;
			} else {
				temp = temp.next;
			}
		}
		return temp;
	}

	/*
	 * 删除指定key值的节点
	 * 遍历整个链表找到对应的节点，找不到返回null
	 */
	public Link deletLink(int key) {
		Link temp = first;
		Link old = first;
		while (temp.id != key) {
			if (temp.next == null) {
				return null;               // 找到末尾了都没有找到
			} else {
				old = temp;
				temp = temp.next;
			}
		}                                  // 循环结束找到了

		if (temp == first)                 // 如果恰好要删除的是第一个节点，直接first = first.next;
			first = first.next;
		else
			old.next = temp.next;          //要删除的节点在中间
		return temp;                       
	}
	
	
	/*
	 * 打印链表中的节点
	 * 遍历打印整个链表
	 */
	public void displayList() {
		Link temp = first;
		while(temp != null) {
			temp.displayLink();
			temp = temp.next;
		}
	}
	
	/*
	 * 查看找到相应key值的节点
	 */
	public void lookFindNode(Link link) {
		if(link != null) {
			System.out.println("找到了相应的key值的节点 ："+link.data);
		}
		else{
			System.out.println("没有找到相应的key值的节点！");
		}
	}
	
	/*
	 * 查看删除相应key的节点
	 */
	public void lookdeletNode(Link link) {
		if(link != null) {
			System.out.println("节点已经删除，为："+link.data);
		}
		else {
			System.out.println("没有删除相应的节点");
		}
	}
	
	/*
	 * main方法进行测试
	 */
	public static void main(String[] args) {
		Linklist list = new Linklist();
		list.insertFirst(1, 10.0);
		list.insertFirst(2, 20.0);
		list.insertFirst(5, 30.0);
		list.insertFirst(7, 40.0);
		list.insertFirst(3, 50.0);
		
		System.out.println("打印插入的元素：");
		list.displayList();
		
		System.out.println("<------------------------------------------>");
		
		System.out.println("查找相应key值的节点：");
		Link l = list.findLink(8);
		list.lookFindNode(l);
		Link l2 = list.findLink(2);
		list.lookFindNode(l2);
		
		System.out.println("<------------------------------------------>");
		System.out.println("删除相应key值的节点：");
		Link l3 = list.deletLink(10);
		list.lookdeletNode(l3);
		
		Link l4 = list.deletLink(7);
		list.lookdeletNode(l4);
		
		System.out.println("删除后：");
		list.displayList();
		
	}
}

 

    测试输出结果：

   

打印插入的元素：
id = 3 data = 50.0
id = 7 data = 40.0
id = 5 data = 30.0
id = 2 data = 20.0
id = 1 data = 10.0
<------------------------------------------>
查找相应key值的节点：
没有找到相应的key值的节点！
找到了相应的key值的节点 ：20.0
<------------------------------------------>
删除相应key值的节点：
没有删除相应的节点
节点已经删除，为：40.0
删除后：
id = 3 data = 50.0
id = 5 data = 30.0
id = 2 data = 20.0
id = 1 data = 10.0

  

   PS:好，结束一天，洗洗睡了。链表的知识和形式还有很多，期待下一发。