数据结构和算法分享专题基础编程数据结构和算法分析

链表

2016-06-28  本文已影响718人  王一航

阅读原文

代码实现

[Java]单向链表代码 :

package linkedList;
/** 
   * 节点类(单向链表) 
   * @author 王一航 
   */
class Node {
    //数据域   Object data;
    //指针域   Node nextNode = null;//单向链表因此只有一个指向自身类型的引用
        //构造函数
    public Node(Object data){
        this.data = data;
    }
}

package linkedList;
/** * 单向链表类 * @author 王一航 */
public class LinkedList {
    /**  * 成员变量  */ int length = 0;
    Node headNode = null;
    /**  * 成员方法  */
    //初始化链表(利用构造器)
    public LinkedList(){
        int length = 0;//记录链表长度
        Node headNode = null;//头结点
    }
    //增加尾节点
    public void add(Object data){
        insert(length, data);
    }
    //插入指定节点
    public void insert(int index, Object data){
        Node temp = getNode(index);//使用一个临时的引用记录需要插入的位置的前驱结点的地址
        Node node = new Node(data);//创建新节点准备插入
        if(index > 0){
            getNode(index - 1).nextNode = node;     
            }else{
            headNode = node;
        }
        node.nextNode = temp;
        length++;
    }
    //删除尾节点
    public void del(){
        del(length - 1);
    }
    //删除指定节点
    public void del(int index){
        //TODO 检查入口参数
        if(index > 0){
            getNode(index - 1).nextNode = getNode(index + 1);
            length--;
        }
        if(index == 0){
            headNode = getNode(1);
            length--;
        } //TODO 释放内存
    }
    //修改尾节点
    public void update(Object newData){
        update(length - 1, newData);
    }
    //修改指定节点
    public void update(int index, Object newData){  
            getNode(index).data = newData;
    }   
        //获取尾节点
    public Node getNode(){
        return getNode(length - 1);
    }
    //获取指定节点
    public Node getNode(int index){
        try{
            point = headNode;
            int count = 0;
            while(count < index){
                point = point.nextNode;
                count++;
            }
            return point;
        }catch(NullPointerException e){
            System.out.println("请检查链表是否越界! 链表长度 : " + length);
            return null;
        }
    }
    //链表长度
    public int length(){
        return length;
    }
    //判断空链表
    public boolean isEmpty(){
        return length == 0 ? true : false;
    }
    //排序
    public void sort(){
        //TODO 完成排序功能
        System.out.println("请完成排序功能!");
    }
    //截取链表
    public LinkedList subLinkedList(int start, int end){
        if(end >= start){
            headNode = getNode(start);
            getNode(end - start).nextNode = null;
            length = end - start;
        }
        return this;
        //TODO 释放不需要的内存
    }
    //打印链表所有元素
    public void show(){
        for(int i = 0; i < length; i++){
            System.out.println("索引 : " + i + " 第" + (i+1) + "个" + getNode(i).data);
        }
    }
}

[Java]双向链表代码 :

package doubleLinkedList;
/** * 双向链表节点类 * @author 王一航 */
class Node {
    //数据域   Object data;
    //指针域   Node lastNode = null;//前驱节点引用
    Node nextNode = null;//后继节点引用
    //构造函数  public Node(Object data){
        this.data = data;
    }
}
//TODO 添加双向链表的代码

[Java]单向环形链表代码 :

//TODO 添加代码
package circularLinkedList;
/** * 单向环形链表节点类 * @author 王一航 */
public class Node {
    /**  * 成员属性  */
    //数据域   Object data;
    //指针域   Node successorNode;//后继节点
    /**  * 成员方法  */
    public Node(Object data){
        this.data = data;
    }
}

[Java]双向环形链表代码 :

//TODO 添加代码
package circularLinkedList;
/** * 双向环形链表节点类 * @author 王一航 */
public class Node {
    /**  * 成员属性  */
    //数据域   Object data;
    //指针域   Node successorNode;//后继节点
    Node precursorNode;//前驱节点
    /**  * 成员方法  */
    public Node(Object data){
        this.data = data;
    }
}

总结(个人理解):

注意 :

1 . 杜绝魔术数字的出现,程序中一旦需要使用到某些常量,则必须首先声明常量为一个有意义的名字,然后根据这个名字去访问该常量

上一篇 下一篇

猜你喜欢

热点阅读