双向链表

    数据结构中的顺序表，可分为物理位置相邻和物理位置不相邻。物理位置相邻且逻辑关系也相邻的我们一般最熟悉的便是数组了，这种结构的特点是可以实现随机存储，但是对于插入删除这些操作来说则极为不便。而链表正是克服了数组的缺点，但同时也有着查找不方便的缺点。链表上的元素虽然在物理上不一定连续，但是在逻辑上一定是连续的。在Java中，有专门实现链表的类：LinkedList。但我们依旧有必要知道如何自定义链表以及链表操作的实现，毕竟有些时候我们要自定义合适的链表从而来满足自己的要求。

    链表最基本的元素就是节点(node)了。节点包含两部分，数据域和指针域。由此，便可以由n个节点连接而成一个链表。整个链表的读取必须从头指针开始。为此，要专门存储头节点。在Java中，由于没有指针这个概念，我们就必须借助地址的引用，将下一个节点的地址存到自己上一个节点中的指针域(只是为了称呼方便而已）。链表分为循环链表（Circular Linked List）、双向链表（Double Linked List）、单向链表、双向循环链表。

    双向链表的具体原理演示：http://www.cnblogs.com/image-eye/archive/2011/07/12/2104436.html

    下面给大家看看我用自定义的Hash函数实现的链表的去除重复和无序化。漏洞很多，但是基本的思想都有了。

     分为四个类：学生类、节点类、链表类、主函数类。

     学生类：主要用于数据测试

 

      public class Student {
	//私有化名字
	private String name;
	//学分
	private int score;
	
	//设置名字
	public void setName(String name){
		this.name = name;
	}
	
	//获得名字
	public String getName(){
		return name;
	}
	
	//学分
	public void setScore(int score){
		this.score = score;
	}
	
	//获得学分
	public int getScore(){
		return score;
	}

}

 

      节点类：链表的基本构成单元

public class LinkNode<E> {
//节点内的数据对象
private E e; 
//节点的下一个引用
private LinkNode<E> child;
//节点的上一个引用
private LinkNode<E> parent;

public LinkNode(E e){
this.e = e;
}
//设置值
public void setObj(E e){
this.e = e;
}
//得到值
public E getObj(){
return e;
}
//设置孩子节点
public void setChild(LinkNode<E> child){
this.child = child;
}

//得到孩子节点
public LinkNode<E> getChild(){
return child;
}
//父节点
public void setParent(LinkNode<E> last){
this.parent = last;
}

public LinkNode<E> getParent(){
return parent;
}


}

     链表类：实现链表的各种操作

    public class LinkList {

	public static LinkNode<Object> front = null;
	public static LinkNode<Object> last = null;
	Student[] opArray = new Student[79];
	
	/**
	 * 往链表中添加元素
	 * @param obj 数据
	 */
	public void add(Student s1){
		//得到关键值
		int key = hashKey(s1);
		//得到新的Hash表
		isPut(key,s1);
		//将原来的表置空
		front = null;
		last = null;
		//遍历数组，按顺序保存不是null的数组元素
		for(int i = 0;i < opArray.length; i++){
			//创建一个新的节点
			if(opArray[i] != null){
				Student temp = opArray[i];
				LinkNode<Object> node = new LinkNode<Object>(temp);
				if(null == front){//如果链表为空
					front = node;
					last = front;
				}else{
					last.setChild(node);
					node.setParent(last);
					last = node;
				}
			}
			
		}
		
	}
	/**
	 * 得到关键值
	 * @param obj 具体的数值
	 * @return  返回Hash的关键值
	 */
	public int hashKey(Student stu){
		int key = 0;
		String nameString = stu.getName();
		int len = nameString.length();
		char[] dst = nameString.toCharArray();
//		nameString.getChars(0,len - 1, dst, 0);
		for(int i = 0; i < len; i++){
//			System.out.println((int)dst[i]);
			key += (int)dst[i];
		}
		key += stu.getScore();
		key %= 79;
//		System.out.println("最初得到的key:"+key);
		return key;
	}
	
	/**
	 * 是否冲突以及冲突的处理
	 * @param key
	 * @param 对象变量
	 */
	public void isPut(int key,Student stu){
		//处理冲突的方法
		while(opArray[key] != null && key < opArray.length){
//		while(!stu.getName().equals(opArray[index].getName()) && opArray[index] != null && index < opArray.length){
		   key++;
		}
		//当搜索到数组尾依旧没有找到合适的位置时
		if(key == opArray.length){
			key = 0;
			isPut(key,stu);
		}else{
//			System.out.println("我的key:"+key);
//			System.out.println("执行了");
			opArray[key] = stu;
			return;
		}
	}
	
	/**
	 * 得到链表的长度
	 * @return：链表的长度
	 */
	public int getLength() {
		int count = 0;
		if(front == null){
			return count;
		}
		count++;
		LinkNode<Object> node = front.getChild();
		while(null!=node){
			count++;
			node = node.getChild();
		}
		return count;
	}
	
	/**
	 * 根据索引取出节点
	 * @param index:第几个节点
	 * @return:根据索引返回的节点
	 */
		public LinkNode<Object> getLinkNode(int index) {
			if(this.getLength() < index || index < 0){
				throw new java.lang.RuntimeException("下标越界： "+index+",size:"
						+this.getLength());
			}
			else{
				int num = 0;
				LinkNode<Object> node = front;
				while(num != index){
					node = node.getChild();
					num++;
				}
				return node;
			}
		}
		
		
	/**
	 * 删除节点
	 * @param index 指定位置
	 */
	public void deleteLinkNode(int index){
		if(this.getLength() < index || index < 0){
			throw new java.lang.RuntimeException("下标越界：" + index + ",size:"
					+this.getLength());
		}else{
			//得到当前索引位置的节点
			LinkNode<Object> node = this.getLinkNode(index);
			//得到父节点
			LinkNode<Object> fNode = node.getParent();
			//得到子节点
			LinkNode<Object> cNode = node.getChild();
			if(fNode == null){
				front = cNode;
			}else if(cNode == null){
				fNode.setChild(null);
			}else{
				fNode.setChild(cNode);
				cNode.setParent(fNode);
			}
		}
	}
	
	/**
	 * 删除某个对象在Hash数组上的储存
	 * @param index
	 */
	public void deleteHash(int index){
		//得到当前索引位置的节点
		LinkNode<Object> node = this.getLinkNode(index);
		//得到关键字的储存位置并且删除
		for(int i = 0; i < opArray.length; i++){
			if(opArray[i].equals(node))
				opArray[i] = null;
		}
	}
	
	
	
	/**
	 * 遍历链表的方法
	 * @param root:；链表的根节点
	 */
	public void printLinkList(LinkNode<Object> root){
		if(null != root){
			Object data = root.getObj();
			System.out.println(data);
			LinkNode<Object> temp = root.getChild();
			printLinkList(temp);
		}
	}

}

      主函数类：用来测试

 

public class Main {
	static LinkList list = new LinkList();
	public static void main(String[] args){
		System.out.println("Which fuction you want to realize?");
		int choose = 2;
		java.util.Scanner sc1 = new java.util.Scanner(System.in);
		while(choose != 4){
			System.out.println("0、Print the list");
			System.out.println("1、Find someting");
			System.out.println("2、add to List");
			System.out.println("3、delete a element");
			System.out.println("4、exit");
			choose = sc1.nextInt();
			if(choose == 0){
				printList();
			}else if(choose == 1){
				list.getLinkNode(sc1.nextInt());
			}else if(choose == 2){
				Student s1 = new Student();
				System.out.println("Please input the name!");
				s1.setName(sc1.next());
				System.out.println("Please input the score!");
				s1.setScore(sc1.nextInt());
				list.add(s1);
			}else if(choose == 3){
				int a = sc1.nextInt();
				list.deleteLinkNode(a);
				list.deleteHash(a);
			}
	}
	}
	
	
	/**
	 * 打印结果
	 */
	public static void printList() {
		for(int i = 0; i < list.getLength(); i++){
			Student s = (Student) list.getLinkNode(i).getObj();
			s.getName();
			s.getScore();
			System.out.println(s.getName()+"       "+s.getScore());
		}
	}
}

    大家现在有点知道Set是怎样实现无序不重复了吧，就是利用哈希关键字实现。在Java源代码中，我们可以清楚地看到Set借用了Map类，而Map类中正是用Hash函数实现的快速查找和存放。

评论

1 楼 再_见孙悟空 2013-10-10  

同学，我认为else if(choose == 3){  
               int a = sc1.nextInt();  
               list.deleteLinkNode(a);  
               list.deleteHash(a);  
}这个顺序应该调换一下 ，先删除哈希表上的，在删除节点，不然会报空指针