数据结构中的顺序表，可分为物理位置相邻和物理位置不相邻。物理位置相邻且逻辑关系也相邻的我们一般最熟悉的便是数组了，这种结构的特点是可以实现随机存储，但是对于插入删除这些操作来说则极为不便。而链表正是克服了数组的缺点，但同时也有着查找不方便的缺点。链表上的元素虽然在物理上不一定连续，但是在逻辑上一定是连续的。在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函数实现的快速查找和存放。
分享到：
相关推荐
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表，使得该链表中的数据元素递增有序排列。（必须使用双向链表完成...
双向链表
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x，y以及左结点指针left及右结点指针right。 包含的函数成员包括： (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
详细的介绍了Linux内核中使用的最频繁的双向链表
双向链表类定义及测试文件 对应于数据机构与算法分析（c++版）第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
一种支持类模版和函数模版的C++双向链表，实现了各种排序算法（排序原则可定制），包含学生信息的使用示例(VC 6.0、VS2008).
实现双向链表的增删改查功能，dos窗口输入输出，可运行，有注释
C 语言版 双向链表 #include #include typedef struct list { int date; struct list *llink; struct list *rlink; }st; st *creat () //创建双向链表 { st *head , *p , *q; head = q = p = NULL; int ...
通过建立双向链表，来实现双向查找，增加和删除的功能
双向链表是一种比较常用的数据结构，在许多场合都有应用。但是，双向链表的节点操作，对于初学者来说或许显得比较繁琐。尤其是，当用链表描述不同的数据结构时，节点结构体的定义都是不同的，这就需要为每一种链表都...
操作系统c++编程实现安全型双向链表，线程的创建，利用线程对链表进行增删改操作，并检验结果是否正确
原创手操，操作系统课设，线程安全的双向链表，VC6.0，无须配置，可运行
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
用模板类实现了一个简单的双向链表domo。
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘
循环双向链表，实现了插入、查找特定的节点、删除等功能，是自己花了半天的时间写完的。
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
基础数据结构双向链表的C++描述版。实现了双向链表的基本功能。包括拷贝构造函数和IO操作符重载、赋值操作符重载
ALIST是一段基于C语言的数组型双向链表的处理代码，接口简单明了，易于使用，标准C语言开发，可添加在任何C/C++语言工程中，需要注意的是，如果使用了操作系统，请自行在库中修改指向处添加资源锁定，避免因操作系统...