浅谈iOS 数据结构之链表

原文

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，表现形式如下图所示：

单链表

双链表

数组和链表区别：

  • 数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
  • 链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

Objective-C 里没有现成的链表结构，下面我实现了非线程安全的单链表和双链表，以下都是具体的实现细节，完整代码可以在这儿下载

单链表

单链表提供了插入、删除、查询、反转等操作，具体实现如下：

BBSingleLinkedList.h

#import <Foundation/Foundation.h>

@interface BBSingleLinkedNode : NSObject <NSCopying>

@property (nonatomic, strong) NSString *key;
@property (nonatomic, strong) NSString *value;
@property (nonatomic, strong) BBSingleLinkedNode *next;

- (instancetype)initWithKey:(NSString *)key
      value:(NSString *)value;

  (instancetype)nodeWithKey:(NSString *)key
      value:(NSString *)value;

@end

@interface BBSingleLinkedList : NSObject

- (void)insertNode:(BBSingleLinkedNode *)node;
- (void)insertNodeAtHead:(BBSingleLinkedNode *)node;
- (void)insertNode:(BBSingleLinkedNode *)newNode beforeNodeForKey:(NSString *)key;
- (void)insertNode:(BBSingleLinkedNode *)newNode afterNodeForKey:(NSString *)key;

- (void)bringNodeToHead:(BBSingleLinkedNode *)node;

- (void)removeNode:(BBSingleLinkedNode *)node;

- (BBSingleLinkedNode *)nodeForKey:(NSString *)key;
- (BBSingleLinkedNode *)headNode;
- (BBSingleLinkedNode *)lastNode;

- (NSInteger)length;
- (BOOL)isEmpty;

- (void)reverse;
- (void)readAllNode;

@end

BBSingleLinkedList.m

#import "BBSingleLinkedList.h"

@implementation BBSingleLinkedNode

- (instancetype)initWithKey:(NSString *)key
      value:(NSString *)value
{
 if (self = [super init]) {
  _key = key;
  _value = value;
 }
 return self;
}

  (instancetype)nodeWithKey:(NSString *)key
      value:(NSString *)value
{
 return [[[self class] alloc] initWithKey:key value:value];
}

#pragma mark - NSCopying
- (id)copyWithZone:(nullable NSZone *)zone
{
 BBSingleLinkedNode *newNode = [[BBSingleLinkedNode allocWithZone:zone] init];
 newNode.key = self.key;
 newNode.value = self.value;
 newNode.next = self.next;
 return newNode;
}

@end

@interface BBSingleLinkedList ()

@property (nonatomic, strong) BBSingleLinkedNode *headNode;
@property (nonatomic, strong) NSMutableDictionary *innerMap;

@end

@implementation BBSingleLinkedList

- (instancetype)init
{
 self = [super init];
 if (self) {
  _innerMap = [NSMutableDictionary new];
 }
 return self;
}

#pragma mark - public
- (void)insertNodeAtHead:(BBSingleLinkedNode *)node
{
 if (!node || node.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:node]) {
  return;
 }
 
 _innerMap[node.key] = node;
 if (_headNode) {
  node.next = _headNode;
  _headNode = node;
 } else {
  _headNode = node;
 }
}

- (void)insertNode:(BBSingleLinkedNode *)node
{
 if (!node || node.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:node]) {
  return;
 }
 
 _innerMap[node.key] = node;
 
 if (!_headNode) {
  _headNode = node;
  return;
 }
 BBSingleLinkedNode *lastNode = [self lastNode];
 lastNode.next = node;
}

- (void)insertNode:(BBSingleLinkedNode *)newNode beforeNodeForKey:(NSString *)key
{
 if (key.length == 0 || !newNode || newNode.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:newNode]) {
  return;
 }
 
 if (!_headNode) {
  _headNode = newNode;
  return;
 }
 
 BBSingleLinkedNode *node = _innerMap[key];
 if (node) {
  _innerMap[newNode.key] = newNode;
  BBSingleLinkedNode *aheadNode = [self nodeBeforeNode:node];
  if (aheadNode) {
   aheadNode.next = newNode;
   newNode.next = node;
  } else {
   _headNode = newNode;
   newNode.next = node;
  }
  
 } else {
  [self insertNode:newNode]; //insert to tail
 }
}

- (void)insertNode:(BBSingleLinkedNode *)newNode afterNodeForKey:(NSString *)key
{
 if (key.length == 0 || !newNode || newNode.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:newNode]) {
  return;
 }
 
 if (!_headNode) {
  _headNode = newNode;
  return;
 }
 
 BBSingleLinkedNode *node = _innerMap[key];
 if (node) {
  _innerMap[newNode.key] = newNode;
  newNode.next = node.next;
  node.next = newNode;
 } else {
  [self insertNode:newNode]; //insert to tail
 }
}

