文档章节

数据结构之“数组“和“链表”

code-ortaerc
 code-ortaerc
发布于 10/21 00:44
字数 2451
阅读 14
收藏 0

前言

本片文章重点在于讨论数据结构之“数组”和“链表”

数组

链表

优点和缺点

  • 优点:数据存储在“节点”(Node)中,做到真正的动态,不需要处理 固定容量的问题。
  • 缺点:丧失了随机访问的能力。

掌握链表需要牢记下面几大技巧:

技巧一:掌握链表,想轻松写出正确的链表代码,需要理解指针获引用的含义:

对于指针的理解,我总结了下面这句话:

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

在编写代码中我们经常遇到 p->next  = q、p->next = p->next->next两者的含义:

① p->next = q:p结点中的next指针存储了q结点的内存地址(p结点的next指针指向q)

② p->next = p->next->next:p结点的next指针储存了p结点的下下一个结点的内存地址

技巧二:插入节点时要警惕指针丢失和内存泄漏

假设我们希望在结点a和相邻结点b之间插入结点x,假设当前指针p指向结点a,如果我们将代码编程下面的这个样子,就会发生指针丢失和内存泄漏:

p->next = x;  //将 p 的next 指针指向x结点
x->next = p->next;  //将 x 结点的next指针指向 b 结点

初学者经常会在这儿犯错,p->next 指针在完成第一步操作之后,已经不再指向结点 b了,而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next,自己指向自己。因此,整个链表也就断成了两半,从结点 b 往后的所有结点都无法访问到了,所以在我们插入结点时,一定要注意操作顺序,现将x结点的next指针指向b,再把结点a的next指针指向结点x,这样才不会丢失指针,导致内存泄漏,正确的删除操作代码应该是:

x->next = p->next;
p->next = x;

技巧三:利用哨兵简化实现难度

回顾单链表的插入和删除操作,希望在p结点之后插入一个新的结点,需要下面两行代码可以搞定:

newNode->next = p->next;
p->next = newNode;

但是,当我们要向一个空链表中插入第一个结点,刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理,其中 head 表示链表的头结点。所以,从这段代码,我们可以发现,对于单链表的插入操作,第一个结点和其他结点的插入逻辑是不一样的。

if(head == null){
   head = newNode;
}

再来看看删除结点:

p->next = p->next->next;

但是,如果我们要删除链表中的最后一个结点,前面的删除代码就不 work 了。跟插入类似,我们也需要对于这种情况特殊处理。写成代码是这样子的:

if(head->next == null){
   head = null;
}

从前面的一步一步分析,可以看出,针对链表的插入、删除操作,需要对插入第一个结点和删除最后一个结点的情况进行特殊处理,这样的代码实现起来很繁琐,不简洁,并且也容易因为考虑不全而出错,如何解决这个问题呢?此时,技巧三的提到的哨兵就要登场了,哨兵,解决的是国家之间的边界问题。同理,这里说的哨兵也是解决“边界问题”的,不直接参与业务逻辑。还记得如何表示一个空链表吗?head=null 表示链表中没有结点了。其中 head 表示头结点指针,指向链表中的第一个结点。

如果我们引入哨兵结点,在任何时候,不管链表是不是空,head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反,没有哨兵结点的链表就叫作不带头链表。

实际上,这种利用哨兵简化编程难度的技巧,在很多代码实现中都有用到,比如插入排序、归并排序、动态规划等。

技巧四:重点留意边界条件处理

软件开发中,代码在一些边界或者异常情况下,最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码,一定要在编写的过程中以及编写完成之后,检查边界条件是否考虑全面,以及代码在边界条件下是否能正确运行。

我们经常检查链表代码是否正确的边界条件有这样几个:

  • 如果链表为空时,代码是否能正常工作?
  • 如果链表只包含一个结点时,代码是否能正常工作?
  • 如果链表只包含两个结点时,代码是否能正常工作?
  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

实际上,不光光是写链表代码,你在写任何代码时,也千万不要只是实现业务正常情况下的功能就好了,一定要多想想,你的代码在运行的时候,可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对,这样写出来的代码才够健壮!

技巧五:举例画图,辅助思考

对于稍微复杂的链表操作,比如前面我们提到的单链表反转,指针一会儿指这,一会儿指那,一会儿就被绕晕了。总感觉脑容量不够,想不清楚。所以这个时候就要使用大招了,举例法和画图法。

技巧六:多写多练,没有捷径

当我们已经掌握了签前面所说的方发时,但是手写链表代码还是会出现各种各样的错误,也不要着急,我们写这些代码,其实没什么技巧,就是把常见的链表操作都自己多些几遍,出问题就一点一点调试,熟能生巧!所以,我精选了 5 个常见的链表操作。你只要把这几个操作都能写熟练,不熟就多写几遍,我保证你之后再也不会害怕写链表代码。

  1. 单链表反转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数第 n 个结点
  5. 求链表的中间结点

