原来你是这样的数据结构之链表结构

顺序表结构的存储方式非常容易理解,操作也十分方便,但是顺序结构有如下缺点:

1.在插入或删除时,往往需要移动大量数据
2.如果表比较大,有时难以分配比较足够连续的存储空间,往往导致内存分配失败.

为了克服上述顺序表的缺点,可以采用链表结构,链表结构是一种动态存储分配的结构形式,可以根据需要动态申请所需的内存单元.

什么是链表结构

典型的链表结构,链表中每一个结点都应包括两部分

• 数据部分,保存当前结点的实际数据
• 地址部分,保存的是下一个结点的引用

链表结构就是由许多这种结点构成的,在进行链表操作时,首先需要定义一个"头引用"变量,一般以(head)表示,该引用变量指向链表结构的第一个结点,第一个结点的地址部分又之向第二个结点,第二个结点的地址部分又指向第三个结点,一直到最后一个结点,这时最后一个结点的地址部分为空,称为"表尾",一般在表层的地址部分放一个空地址null,链表到此结束,如下图

image

由于采用了引用来指示下一个数据的地址,因此在链表结构中,逻辑上相邻的结点在内存中并不一定相邻,逻辑相邻关系通过地址部分的引用变量来实现.

链表结构带来的最大好处就是结点之间不要求连续存放,因此在保存大量数据时,不需要分配一块连续的存储空间,用户可以用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代码实现,当然只是单链表,还有双链表,单循环链表,双循环链表,这些我们会之后一一添加!
原来你是这样的数据结构之栈结构