数据结构算法 - 数组与链表

是时候来撸一波数据结构和算法了,学完 NDK 自己打算又重新回到 Android 和 Java , 再去抓一些有细节和深度的东西。大学选的是教育专业后来自学的编程,学编程的第一感觉就是可以找一份工作,薪资方面什么的都还好,因为农村孩子家里穷所以就学了。刚开始学习不像现在,谈不上有多喜欢,也没学过什么数据结构和算法,感觉开发中能用到的地方也不多,面试基本也不问(长沙)。前几天在微信公众号看到一篇文章 《 P2P被套了,失业了,魔都我又开始面试了,说好的不跳的》 现在企业的用人标准,似乎都比以前高了很多。来深圳面试上了 500 人以上的企业,基本都会问一些数据结构和算法的知识,好在自己在还没来深圳之前,就做了一些准备。

学了数据结构和算法后,自己的第一感觉就是思维更加敏捷和开阔了,写代码的时候严谨了很多,线上崩溃 Bug 也少了许多。如果说语言的基础语法和业务逻辑是术,那 数据结构与算法思想和设计模式就是道。后期如果想要有一个飞跃式的提高,数据结构与算法、设计模式这个时候就很重要,是一门内功心法。

首先我们需要了解几个概念,什么是数据结构?什么是算法?算法的优劣怎样来衡量?

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系,简单的理解就是元素之间的相互关系。其中逻辑结构分为四类:集合结构,线性结构,树形结构,图形结构。存储结构一般分为顺序存储和连式存储。

算法是指特定问题求解步骤的描述。算法的特性有:输入,输出,有穷性,确定性和可行性。算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量,也称之为时间复杂度空间复杂度

时间复杂度是一个函数,它定性描述了该算法的运行时间,时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。

概念性的东西理解起来比较困难,我们来看一个简单的实例,相信就能理解什么是时间复杂度和空间复杂度了。假如我们现在需要求 1+2+3+4+5+ **** + n ,我们可能会有如下写法:

// 通过具体的 n 的步骤就可以推演出算法的复杂度
int sum1(int n){ // 时间复杂度 O(n)
    int sum = 0; // 执行 1 步
    for (int i = 1; i <= n; i++) // 执行 n 步
    {
        sum += i;
    }
    return sum;
}

int sum2(int n){// 时间复杂度 O(1)
    return (1 + n) * n / 2;// 1步
}

上面的实例,通过具体的 n 的步骤就可以推演出算法的复杂度,因此 sum1 的时间复杂度我们可以表示为 O(n) , sum2 的时间复杂度为 O(1) 。

常见的时间复杂度有: 常数阶O(1),对数阶O(log2 n),线性阶O(n),线性对数阶O(n log2 n),平方阶O(n^2), 立方阶O(n^3), k次方阶O(n^K),指数阶O (2^n)。 随着n的不断增大,时间复杂度不断增大,算法花费时间越多。

理论过后就是去实践了,为了方便巩固我们 NDK 所学的内容,后面的文章分析源码主要以 Java 为主,语法主要以 c/c++ 为主。至于数组之前的文章 《C++基础 - 实现 Native 层的 ArrayList》 有讲过,这里就不再过多的啰嗦。那么本文就主要来分析链表,以 Java 的 LinkedList 源码为例。

template<typename E>
typedef
struct Node {
    E value;
    Node *next;
public:
    Node(E value, Node *next) {
        this->value = value;
        this->next = next;
    }
};

template<typename E>
E LinkedList<E>::get(int index) {
    assert(index >= 0 && index < len);
    return node(index)->value;
}

template<typename E>
int LinkedList<E>::size() {
    return len;
}

template<typename E>
void LinkedList<E>::push(E e) {
    // 创建新的节点
    Node<E> *newNode = new Node<E>(e, NULL);
    if (head) {
        // 获取最后一个节点
        Node<E> *last = node(len - 1);
        last->next = newNode;
    } else {
        head = newNode;
    }
    len++;
}

template<typename E>
Node<E> *LinkedList<E>::node(int index) {
    Node<E> *cur = head;

    for (int i = 0; i < index; ++i) {
        cur = cur->next;
    }

    return cur;
}

template<typename E>
void LinkedList<E>::insert(int index, E e) {
    assert(index >= 0 && index <= len);

    Node<E> *newNode = new Node<E>(e, NULL);

    if (index == 0) {
        newNode ->next = head;
        head = newNode;
    } else {
        // 获取当前位置的前一个节点
        Node<E> *pre = node(index - 1);
        // 保存当前位置
        Node<E> *next = pre->next;
        pre->next = newNode;
        newNode->next = next;
    }
    len++;
}

template<typename E>
E LinkedList<E>::remove(int index) {
    assert(index >= 0 && index < len);
    len--;
    if(index == 0){
        Node<E> *h = head;
        head = head->next;

        E value = h->value;
        delete h;
        return value;
    } else {
        Node<E> *pre = node(index - 1);
        Node<E> *next = pre->next;
        pre->next = pre->next->next;

        E value = next->value;
        // new 的对象,需要删除当前节点
        delete next;
        return value;
    }
}

上面的代码比较简单,主要采用单链表来实现一个集合。一个算法我们可以优先考虑时间复杂度,所以在大多数场景下,可以考虑用空间复杂度来换时间复杂度,比如我们现在插入一条数据的时间复杂度是 O(n) 级别,那么我们就需要想办法去优化。比如我们加一个 last 节点,就可以把插入数据的复杂度降为 O(1) 级别。不要小看了这些优化,当数据量大的时候就会非常有用。

对插入 50000 条数据进行测试,耗时是 8000ms ,上面插入算法时间复杂度是 O(n) 级别的,关键就在于每次插入数据的时候,都需要遍历整个链表找到最后一个节点才能插入。因此我们可以针对性的做一些优化,我们再定义一个节点用来记录链表的最后一个位置,将时间复杂度优化为 O(1) 级别。

template<typename E>
void LinkedList<E>::linkLast(E e) {
    Node<E> *l = last;
    Node<E> *new_node = new Node<E>(e, NULL);
    last = new_node;

    if (l == NULL) {
        head = new_node;
    } else {
        l->next = new_node;
    }
}

对插入 50000 条数据进行测试,耗时是 0ms 。链表和数组相比劣势就在于查找,因为数组可以根据索引查找,因此时间复杂度是 O(1) 级别,而链表的时间复杂度是 O(n),当然我们也可以对其进行优化,比如采用双向链表或是单链表位运算等等。

template<typename E>
void LinkedList<E>::linkBefore(E e, Node<E> *cur) {
    Node<E> *prev = cur->prev;
    Node<E> *new_node = new Node<E>(e, prev, cur);
    cur->prev = new_node;

    if(prev){
        prev->next = new_node;
    } else{
        head = new_node;
    }
}

视频地址:https://pan.baidu.com/s/1s0Xb_PM3Ehp81slUY7qnGg
视频密码:kcek

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

推荐阅读更多精彩内容

  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,807评论 0 13
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,105评论 0 12
  • 原文地址:http://theory.stanford.edu/~amitp/GameProgramming/ 1...
    达微阅读 19,457评论 0 28
  • 真正的朋友 不会因为离开的时间长短 而让友谊变质 相反它会像一杯美酒 时间越久,它越有韵味 真正的朋友 不是锦上添...
    呼啸的烈风阅读 230评论 4 3
  • 使用nova管理docker的container,为了省事,没想到踩到了不少坑。 第一坑 nova-docker的...
    zengjie_dev阅读 1,861评论 0 1