- (void)removeNode:(BBSingleLinkedNode *)node
{
 if (!node || node.key.length == 0) {
  return;
 }
 [_innerMap removeObjectForKey:node.key];
 
 if (node.next) {
  node.key = node.next.key;
  node.value = node.next.value;
  node.next = node.next.next;
 } else {
  BBSingleLinkedNode *aheadNode = [self nodeBeforeNode:node];
  aheadNode.next = nil;
 }
}

- (void)bringNodeToHead:(BBSingleLinkedNode *)node
{
 if (!node || !_headNode) {
  return;
 }
 
 if ([node isEqual:_headNode]) {
  return;
 }
 
 BBSingleLinkedNode *aheadNode = [self nodeBeforeNode:node];
 aheadNode.next = node.next;
 node.next = _headNode;
 _headNode = node;
}

- (BBSingleLinkedNode *)nodeForKey:(NSString *)key
{
 if (key.length == 0) {
  return nil;
 }
 BBSingleLinkedNode *node = _innerMap[key];
 return node;
}

- (BBSingleLinkedNode *)headNode
{
 return _headNode;
}

- (BBSingleLinkedNode *)lastNode
{
 BBSingleLinkedNode *last = _headNode;
 while (last.next) {
  last = last.next;
 }
 return last;
}

- (void)reverse
{
 BBSingleLinkedNode *prev = nil;
 BBSingleLinkedNode *current = _headNode;
 BBSingleLinkedNode *next = nil;
 
 while (current) {
  next = current.next;
  current.next = prev;
  prev = current;
  current = next;
 }
 
 _headNode = prev;
}

- (void)readAllNode
{
 BBSingleLinkedNode *tmpNode = _headNode;
 while (tmpNode) {
  NSLog(@"node key -- %@, node value -- %@", tmpNode.key, tmpNode.value);
  tmpNode = tmpNode.next;
 }
}

- (NSInteger)length
{
 NSInteger _len = 0;
 for (BBSingleLinkedNode *node = _headNode; node; node = node.next) {
  _len   ;
 }
 return _len;
}

- (BOOL)isEmpty
{
 return _headNode == nil;
}

#pragma mark - private
- (BBSingleLinkedNode *)nodeBeforeNode:(BBSingleLinkedNode *)node
{
 BBSingleLinkedNode *targetNode = nil;
 BBSingleLinkedNode *tmpNode = _headNode;
 while (tmpNode) {
  if ([tmpNode.next isEqual:node]) {
   targetNode = tmpNode;
   break;
  } else {
   tmpNode = tmpNode.next;
  }
 }
 return targetNode;
}

- (BOOL)isNodeExists:(BBSingleLinkedNode *)node
{
 BBSingleLinkedNode *tmpNode = _headNode;
 while (tmpNode) {
  if ([tmpNode isEqual:node]) {
   return YES;
  }
  tmpNode = tmpNode.next;
 }
 return false;
}

@end

双链表

双链表提供了插入、删除、查询操作，具体实现如下：

BBLinkedMap.h

#import <Foundation/Foundation.h>

@interface BBLinkedNode : NSObject <NSCopying>

@property (nonatomic, strong) NSString *key;
@property (nonatomic, strong) NSString *value;
@property (nonatomic, strong) BBLinkedNode *prev;
@property (nonatomic, strong) BBLinkedNode *next;

- (instancetype)initWithKey:(NSString *)key
      value:(NSString *)value;

  (instancetype)nodeWithKey:(NSString *)key
      value:(NSString *)value;

@end

@interface BBLinkedMap : NSObject

- (void)insertNodeAtHead:(BBLinkedNode *)node;
- (void)insertNode:(BBLinkedNode *)node;
- (void)insertNode:(BBLinkedNode *)newNode beforeNodeForKey:(NSString *)key;
- (void)insertNode:(BBLinkedNode *)newNode afterNodeForKey:(NSString *)key;
- (void)bringNodeToHead:(BBLinkedNode *)node;

- (void)readAllNode;
- (void)removeNodeForKey:(NSString *)key;
- (void)removeTailNode;

- (NSInteger)length;
- (BOOL)isEmpty;

- (BBLinkedNode *)nodeForKey:(NSString *)key;
- (BBLinkedNode *)headNode;
- (BBLinkedNode *)tailNode;

@end

BBLinkedMap.m

#import "BBLinkedMap.h"