链表的定义

数据存储子“节点”(Node)中:

class Node{
    E e;
    Node next;
}

添加元素

1.在链表头部添插入元素

实现:

private void addFirst(E e){
   //创建一个节点
   Node node = new Node();
   //将node的next指向head
   node.next = head;
   //将head更新为node
   head = node;
   
   size++;
}

2.在索引为2的地方添加元素666

 

实现:

  //在链表的中间index(0-based)位置添加元素
    public void add(int index, E data){
        if (index<0 || index>size)
            throw new IllegalArgumentException("Add failed,Illegal index");
        if (index==0)
            addFirst(data);
        else {
            //先找到要插入节点的前一个节点
            Node prev = head;
            for (int i = 0; i < index - 1; i++){//需要知道index的前一个节点,所有遍历index-1次
               prev = prev.next;             //prev节点向后移动
               Node node = new Node(data);   //先创建一个新节点
               node.next = prev.next;        //先将新节点的next指向prev的next
               prev.next = node;             //将prev的next指向node新节点
//            prev.next = new Node(data,prev.next);
            size++;
        }
    }
}

另外,插入元素很容易将顺序颠倒,比如:

如果先执行 prev.next = node (此时prev的next指针已经指向node新节点),接着执行node.next = =prev.next,这时候又将node.next指向他自己(perv.next)明显逻辑顺序户不合,所有在插入元素的过程,顺序很重要。

3.在链表的末尾添加元素

实现:

public void addLast(E data){
   add(size,data)
}

删除元素

数组和链表的对比

区别一:物理地址存储的连续性
数组的元素在内存中是连续存放的。
链表的元素在内存中不一定是连续存放的,通常是不连续的。
区别二:访问速度
数组的访问速度很快,因为数组可以根据数组可以根据下标进行快速定位。
链表的访问速度较慢,因为链表访问元素需要移动指针。
区别三:添加、删减元素速度
数组的元素增删速度较慢,因为需要移动大量的元素。
链表的元素增删速度较快,因为只需要修改指针即可。

总结

写链表代码考验的是逻辑思维能力,因为,链表代码到处都是指针的操作、边界条件的处理,稍有不慎就容易产生 Bug。链表代码写得好坏,可以看出一个人写代码是否够细心,考虑问题是否全面,思维是否缜密。所以,这也是很多面试官喜欢让人手写链表代码的原因。所以,这一节讲到的东西,你一定要自己写代码实现一下,才有效果。

© 著作权归作者所有

code-ortaerc
粉丝 0
博文 19
码字总数 22232
作品 0
广州
私信 提问
浅入浅出数据结构(1)——什么是数据结构及算法

在很多数据结构相关的书籍,尤其是中文书籍中,常常把数据结构与算法“混合”起来讲,导致很多人初学时对于“数据结构”这个词的意思把握不准,从而降低了学习兴趣和学习信心。然而实际上,数...

你的社交帐号昵
2018/05/15
0
0
应对程序员面试,你必须知道的八大数据结构

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

技术小能手
2018/08/29
0
0
Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。 40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。 几乎...

JAVA高级架构开发
2018/10/07
0
0
线性表

1、线性表的定义 线性表(List):零个或多个数据元素的有限序列 第一个元素无前驱,最后一个元素无后继,其他元素都有且只有一个前驱和后继。然后,线性表强调是有限的, 线性表元素的个数n...

DWade_Coding
2017/11/08
0
0
看图轻松理解数据结构与算法系列(单向链表)

前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等...

超人汪小建
2018/07/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Vue.js学习笔记2 - better-scroll滚动条

better-scroll滚动条 使用作者自制的better-scroll库,实现内容的滚动。 先在package.json加上依赖: "better-scroll": "^0.1.7" 接着再npm install安装依赖。 import BScroll from 'better-......

swanf
今天
7
0
设计模式之适配器模式

定义 将一个类的接口变换成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够在一起工 作。 UML类图 适配器分为两种,类适配器与对象适配器。 类适配器的UML图...

陈年之后是青葱
今天
8
0
教你玩转Linux—磁盘管理

导读 Linux磁盘管理好坏直接关系到整个系统的性能问题,Linux磁盘管理常用三个命令为df、du和fdisk。 df df命令参数功能:检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了...

问题终结者
今天
11
0
KMP

字符串匹配算法 针对被匹配字段生产一个部分匹配表 A B C D A B D 0 0 0 0 1 2 0 部分匹配表 熟悉前缀与后缀的概念 ,“部分匹配表” 的生产就是根据前缀、后缀的最苍的共有元素的长度 前缀:...

鬼才王
昨天
6
0
快速搭建Jenkins集群

关于Jenkins集群 在Jenkins上同时执行多个任务时,单机性能可能达到瓶颈,使用Jenkins集群可以有效的解决此问题,让多台机器同时处理这些任务可以将压力分散,对单机版Jenkins的单点故障的隐...

程序员欣宸
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部