链表


阅读原文


  • 什么是链表
    • 概念

    • 链表

    • 是一种物理存储单元上非连续/非顺序的存储结构.

    • 节点

      • 概念
      • 所谓链表即是由多个节点组成,像一条铁链,铁链的每一个环就相当于链表的节点.
      • 组成
        • 数据域
        • 一个节点用于储存数据的内存控件
        • 指针域
        • 一个节点用于储存和它连接的下一个节点地址的内存空间
    • 优点

      • 创建节点
      • 不需要指定内存空间的大小,非常具有灵活性
      • 删除节点
      • 删除一个节点不需要像数组那样将其余的数据整体向前移动,只需要修改节点的指针域即可完成删除节点的操作
    • 缺点

      • 访问节点
      • 可以通过循环或者递归访问到链表的任何数据,但是访问效率低于数组(线性数据结构)
      • 储存方面
      • 由于不是线性结构,并且相对于线性的储存结构来说,需要保存每个节点的指针域,这又是一笔内存开销,占用了内存空间,对内存空间的利用效率低

  • 链表的种类

    • 方向

      • 单向链表
      • 是连接方向单一的链表,从头结点开始可以一直指向尾节点,方向不会改变(即从头结点走到尾节点只有一条路径).其中每一个节点的指针域只有一个指向,也就是一个节点有一个指针,可以保存下一个节点
    • 双向链表

      • 每一个节点的指针域中保存有两个指针(引用),可以同时指向该节点的前驱节点和后继节点
  • 形状

  • 单链表

    • 单链表:是一种逻辑上的线性结构,只有一条链,首尾不相接
  • 环形链表

    • 环形链表:首尾相接的链表(类比丢手帕)(约瑟夫问题)

  • 如何创建链表
    • 思路分析

      • 图形化结构
        • 链表
          signal-linked-list

          signal-circular-linked-list

          double-signal-linked-list

          double-signal-circular-linked-list
        • 节点
          • 节点类图
            Node-class
          • 节点属性
            • 数据域 : 节点中储存数据内存控件
            • 指针域 : 节点中储存其他节点(可能是下一个,也可能是上一个)的地址信息的内存空间
    • 类图

      • [Java]单项链表类图//TODO 修改类图(无bug的类图)
        LinkedList_Class_Map
        • 文本思路
          • 单向链表
            * //TODO 书写思路
          • 双向链表
            * //TODO 书写思路
          • 单向环形链表
            * //TODO 书写思路
          • 双向环形链表
            * //TODO 书写思路
    • 代码实现

    • [Java]单向链表

    • [Java]双向链表//TODO 添加超链接

    • [Java]单向环形链表//TODO 添加超链接

    • [Java]双向环形链表//TODO 添加超链接


  • 如何使用链表

    • 节点

      • 属性

        • 数据域 : Object data
        • 指针域 :
        • Node successorNode//前驱节点(双向链表节点特有属性)
        • Node precursorNode//后继节点
      • 方法

        • 构造方法 : (根据传入的Object对象创建一个后继节点指向null的Node对象)
        • 查询节点数据 : private Object getData()
        • 修改节点数据 : private void setData(Object newData)//当Node类的成员属性不是私有的时候不需要这些方法,并且就算有这些方法,它们的修饰符也不能是private
    • 链表

    • 属性

    • 长度 : int length = 0

    • 头结点引用 : Node headNode = null

    • 尾节点引用 : Node tailNode = null ? ?(双向链表特有属性)

    • 方法[单向链表]//TODO完成四种链表的分类

    • 初始化链表(利用构造器) : public LinkedList()

    • 增加尾节点 : public void add()

    • 插入指定节点: public void insert(int index)

    • 删除尾节点 : public void del()

    • 删除指定节点 : public void del(int index)

    • 修改尾节点 : public void update(Object newData)

    • 修改指定节点 : public void update(int index, Object newData)

    • 获取尾节点 : public Node getNode()

    • 获取指定节点 : public Node getNode(int index)

    • 链表长度 : public int length()

    • 判断空链表 : public boolean isEmpty()

    • 排序 : public void sort()

    • 截取链表 : public LinkedList subLinkedList(int start, int end)


  • 如何进行测试

    • 当我们构建好了我们自己的链表的时候,就必须得对其正确性和健壮性进行测试,这个测试的过程一般来说是随着编码一起进行的,我们来看一下应该如何进行测试.

      • 正确性//TODO
      • 健壮性//TODO

  • 如何优化链表

    • 算法方面
      • 排序算法
      • 冒泡排序
      • 选择排序
      • 插入排序
      • 检索算法
    • 操作方法
    • 健壮性
    • 待续

  • 链表的应用场景

    • 首先我们知道链表的特点就是可以动态地增加和删除元素,就类似与一个可以自动扩大和缩小容量的数组,因此,我们可以想到它的应用场景应该有:

      • 1.求解约瑟夫问题(利用环形链表)

代码实现

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,311评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,339评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,671评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,252评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,253评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,031评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,340评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,973评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,466评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,937评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,039评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,701评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,254评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,259评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,497评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,786评论 2 345

推荐阅读更多精彩内容

  • 作为一个资深的新手程序员😂,链表这些既基础又深奥的东西是日常工作中并不常见,但是却非常重要,所以就总结一下链表的简...
    Clark_new阅读 4,238评论 4 12
  • 本文内容:1、 什么是链表?2、 链表共分几类?3、 链表的 C 实现! 总表:《数据结构?》 工程代码 Gith...
    半纸渊阅读 39,923评论 0 54
  • 链表 概念 说到链表,coder们都不会陌生,在日常开发中或多或少都会用到它。它是链式存储的线性表,简称链表。链表...
    扈扈哈嘿阅读 2,076评论 0 5
  • 【声明】欢迎转载,但请保留文章原始出处→_→文章来源:http://www.jianshu.com/p/08d08...
    梦工厂阅读 3,758评论 3 31
  • //leetcode中还有花样链表题,这里几个例子,冰山一角 求单链表中结点的个数----时间复杂度O(n)这是最...
    暗黑破坏球嘿哈阅读 1,510评论 0 6