@implementation BBLinkedNode

- (instancetype)initWithKey:(NSString *)key
      value:(NSString *)value
{
 if (self = [super init]) {
  _key = key;
  _value = value;
 }
 return self;
}

  (instancetype)nodeWithKey:(NSString *)key
      value:(NSString *)value
{
 return [[[self class] alloc] initWithKey:key value:value];
}

#pragma mark - NSCopying
- (id)copyWithZone:(nullable NSZone *)zone
{
 BBLinkedNode *newNode = [[BBLinkedNode allocWithZone:zone] init];
 newNode.key = self.key;
 newNode.value = self.value;
 newNode.prev = self.prev;
 newNode.next = self.next;
 return newNode;
}

@end

@interface BBLinkedMap ()

@property (nonatomic, strong) BBLinkedNode *headNode;
@property (nonatomic, strong) BBLinkedNode *tailNode;
@property (nonatomic, strong) NSMutableDictionary *innerMap;

@end

@implementation BBLinkedMap

- (instancetype)init
{
 self = [super init];
 if (self) {
  _innerMap = [NSMutableDictionary new];
 }
 return self;
}

#pragma mark - public
- (void)insertNodeAtHead:(BBLinkedNode *)node
{
 if (!node || node.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:node]) {
  return;
 }
 
 _innerMap[node.key] = node;
 
 if (_headNode) {
  node.next = _headNode;
  _headNode.prev = node;
  _headNode = node;
 } else {
  _headNode = _tailNode = node;
 }
}

- (void)insertNode:(BBLinkedNode *)node
{
 if (!node || node.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:node]) {
  return;
 }
 
 if (!_headNode && !_tailNode) {
  _headNode = _tailNode = node;
  return;
 }
 
 _innerMap[node.key] = node;
 
 _tailNode.next = node;
 node.prev = _tailNode;
 _tailNode = node;
}

- (void)insertNode:(BBLinkedNode *)newNode beforeNodeForKey:(NSString *)key
{
 if (key.length == 0 || !newNode || newNode.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:newNode]) {
  return;
 }
 
 if (!_headNode && !_tailNode) {
  _headNode = _tailNode = newNode;
  return;
 }
 
 BBLinkedNode *node = _innerMap[key];
 if (node) {
  _innerMap[newNode.key] = newNode;
  if (node.prev) {
   node.prev.next = newNode;
   newNode.prev = node.prev;
  } else {
   _headNode = newNode;
  }
  node.prev = newNode;
  newNode.next = node;
 } else {
  [self insertNode:newNode]; //insert to tail
 }
 
}

- (void)insertNode:(BBLinkedNode *)newNode afterNodeForKey:(NSString *)key
{
 if (key.length == 0 || !newNode || newNode.key.length == 0) {
  return;
 }
 
 if ([self isNodeExists:newNode]) {
  return;
 }
 
 if (!_headNode && !_tailNode) {
  _headNode = _tailNode = newNode;
  return;
 }
 
 BBLinkedNode *node = _innerMap[key];
 if (node) {
  _innerMap[newNode.key] = newNode;
  if (node.next) {
   newNode.next = node.next;
   node.next.prev = newNode;
  } else {
   _tailNode = newNode;
  }
  newNode.prev = node;
  node.next = newNode;
 } else {
  [self insertNode:newNode]; //insert to tail
 }
}

- (void)bringNodeToHead:(BBLinkedNode *)node
{
 if (!node) {
  return;
 }
 if (!_headNode && !_tailNode) {
  _headNode = _tailNode = node;
  return;
 }
 
 if ([_headNode isEqual:node]) {
  return;
 }
 
 if ([_tailNode isEqual:node]) {
  _tailNode = node.prev;
  _tailNode.next = nil;
 } else {
  node.prev.next = node.next;
  node.next.prev = node.prev;
 }
 
 _headNode.prev = node;
 node.next = _headNode;
 node.prev = nil;
 _headNode = node;
}

- (void)removeNodeForKey:(NSString *)key
{
 if (key.length == 0) {
  return;
 }
 
 BBLinkedNode *node = _innerMap[key];
 if (!node) {
  return;
 }
 
 [_innerMap removeObjectForKey:key];
 
 if ([_headNode isEqual:node]) {
  _headNode = node.next;
 } else if ([_tailNode isEqual:node]) {
  _tailNode = node.prev;
 }
 
 node.prev.next = node.next;
 node.next.prev = node.prev;
 
}

