当前位置：移动技术网 > IT编程>移动开发>IOS > 浅谈iOS 数据结构之链表

浅谈iOS 数据结构之链表

2019年07月24日 | 移动技术网IT编程 | 我要评论

萝莉情人,中央大老虎是谁,虚幻彼方第二部

链表（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

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！点击进行留言回复

ios uicollectionview实现横向滚动

现在使用卡片效果的app很多，之前公司让实现一种卡片效果，就写了一篇关于实现卡片的文章。文章最后附有demo实现上我选择了使用uicollectionview ... [阅读全文]
iOS UICollectionView实现横向滑动

本文实例为大家分享了ios uicollectionview实现横向滑动的具体代码，供大家参考，具体内容如下uicollectionview的横向滚动，目前我使... [阅读全文]
iOS13适配深色模式(Dark Mode)的实现

好像大概也许是一年前, mac os系统发布了深色模式外观, 看着挺刺激, 时至今日用着也还挺爽的终于, 随着iphone11等新手机的发售, ios 13系统... [阅读全文]
ios 使用xcode11 新建项目工程的步骤详解

xcode11新建项目工程，新增了scenedelegate这个类，转而将原appdelegate负责的对ui生命周期的处理担子接了过来。故此可以理解为：ios... [阅读全文]
iOS实现转盘效果

本文实例为大家分享了ios实现转盘效果的具体代码，供大家参考，具体内容如下demo下载地址： ios转盘效果功能：实现了常用的ios转盘效果，轮盘抽奖效果的实现... [阅读全文]
iOS开发实现转盘功能

本文实例为大家分享了ios实现转盘功能的具体代码，供大家参考，具体内容如下今天给同学们讲解一下一个转盘选号的功能，直接上代码直接看viewcontroller#... [阅读全文]
iOS实现轮盘动态效果

本文实例为大家分享了ios实现轮盘动态效果的具体代码，供大家参考，具体内容如下一个常用的绘图，主要用来打分之类的动画，效果如下。主要是ios的绘图和动画，本来想... [阅读全文]
iOS实现九宫格连线手势解锁

本文实例为大家分享了ios实现九宫格连线手势解锁的具体代码，供大家参考，具体内容如下demo下载地址：效果图：核心代码：//// clockview.m// 手... [阅读全文]
iOS实现卡片堆叠效果

本文实例为大家分享了ios实现卡片堆叠效果的具体代码，供大家参考，具体内容如下如图，这就是最终效果。去年安卓5.0发布的时候，当我看到安卓全新的material... [阅读全文]
iOS利用余弦函数实现卡片浏览工具

本文实例为大家分享了ios利用余弦函数实现卡片浏览工具的具体代码，供大家参考，具体内容如下一、实现效果通过拖拽屏幕实现卡片移动，左右两侧的卡片随着拖动变小，中间... [阅读全文]

网友评论


验证码：

浅谈iOS 数据结构之链表

2019年07月24日 | 移动技术网IT编程 | 我要评论

您可能感兴趣的文章:

相关文章:

网友评论