数据结构中的顺序表，可分为物理位置相邻和物理位置不相邻。物理位置相邻且逻辑关系也相邻的我们一般最熟悉的便是数组了，这种结构的特点是可以实现随机存储，但是对于插入删除这些操作来说则极为不便。而链表正是克服了数组的缺点，但同时也有着查找不方便的缺点。链表上的元素虽然在物理上不一定连续，但是在逻辑上一定是连续的。在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函数实现的快速查找和存放。
分享到：
相关推荐
双向链表是一种特殊类型的数据结构，与常见的单向链表相比，它具有更丰富的操作能力，可以支持前后两个方向的遍历。本篇文章将深入探讨如何创建双向链表以及其在增加和删除操作中的应用。 双向链表的每个节点不仅...
在C++编程中，双向链表是一种特殊类型的链表，其中每个节点不仅包含数据，还包含两个指针，分别指向其前一个节点和后一个节点。这种数据结构提供了向前和向后遍历列表的能力，而不仅仅是单向。下面将详细讨论如何在...
### 双向链表及其操作实现 #### 一、引言 双向链表是一种线性数据结构，每个节点包含一个前驱指针和一个后继指针，这使得我们可以从两个方向遍历列表。双向链表相较于单向链表具有更强的灵活性，但也因此消耗更多的...
双向链表类定义及测试文件 对应于数据机构与算法分析（c++版）第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
在Python中，我们可以自定义链表结构来实现单向链表和双向链表。 单向链表（Single Linked List）的特点是每个节点只包含一个指向下一个节点的引用。在单向链表中，遍历只能从头节点开始，按顺序访问每个节点，无法...
操作系统课程设计中实现线程安全的双向链表是一项重要的实践任务，这涉及到多线程编程、数据结构以及并发控制等核心知识点。在这个项目中，我们主要关注如何在多线程环境下构建一个能够正确操作（如插入、删除）而不...
C语言，实现双向链表以及其基本操作，基本操作：链表初始化、创建、查询、删除、释放，查询和删除均有两种方式，一种是按照值，另一种是按照结点的序号。
在C++编程中，双向链表是一种非常重要的数据结构，它允许我们从两个方向遍历元素，即向前和向后。下面将详细讲解如何在C++中操作双向链表，包括创建、查找、插入和删除节点。 首先，我们需要定义双向链表的节点结构...
在这个项目中，我们讨论的是如何在STM32F103上实现一个双向链表的数据结构。双向链表是一种特殊的数据结构，它允许我们在列表中的节点之间进行前向和后向的移动，这在处理动态数据集合时非常有用。 首先，我们要...
在本文中，我们将深入探讨如何使用C语言和双向链表实现经典的贪吃蛇游戏。双向链表是一种数据结构，它允许我们在列表中的任何位置轻松地插入和删除元素，这使得它成为实现动态游戏世界，如贪吃蛇，的理想选择。 1. ...
双向链表（Doubly Linked List）是一种特殊的链表类型，它允许我们在链表中的节点前后两个方向进行遍历。相较于单向链表，双向链表提供了更多的灵活性，但同时也需要额外的空间来存储指向前一个节点和后一个节点的...
C++实现双向链表（List） C++实现双向链表是C++编程语言中一种常见的数据结构实现。双向链表是一种非连续存储结构，具有双链表结构，支持前向/后向遍历，且支持高效的随机删除/插入。 链表的基本概念 链表是一种...
C++双向链表实现简单通讯录 在本文中，我们将详细介绍C++双向链表实现简单通讯录的实现方法。我们将从头开始，了解C++双向链表的基本概念，然后逐步实现一个简单的通讯录系统。 首先，让我们了解一下C++双向链表...
双向链表是一种特殊的数据结构，它在计算机程序设计中扮演着重要角色，特别是在C++这样的编程语言中。本节将深入探讨双向链表的概念、其结构、操作以及C++中的实现。 双向链表与单链表不同，它允许每个节点不仅有一...
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x，y以及左结点指针left及右结点指针right。 包含的函数成员包括： (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
**C++的双向链表实现** 在C++中，双向链表是一种数据结构，它包含节点，每个节点都有指向其前一个节点和后一个节点的指针。这使得在链表中的导航比单链表更加灵活，因为可以向前或向后移动。双向链表在许多算法和...
在Java编程中，双向链表（Double Linked List）是一种数据结构，它允许我们在列表的任一侧进行插入和删除操作。与单向链表不同，双向链表中的每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点。这...