- (void)removeTailNode
{
 if (!_tailNode || _tailNode.key.length == 0) {
  return;
 }
 
 [_innerMap removeObjectForKey:_tailNode.key];
 if (_headNode == _tailNode) {
  _headNode = _tailNode = nil;
  return;
 }
 
 _tailNode = _tailNode.prev;
 _tailNode.next = nil;
}

- (BBLinkedNode *)nodeForKey:(NSString *)key
{
 if (key.length == 0) {
  return nil;
 }
 BBLinkedNode *node = _innerMap[key];
 return node;
}

- (BBLinkedNode *)headNode
{
 return _headNode;
}

- (BBLinkedNode *)tailNode
{
 return _tailNode;
}

- (void)readAllNode
{
 BBLinkedNode *node = _headNode;
 while (node) {
  NSLog(@"node key -- %@, node value -- %@", node.key, node.value);
  node = node.next;
 }
}

- (NSInteger)length
{
 NSInteger _len = 0;
 for (BBLinkedNode *node = _headNode; node; node = node.next) {
  _len   ;
 }
 return _len;
}

- (BOOL)isEmpty
{
 return _headNode == nil;
}

#pragma mark - private
- (BOOL)isNodeExists:(BBLinkedNode *)node
{
 BBLinkedNode *tmpNode = _headNode;
 while (tmpNode) {
  if ([tmpNode isEqual:node]) {
   return YES;
  }
  tmpNode = tmpNode.next;
 }
 return false;
}

@end

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持Devmax。

