完整的代码地址为：github 点击查看
单链表
单链表包括数据域和指向下一个节点的指针域，其结构如上图所示
首先定义一个数据类：
class DATA{ //定义链表的一个节点
String key; //节点的关键字
String name;
int age;
}
定义一个单向链表类（包括以下几种方法）：
1：在尾部添加节点
2：在头部添加节点
3：查找节点
4：插入节点
5：删除节点
6：计算链表长度
7：显示所有节点对应的代码如下
public class Link { //定义链表结构
DATA nodeData = new DATA(); //声明一个节点
Link nextNode; //指向下一个节点的指针
//添加节点
Link linkAddEnd(Link head, DATA nodeData)
{
Link node, hTemp;
if( (node = new Link()) ==null) //如果内存空间分配失败，则返回为空
{
System.out.println("内存空间分配失败！");
return null;
}
else
{
node.nodeData = nodeData;
node.nextNode = null;
if(head == null) //如果头节点为空，则把当前节点赋给head，并返回
{
head = node;
return head;
}
hTemp = head; //如果头节点不为空
while(hTemp.nextNode!=null) //查找链表的末尾
{
hTemp = hTemp.nextNode;
}
hTemp.nextNode = node;
return head;
}
}
//插入头节点
Link linkAddFirst(Link head, DATA nodeData)
{
Link node;
if((node=new Link()) == null ) //如果内存空间分配失败，则返回为空
{
System.out.println("内存分配失败");
return null;
}
else
{
node.nodeData = nodeData;
node.nextNode = head;
head = node;
return head;
}
}
//查找节点
Link linkFindNode(Link head, String key)
{
Link hTemp;
hTemp = head;
while(hTemp!=null) //若节点有效，则进行查找
{
if(hTemp.nodeData.key.compareTo(key) == 0) //若节点的关键字与传入的关键字相同
{
return hTemp;
}
hTemp = hTemp.nextNode; //处理下一个节点
}
return null;
}
//插入节点
Link linkInsertNode(Link head, String findKey,DATA nodeData)
{
Link node,hTemp;
if((node = new Link() ) == null ) //分配内存失败，则返回
{
System.out.println("分配内存失败...");
return null;
}
node.nodeData = nodeData; //保存当前集节点信息
hTemp = linkFindNode(head, findKey); //查找要插入的节点
if(hTemp != null)
{
node.nextNode = hTemp.nextNode;
hTemp.nextNode = node;
}
else
{
System.out.println("未找到正确的插入位置.........");
}
return head; //返回头引用
}
//删除节点
int linkDeleteNode(Link head, String key)
{
Link node,hTemp;
hTemp = head;
node = head;
while(hTemp != null )
{
if(hTemp.nodeData.key.compareTo(key) == 0) //若找到关键字，则删除
{
node.nextNode = hTemp.nextNode;
hTemp = null;
return 1;
}
else //跳到下一个节点
{
node = hTemp;
hTemp = hTemp.nextNode;
}
}
return 0;
}
//计算链表长度
int linkLength(Link head)
{
Link hTemp;
hTemp = head;
int num = 0;
while(hTemp!=null)
{
num ++ ;
hTemp = hTemp.nextNode;
}
return num;
}
//显示所有节点
void linkShow(Link head)
{
Link hTemp;
DATA nodeData;
hTemp = head;
System.out.printf("当前链表共有 %d 个节点，链表所有的数据如下：\n" , linkLength(head));
while(hTemp!=null)
{
nodeData = hTemp.nodeData; //获取当前的节点数据
System.out.printf("节点(%s %s %d)\n",nodeData.key,nodeData.name,nodeData.age);
hTemp = hTemp.nextNode;
}
}
}
编写测试类：
public class linkTest {
public static void main(String[] args) {
Link node = null , head=null;
Link link = new Link();
String key, findKey;
Scanner input = new Scanner(System.in);
System.out.printf("链表测试开始，先输出链表中的数据，格式为：关键字 姓名 年龄\n");
do
{ //循环插入节点，知道输入的key 为0 结束
DATA nodeData = new DATA();
nodeData.key = input.next();
if(nodeData.key.equals("0"))
{
break;
}
else
{
nodeData.name = input.next();
nodeData.age = input.nextInt();
head = link.linkAddEnd(head, nodeData); //在链表尾部添加节点
}
}while(true);
link.linkShow(head); //显示所有节点
System.out.printf("\n演示插入节点，输入插入位置的关键字：");
findKey = input.next(); //输入插入的关键字
System.out.println("输入插入节点的数据(关键字 姓名 年龄)");
DATA nodeData = new DATA(); //输入节点的元素值
nodeData.key = input.next();
nodeData.name = input.next();
nodeData.age = input.nextInt();
head = link.linkInsertNode(head, findKey, nodeData); //调用插入函数
link.linkShow(head); //显示所有节点
System.out.println("演示删除节点，输入要删除的关键字：");
key = input.next();
link.linkDeleteNode(head, key); //调用删除节点的函数
link.linkShow(head); //显示所有节点
System.out.println("演示在链表中差找，输入要查找的关键字：");
key = input.next();
node = link.linkFindNode(head, key); //调用查找函数,返回节点引用
if(node!=null)
{
nodeData = node.nodeData; //获取节点的数据
System.out.printf("关键字 %s 对应的节点数据为 （%s %s %s）\n", key,nodeData.key,nodeData.name,nodeData.age);
}
else
{
System.out.printf("在链表中为查找的为%s 的关键字 \n" , key);
}
}
}
双向链表
链结点的结构：
┌────┬────┬────────┐
│data│next│previous│
└────┴────┴────────┘
结构图如下：
package Link;
import java.util.Scanner;
class Data{ //定义链表的一个节点
String key; //节点的关键字,唯一
String name;
int age;
}
public class DoubleLink {
int flag; //输入选择值
Scanner scan = new Scanner(System.in);
Data data = new Data();
DoubleLink nextNode; //后继节点
DoubleLink priorNode; //前驱节点
//链表添加节点
DoubleLink addNode(DoubleLink head, String priorKey, String nextKey, Data nodeData){
DoubleLink node=null, htemp=null;
if((node = new DoubleLink()) == null)
System.out.println("内存空间分配失败");
if(head== null) //如果head为空
{
System.out.println("当前链表为空，是否将当前节点当作头节点？\n0：否\t1：是");
node.data=nodeData;
node.nextNode=null;
node.priorNode=null;
flag = scan.nextInt();
switch(flag)
{
case 0:
break;
case 1:
head=node;
break;
default:
System.out.println("你输入的数据不合法");;
}
} //如果head不为空
else{
if(linkFindNode(head, priorKey,nextKey,nodeData))
System.out.println("插入成功");
else
System.out.println("插入失败(原因可能是你输入的前驱和后继即诶但均不存在)");
}
return head;
}
//查找并插入节点
boolean linkFindNode(DoubleLink head, String priorKey, String nextKey,Data nodeData) {
// TODO Auto-generated method stub
DoubleLink htemp=null,node=null;
if( (node = new DoubleLink()) == null )
{
System.out.println("内存分配失败");
return false;
}
//将传进来的值赋值给node
node.data = nodeData;
node.nextNode = null;
node.priorNode=null;
//两大类情况
htemp = head;
while(htemp != null)
{
if(htemp.data.key.equals(priorKey)) //前驱节点存在
{
if(htemp.nextNode == null) //该节点的后继节点为空，说明该节点为头节点
{
System.out.println("你输入的后继节点不存在，前驱节点为头节点，是否插入在其后面？\n 1：是 \t 0 ：否 ");
flag = scan.nextInt();
if(flag == 0)
break;
else if(flag==1)
{
htemp.nextNode = node; //将查找到的节点的后继节点指向node
node.nextNode = null;
node.priorNode = htemp;
return true;
}
else
System.out.println("你输入的数字不合法！！！");
}
else //后继节点不为空
{
if(htemp.nextNode.data.key.equals(nextKey)) //存在的后继节点与nextKey相同。相同执行if
{
node.nextNode = htemp.nextNode;
htemp.nextNode.priorNode = node;
htemp.nextNode = node;
node.priorNode = htemp;
return true;
}
else //不同执行else
{
htemp = htemp.nextNode; //若当前节点没找到，遍历下一个节点
}
}
}
else //前驱节点不存在，后驱节点存在
{
if(htemp.data.key.equals(nextKey)) //如果当前节点与nextKey相同
{
if(htemp.nextNode==null) //如果后继节点为空，即当前节点为尾节点
{
System.out.println("你输入的前驱节点不存在，后继节点为头节点，是否插入在其前面？\n 1：是 \t 0 ：否 ");
flag = scan.nextInt();
if(flag == 0)
break;
else if(flag==1)
{
htemp.priorNode = node;
node.nextNode = htemp;
node.priorNode=null;
return true;
}
else
System.out.println("你输入的数字不合法！！！");
}
else //如果当前节点的后继节点不为空，则执行下一个节点
{
htemp = htemp.nextNode; //若当前节点没找到，遍历下一个节点
}
}
else
htemp = htemp.nextNode; //若当前节点没找到，遍历下一个节点
}
}
return false;
}
//输出节点
public void OutputLinkNode(DoubleLink head)
{
if(head == null)
System.out.println("当前链表为空");
else{
System.out.println("输入的链表数据如下：");
DoubleLink htemp;
htemp = head;
while(htemp!=null)
{
System.out.println(htemp.data.key + "\t" + htemp.data.name + "\t" + htemp.data.age);
htemp= htemp.nextNode;
}
}
System.out.println();
}
//输出链表的深度
int LinkDepth(DoubleLink head)
{
int sum = 0;
DoubleLink htemp = head;
while(htemp!=null)
{
sum ++;
htemp = htemp.nextNode;
}
return sum;
}
//查找节点
DoubleLink FindLink(DoubleLink head, String findKey)
{
DoubleLink htemp=head;
while(htemp!=null)
{
if(htemp.data.key.equals(findKey))
return htemp;
htemp = htemp.nextNode;
}
return null;
}
//删除节点
DoubleLink DeleteNode(DoubleLink head, String deleteKey)
{
DoubleLink htemp = head;
while(htemp!=null)
{
if(htemp.data.key.equals(deleteKey))
{
if(htemp.priorNode==null) //如果是头节点
{
return htemp.nextNode;
}
else if (htemp.nextNode==null) //如果是尾节点
{
htemp.priorNode.nextNode=null;
htemp.priorNode=null;
return head;
}
else //如果是中间
{
htemp.priorNode.nextNode=htemp.nextNode;
htemp.nextNode.priorNode = htemp.priorNode;
return head;
}
}
else
htemp = htemp.nextNode;
}
System.out.println("你要删除的节点不存在！");
return head;
}
}
测试实现：
package Link;
import java.util.Scanner;
public class DoubleLinkTest {
public static void main(String[] args) {
DoubleLink node=null, head=null;
DoubleLink dlink = new DoubleLink(); //声明一个双向链表对象
Scanner scan = new Scanner(System.in);
System.out.println("双向链表测试开始....");
do{
System.out.println("请输入插入节点的关键字，姓名和年龄，格式为：关键字 姓名 年龄");
Data data = new Data();
data.key = scan.next();
data.name = scan.next();
data.age = scan.nextInt();
if(data.key.contains("0")) //循环插入节点，直到插入的为0时结束
break;
else
{
System.out.println("请输入插入节点的前驱节点和后继节点，格式为 前驱节点 后继节点");
String priorKey = scan.next();
String nextKey = scan.next();
head = dlink.addNode(head, priorKey, nextKey, data); //添加节点
dlink.OutputLinkNode(head); //输出链表
}
}while(true);
//输出链表的深度
System.out.println("该链表的深度为：" + dlink.LinkDepth(head));
//查找链表中的某个节点
System.out.println("请输入要查找的节点的关键字...");
String findKey = scan.next();
node = dlink.FindLink(head, findKey);
if(node==null)
System.out.println("你所查找的节点不存在！");
else
System.out.println("该节点的值为：" + node.data.key + "\t" + node.data.name + "\t" + node.data.age);
//删除节点值
System.out.println("请输入要删除的节点的关键字...");
String deleteKey = scan.next();
node = dlink.DeleteNode(head, deleteKey);
if(node == null)
System.out.println("删除节点后的链表为空，其深度为：" + 0);
else
{
System.out.println("删除后的链表为：");
dlink.OutputLinkNode(head);
System.out.println("删除节点后链表的深度为：" + dlink.LinkDepth(head));
}
}
}
结果展示
