顺序表结构的存储方式非常容易理解,操作也十分方便,但是顺序结构有如下缺点:
1.在插入或删除时,往往需要移动大量数据
2.如果表比较大,有时难以分配比较足够连续的存储空间,往往导致内存分配失败.
为了克服上述顺序表的缺点,可以采用链表结构,链表结构是一种动态存储分配的结构形式,可以根据需要动态申请所需的内存单元.
什么是链表结构
典型的链表结构,链表中每一个结点都应包括两部分
- 数据部分,保存当前结点的实际数据
- 地址部分,保存的是下一个结点的引用
链表结构就是由许多这种结点构成的,在进行链表操作时,首先需要定义一个"头引用"变量,一般以(head)表示,该引用变量指向链表结构的第一个结点,第一个结点的地址部分又之向第二个结点,第二个结点的地址部分又指向第三个结点,一直到最后一个结点,这时最后一个结点的地址部分为空,称为"表尾",一般在表层的地址部分放一个空地址null,链表到此结束,如下图
由于采用了引用来指示下一个数据的地址,因此在链表结构中,逻辑上相邻的结点在内存中并不一定相邻,逻辑相邻关系通过地址部分的引用变量来实现.
链表结构带来的最大好处就是结点之间不要求连续存放,因此在保存大量数据时,不需要分配一块连续的存储空间,用户可以用new函数来动态分配结点的存储空间,当删除某个结点时,给该结点赋值null,释放其占用的内存空间.
当然链表结构也有缺点,就是浪费存储空间,因此,对于每个结点数据,都要额外保存一个引用变量,但是,在某些场合,链表结构所带来的好处还是大于其缺点的.
对于链表结构的访问只能从表头按个查找,即从head的头结点,到第二个结点,然后第三个结点,直到找到合适的结点.
链式存储是最常用的存储方式之一,它不仅可以用来表示线性表,而且还可以用来表示各种非线性的数据结构,链表结构有如下几种
- 单链表:同上面的链式结构一样,每个结点中只包含一个引用.
- 双向链表:若每个结点包含两个引用,一个是头引用,一个是尾引用,一个指向上一个结点,一个指向下一个结点.
- 单循环链表:在单链表中,将终端结点的饮用域null改为指向表头结点或开始结点即可构成单循环链表.
- 多重链的循环链表:如果将表中结点链在多个环上,将构成多重链的循环语法.
接下来,将分析如何在java语言中建立链表,并完成链表结构的基本运算.
准备数据
下面我们链表结构的程序设计,首先需要准备数据,也就是准备在链表操作中需要用到的变量及类等
class DATA2 //结点数据
{
String key;
String name;
int age;
}
class CLType
{
DATA2 nodeData = new DATA2(); //保存当前结点的数据
CLType nextNode;
}
上面的代码定义了结点的数据DATA2,以及链表结构的类CLType,结点的具体数据保存在DATA2中,下一个结点的引用保存在nextNode中
追加结点
追加结点即在链表末尾增加一个结点,表尾结点的部分保存原来是null,此时需要将其设置为新增结点的地址(即原表尾结点指向新增结点),然后将新增结点的地址部分设置为null,即新增结点成为表尾.
由于一般情况下,链表只有一个头引用head,要在末尾增加结点就需要从头引用head 开始按个检查,直到找到最后一个结点.
典型的追加结点步骤如下:
- 追加一个结点
- 1.首先分配内存空间,保存新增的结点
- 2.从头引用开始检查,直到找到最后一个结点,
- 3.将结尾结点的内存地址设为新的结点
- 4.将新的结点的地址部分设置为空地址,null,即新结点成为表尾.
public CLType CLAddEnd(CLType head,DATA2 nodeData){
//1.分配内存,保存新增的结点数据
CLType node,htemp;
if((node=new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}else{
node.nextData = nodeData; //2.保存数据
node.nextNode = null; //3.设置下一个结点的索引为null,因为追加的这个是链尾
if(head ==null){ //4.判断链头是否为空,如果为空,则直接赋值并返回
head = node;
return head;
}
htemp = head;
while(htemp.nextNode !=null){//5.循环判断是否是链尾,如果不是链尾则继续判断
htemp = htemp.nextNode;
}
htemp.nextNode = node; //6.判断完成后这个肯定是链尾了,直接赋值
return head;
}
}
上述代码中,输入参数head为链表头引用,输入参数nodeData为结点保存的数据,程序中,使用new关键字申请保存结点数据的内存空间,如果分配内存成功,node中将保存指向内存区域的引用,然后,将传入的nodeData保存到申请的内存区域,并设置该结点指向下一个结点的引用值为null.
插入头结点
插入头结点也就是在链表首部添加结点的过程,有如下几个步骤:
- 分配内存空间,保存新增的结点.
- 使新增结点指向头引用head所指向的结点
- 使头引用head指向新增结点.
public CLType CLAddFirst(CLType head,DATA2 nodeData){
CLType node;
if((node =new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}else{
node.nextData = nodeData;
node.nextNode = head;
head = node;
return head;
}
}
查找结点
查找结点就是在链表结构中查找需要的元素.
public CLType CLFindNode(CLType head,String findkey){
CLType htemp;
htemp = head;
while(htemp.nextNode!=null){
if(htemp.nextData.key.compareTo(findkey)==0){
return htemp;
}
htemp = htemp.nextNode;
}
return null;
}
插入结点
插入结点就是在链表中间部分的指定位置增加一个结点,插入结点的过程如下:
- 分配内存空间,保存新增的结点
- 找到需要插入的逻辑位置,也就是位于哪两个结点之间
- 修改插入结点位置的引用,将新增结点的引用指向找到插入结点位置的饮用
- 将新增结点的位置引用指向插入结点原来的地址
public CLType CLInsertNode(CLType head,String findkey,DATA2 nodeData){
CLType node,nodetemp;
if((node=new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}
node.nextData = nodeData;
nodetemp = head.CLFindNode(head, findkey);
if(nodetemp!=null){
node.nextNode = nodetemp.nextNode;
nodetemp.nextNode = node;
}else{
System.out.println("插入失败 \n");
}
return head;
}
删除结点
删除结点就是删除链表结构中的结点引用,步骤如下:
- 查找需要删除的结点
- 使前一结点指向当前结点的下一个结点
- 删除结点
public int CLDeleteNode(CLType head,String key){
CLType node,htemp; //保存上一个结点和当前结点
htemp = head; //保存当前结点
node = head;
while(htemp!=null){
if(htemp.nextData.key.compareTo(key)==0){
node.nextNode = htemp.nextNode;
htemp = null;
return 1;
}else{
node = htemp;
htemp = htemp.nextNode;
}
}
return 0;
}
计算链表长度
计算链表长度即统计链表结构中结点的数量,在顺序表中比较方便,在链表结构中需要遍历整个链表结构来计算长度.
public int CLLength(CLType head){
int length = 0;
CLType htemp = head;
while(htemp!=null){
length++;
htemp = htemp.nextNode;
}
return length;
}
完整实现代码如下:
package LinkedList;
/**
* 数据结点类型
* 定义链表结构
* @author feiyu
*
*/
public class CLType {
DATA2 nextData = new DATA2(); //当前结点的数据类型
CLType nextNode; //储存下一个结点的位置
/**
* 追加一个结点
* 1.首先分配内存空间,保存新增的结点
* 2.从头引用开始检查,直到找到最后一个结点,
* 3.将结尾结点的内存地址设为新的结点
* 4.将新的结点的地址部分设置为空地址,null,即新结点成为表尾.
* @param head 头结点
* @param nodeData 结点数据
* @return 返回头结点
*/
public CLType CLAddEnd(CLType head,DATA2 nodeData){
//1.分配内存,保存新增的结点数据
CLType node,htemp;
if((node=new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}else{
node.nextData = nodeData; //2.保存数据
node.nextNode = null; //3.设置下一个结点的索引为null,因为追加的这个是链尾
if(head ==null){ //4.判断链头是否为空,如果为空,则直接赋值并返回
head = node;
return head;
}
htemp = head;
while(htemp.nextNode !=null){//5.循环判断是否是链尾,如果不是链尾则继续判断
htemp = htemp.nextNode;
}
htemp.nextNode = node; //6.判断完成后这个肯定是链尾了,直接赋值
return head;
}
}
/**
* 插入头结点
* 1.分配内存空间,保存新增的结点
* 2.将新增结点指向头引用的head所指向的结点
* 3.使头引用指向新增的结点 ,有点绕,就是交换了一下位置,让head原来的头结点指向新的头结点
* @param head
* @param nodeData
* @return
*/
public CLType CLAddFirst(CLType head,DATA2 nodeData){
CLType node;
if((node =new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}else{
node.nextData = nodeData;
node.nextNode = head;
head = node;
return head;
}
}
/**
* 查找结点
* @param head 头结点
* @param findkey
* @return
*/
public CLType CLFindNode(CLType head,String findkey){
CLType htemp;
htemp = head;
while(htemp.nextNode!=null){
if(htemp.nextData.key.compareTo(findkey)==0){
return htemp;
}
htemp = htemp.nextNode;
}
return null;
}
/**
* 插入结点
* 1.分配内存空间,保存新增的结点
* 2.查找关键字,找到需要插入的结点位置并返回
* 3.把找到的结点位置地址保存到新的结点地址位置
* 4.把找到的结点位置指向新的结点
* @param head
* @param findkey
* @param nodeData
* @return
*/
public CLType CLInsertNode(CLType head,String findkey,DATA2 nodeData){
CLType node,nodetemp;
if((node=new CLType())==null){
System.out.println("申请内存失败! \n");
return null;
}
node.nextData = nodeData;
nodetemp = head.CLFindNode(head, findkey);
if(nodetemp!=null){
node.nextNode = nodetemp.nextNode;
nodetemp.nextNode = node;
}else{
System.out.println("插入失败 \n");
}
return head;
}
/**
* 删除结点
* 1.找到要删除的结点位置
* 2.把前一个结点指向当前结点的后一个结点
* 3.删除结点
* @param head
* @param key
* @return
*/
public int CLDeleteNode(CLType head,String key){
CLType node,htemp; //保存上一个结点和当前结点
htemp = head; //保存当前结点
node = head;
while(htemp!=null){
if(htemp.nextData.key.compareTo(key)==0){
node.nextNode = htemp.nextNode;
htemp = null;
return 1;
}else{
node = htemp;
htemp = htemp.nextNode;
}
}
return 0;
}
/**
* 获取链表的长度
* 1.从遍历到尾,然后进行累加
* @return
*/
public int CLLength(CLType head){
int length = 0;
CLType htemp = head;
while(htemp!=null){
length++;
htemp = htemp.nextNode;
}
return length;
}
/**
* 显示所有结点
* @param head
*/
public void CLAllNode(CLType head){
CLType htemp;
htemp = head;
DATA2 nodeData;
while(htemp!=null){
nodeData = htemp.nextData;
System.out.printf("结点(%s,%s,%d) \n",nodeData.key,nodeData.name,nodeData.age);
htemp = htemp.nextNode;
}
}
}
上面就是链表结构的java代码实现,当然只是单链表,还有双链表,单循环链表,双循环链表,这些我们会之后一一添加!
原来你是这样的数据结构之栈结构