浅谈iOS 数据结构之链表的更多相关文章

  1. HTML5在微信内置浏览器下右上角菜单的调整字体导致页面显示错乱的问题

    HTML5在微信内置浏览器下，在右上角菜单的调整字体导致页面显示错乱的问题，本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友参考下吧

  2. iOS实现拖拽View跟随手指浮动效果

    这篇文章主要为大家详细介绍了iOS实现拖拽View跟随手指浮动，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

  3. ios – containerURLForSecurityApplicationGroupIdentifier：在iPhone和Watch模拟器上给出不同的结果

    我使用默认的XCode模板创建了一个WatchKit应用程序.我向iOSTarget,WatchkitAppTarget和WatchkitAppExtensionTarget添加了应用程序组权利.(这是应用程序组名称：group.com.lombax.fiveminutes)然后,我尝试使用iOSApp和WatchKitExtension访问共享文件夹URL：延期：iOS应用：但是,测试NSURL

  4. ios – Testflight无法安装应用程序

    我有几个测试人员注册了testflight并连接了他们的设备……他们有不同的ios型号……但是所有这些都有同样的问题.当他们从“safari”或“testflight”应用程序本身单击应用程序的安装按钮时……达到约90％并出现错误消息…

  5. ibm-mobilefirst – 在iOS 7.1上获取“无法安装应用程序,因为证书无效”错误

    当我的客户端将他们的设备更新到iOS7.1,然后尝试从AppCenter更新我们的应用程序时,我收到了上述错误.经过一番搜索,我找到了一个类似问题的帖子here.但是后来因为我在客户端使用AppCenter更新应用程序的环境中,我无法使用USB插件并为他们安装应用程序.在发布支持之前,是否有通过AppCenter进行下载的解决方法？

  6. ios – 视图的简单拖放？

    我正在学习iOS,但我找不到如何向UIView添加拖放行为.我试过了：它说“UIView没有可见的接口声明选择器addTarget”此外,我尝试添加平移手势识别器,但不确定这是否是我需要的它被称为,但不知道如何获得事件的坐标.在iOS中注册移动事件回调/拖放操作的标准简单方法是什么？

  7. ios – 什么控制iTunes中iPhone应用程序支持的语言列表？

    什么控制iPhone应用程序的iTunes页面中支持的语言？

  8. ios – 获得APNs响应BadDeviceToken或Unregistered的可能原因是什么？

    我知道设备令牌在某些时候是有效的.用户如何使其设备令牌变坏？从关于“未注册”的文档：Thedevicetokenisinactiveforthespecifiedtopic.这是否意味着应用程序已被删除？.您应该看到四种分发方法：如果您选择AppStore或Enterprise,您将在后面的对话框中看到Xcode将APNS权利更改为生产：如果选择AdHoc或Development,则aps-environment下的文本将是开发,然后应与后端的配置匹配.

  9. ios – 当我关闭应用程序时,我从调试器获得消息：由于信号15而终止

    我怎么能解决这个问题,我不知道这个链接MypreviousproblemaboutCoredata对我的问题有影响吗？当我cmd应用程序的Q时,将出现此消息.Messagefromdebugger:Terminatedduetosignal15如果谁知道我以前的问题的解决方案,请告诉我.解决方法>来自调试器的消息：每当用户通过CMD-Q(退出)或STOP手动终止应用程序(无论是在iOS模拟器中还是

  10. ios – NSUbiquityIdentityDidChangeNotification和SIGKILL

    当应用程序被发送到后台时,我们会删除观察者吗？我遇到的问题是,当UbiquityToken发生变化时,应用程序终止,因为用户已经更改了iCloud设置.你们如何设法订阅这个通知,如果你不这样做,你会做什么来跟踪当前登录的iCloud用户？

随机推荐

  1. iOS实现拖拽View跟随手指浮动效果

    这篇文章主要为大家详细介绍了iOS实现拖拽View跟随手指浮动，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

  2. iOS – genstrings：无法连接到输出目录en.lproj

    使用我桌面上的项目文件夹,我启动终端输入：cd然后将我的项目文件夹拖到终端,它给了我路径.然后我将这行代码粘贴到终端中找.-name*.m|xargsgenstrings-oen.lproj我在终端中收到此错误消息：genstrings：无法连接到输出目录en.lproj它多次打印这行,然后说我的项目是一个目录的路径？没有.strings文件.对我做错了什么的想法？

  3. iOS 7 UIButtonBarItem图像没有色调

    如何确保按钮图标采用全局色调？解决方法只是想将其转换为根注释,以便为“回答”复选标记提供更好的上下文,并提供更好的格式.我能想出这个！

  4. ios – 在自定义相机层的AVFoundation中自动对焦和自动曝光

    为AVFoundation定制图层相机创建精确的自动对焦和曝光的最佳方法是什么？

  5. ios – Xcode找不到Alamofire,错误：没有这样的模块’Alamofire’

    我正在尝试按照github(https://github.com/Alamofire/Alamofire#cocoapods)指令将Alamofire包含在我的Swift项目中.我创建了一个新项目,导航到项目目录并运行此命令sudogeminstallcocoapods.然后我面临以下错误：搜索后我设法通过运行此命令安装cocoapodssudogeminstall-n/usr/local/bin

  6. ios – 在没有iPhone6s或更新的情况下测试ARKit

    我在决定下载Xcode9之前.我想玩新的框架–ARKit.我知道要用ARKit运行app我需要一个带有A9芯片或更新版本的设备.不幸的是我有一个较旧的.我的问题是已经下载了新Xcode的人.在我的情况下有可能运行ARKit应用程序吗？那个或其他任何模拟器？任何想法或我将不得不购买新设备？解决方法任何iOS11设备都可以使用ARKit,但是具有高质量AR体验的全球跟踪功能需要使用A9或更高版本处理器的设备.使用iOS11测试版更新您的设备是必要的.

  7. 将iOS应用移植到Android

    我们制作了一个具有2000个目标c类的退出大型iOS应用程序.我想知道有一个最佳实践指南将其移植到Android？此外,由于我们的应用程序大量使用UINavigation和UIView控制器,我想知道在Android上有类似的模型和实现.谢谢到目前为止,guenter解决方法老实说,我认为你正在计划的只是制作难以维护的糟糕代码.我意识到这听起来像很多工作,但从长远来看它会更容易,我只是将应用程序的概念“移植”到android并从头开始编写.

  8. ios – 在Swift中覆盖Objective C类方法

    我是Swift的初学者,我正在尝试在Swift项目中使用JSONModel.我想从JSONModel覆盖方法keyMapper,但我没有找到如何覆盖模型类中的Objective-C类方法.该方法的签名是：我怎样才能做到这一点？解决方法您可以像覆盖实例方法一样执行此操作,但使用class关键字除外：

  9. ios – 在WKWebView中获取链接URL

    我想在WKWebView中获取tapped链接的url.链接采用自定义格式,可触发应用中的某些操作.例如HTTP：//我的网站/帮助#深层链接对讲.我这样使用KVO：这在第一次点击链接时效果很好.但是,如果我连续两次点击相同的链接,它将不报告链接点击.是否有解决方法来解决这个问题,以便我可以检测每个点击并获取链接？任何关于这个的指针都会很棒！解决方法像这样更改addobserver在observeValue函数中,您可以获得两个值

  10. ios – 在Swift的UIView中找到UILabel

    我正在尝试在我的UIViewControllers的超级视图中找到我的UILabels.这是我的代码：这是在Objective-C中推荐的方式,但是在Swift中我只得到UIViews和CALayer.我肯定在提供给这个方法的视图中有UILabel.我错过了什么？我的UIViewController中的调用：解决方法使用函数式编程概念可以更轻松地实现这一目标.

返回
顶部