阅读 1518

iOS中用到的数据结构_链表

关键词:链表、AutoreleasePool、NSNotification、链表热门问题及解法

推荐大家leetcode的探索里的链表--看的再多不如自己练习下

一.为什么是链表

  一切的起源还是在那场面试中,我们一切都聊的很好,直到他问我什么是双向链表。当时网络工程专业毕业的我竟组织不起语言回答他这个问题....


其实在iOS当中有很多的对象的底层的数据存储用到了链表,学习链表可以帮助我们高效理解部分底层d的实现原理,同时我们亦可以将其巧妙的运用在今后的开发中,提升效率。

同时链表也是我学习数据结构的开始,iOS中有很多点都用到了数据结构,比如weak、objc_class的Cache等之后也会开文章梳理这部分内容,主要有哈希表、栈、队列等。

二.甚是链表(单、双链表)

链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表

每个结点不仅包含值,还包含链接到下一个结点的​引用字段​。通过这种方式,单链表将所有结点按顺序组织起来。

struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};

双链表

以类似的方式工作,但​还有一个引用字段​,称为​“prev”​字段。有了这个额外的字段,您就能够知道当前结点的前一个结点。

struct DoublyListNode {
int val;
DoublyListNode *next, *prev;
DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

三.iOS中的链表

AutoreleasePool

AutoreleasePool中用到链表的地方:
AutoreleasePool中的 AutoreleasePoolPage 是以双向链表的形式连接起来的。
具体实现可以参考自动释放池的前世今生

class AutoreleasePoolPage {    
   magic_t const magic;//magic 用于对当前 AutoreleasePoolPage
   完整性的校验    id *next;//指向了下一个为空的内存地址   
   pthread_t const thread;//thread 保存了当前页所在的线程  
   AutoreleasePoolPage * const parent;//parent 和 child 就是用来构造双向链表的指针 
   AutoreleasePoolPage *child;  
   uint32_t const depth; 
   uint32_t hiwat;
};复制代码
objc_autoreleasePoolPush方法被调用时会牵扯到POOL_SENTINEL、hotPage等,
1.有hotPage且未满时, page->add
2.当hotPage已满时它会从传入的 page 开始遍历整个双向链表,直到:
  1. 查找到一个未满的 AutoreleasePoolPage
  1. 使用构造器传入 parent 创建一个新的 AutoreleasePoolPage
在查找到一个可以使用的 AutoreleasePoolPage 之后,会将该页面标记成 hotPage,然后调动上面分析过的 page->add 方法添加对象。
3.如果当前内存中不存在 hotPage,就会调用 autoreleaseNoPage 方法初始化一个AutoreleasePoolPage。

NSNotification

NSNotificationCenter是中心管理类,实现较复杂。总的来讲在NSNotificationCenter中定义了两个Table,同时为了封装观察者信息,也定义了一个Observation保存观察者信息。这里主要是来保存观察者信,并且发送通知时逐个遍历调用其中方法。
Observation的结构如图

typedef struct  Obs {
  id        observer;   /* 保存接受消息的对象*/  
  SEL       selector;   /* 保存注册通知时传入的SEL*/  
  struct Obs    *next;      /* 保存注册了同一个通知的下一个观察者*/ 
  struct NCTbl  *link;  /* 保存改Observation的Table*/
} Observation;复制代码
下图为NSNotificationCenter维护的Named Table的结构,其中为保存多个观察者的情况,在箭头处内Table的以传入的Object为Key,用链表来保存所有的观察者,并且以这个链表为Value。


addObserver: selector: name: object:时,如果在保存Observation的Table中根据object作为key没有找到对应的链表,则会创建一个节点,作为头结点插入进去;如果找到了则直接在链表末尾插入之前实例化好的Observation。
postNotificationName:(NSNotificationName)aName object:(nullable id)anObject的流程总体来讲就是根据NotifcationName查找到对应的Observer链表,然后遍历整个链表,给每个Observer结点中保持存的对象及SEL,来像对象发送信息(也即是调用对象的SEL方法)

四.链表的优势(主要是与数组做对比)

优点是插入和删除比较方便(不需移动其他元素, 只需改变指针)
  • 不同:
  1. 链表是链式的存储结构;数组是顺序的存储结构。
  2. 链表通过指针来连接元素与元素,数组则是把所有元素按次序依次存储。
  3. 链表的插入删除元素相对数组较为简单,不需要移动元素,且较为容易实现长度扩充,但是寻找某个元素较为困难;
  4. 数组寻找某个元素较为简单,但插入与删除比较复杂,由于最大长度需要再编程一开始时指定,故当达到最大长度时,扩充长度不如链表方便。
  • 相同:
  1. 两种结构均可实现数据的顺序存储,构造出来的模型呈线性结构。

五.链表练习(此处没有代码,只有相应的解法思路以及leetcode解题链接,大家也可以去leetcode看看每个解法的讨论,加油)

链表删除倒数第n个节点(双指针法)

主要还是先出一个指针让其先走n步,然后从head遍历,当先前指针的next为nil时,此时的指针便是要删除的指针。具体解法 :

leetcode-cn.com/problems/re…

环形链表的判断 (快慢指针、哈希法)

  使用一个指针遍历链表,每次访问一个节点首先都判断Hashset中是否存在同一个节点,如果存在则链表存在环,否则持续加入到Hashset中。当指针遍历到NULL的时候仍然没有找到环,证明链表不存在环。

leetcode-cn.com/problems/li… 哈希

  双指针在链表的操作中比较常见,应该作为一种常用的思路记住。,我们设置两个指针从head开始遍历,规定两个指针的前进速度不一样,分别称为快、慢指针,slow指针每次前进一个,fast指针每次前进两个节点。

leetcode-cn.com/problems/li…  快慢指针

反转一个单链表

反转单向链表是个比较简单的操作 

leetcode-cn.com/problems/re…

旋转双向链表

    思想:

    链表中的点已经相连,一次旋转操作意味着:

     1)先将链表闭合成环 

     2)找到相应的位置断开这个环,确定新的链表头和链表尾 

     步骤:

     1)找到旧的尾部并将其与链表头相连 old_tail.next = head,整个链表闭合成环,同时计算出链表的长度 n。

     2) 找到新的尾部,第 (n - k % n - 1) 个节点 ,新的链表头是第 (n - k % n) 个节点。

     3) 断开环 new_tail.next = None,并返回新的链表头 new_head。

    leetcode-cn.com/problems/ro…

    K 个一组翻转链表

    思路1

    把原链表分成若干小段,然后分别对其进行翻转,那么肯定总共需要两个函数,一个是用来分段的,一个是用来翻转的,我们就以题目中给的例子来看,对于给定链表1->2->3->4->5,一般在处理链表问题时,我们大多时候都会在开头再加一个dummy node,因为翻转链表时头结点可能会变化,为了记录当前最新的头结点的位置而引入的dummy node,那么我们加入dummy node后的链表变为-1->1->2->3->4->5,如果k为3的话,我们的目标是将1,2,3翻转一下,那么我们需要一些指针,pre和next分别指向要翻转的链表的前后的位置,然后翻转后pre的位置更新到如下新的位置,以此类推,只要next走过k个节点,就可以调用翻转函数来进行局部翻转了

    leetcode-cn.com/problems/re…

    思路2

    用栈,我们把 k 个数压入栈中,然后弹出来的顺序就是翻转的! 这里要注意几个问题:

     第一,剩下的链表个数够不够 k 个(因为不够 k 个不用翻转);

     第二,已经翻转的部分要与剩下链表连接起来。  

    leetcode-cn.com/problems/re…