iOS数据结构之链表的示例分析-创新互联
这篇文章主要介绍iOS数据结构之链表的示例分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
成都创新互联公司是一家专注于网站设计制作、成都做网站与策划设计,徐汇网站建设哪家好?成都创新互联公司做网站,专注于网站建设十多年,网设计领域的专业建站公司;建站业务涵盖:徐汇等地区。徐汇做网站价格咨询:18980820575链表（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数据结构之链表的示例分析”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联网站建设公司行业资讯频道！
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文标题：iOS数据结构之链表的示例分析-创新互联
浏览地址：https://www.cdcxhl.com/article42/dhphhc.html
成都网站建设公司_创新互联，为您提供定制开发、微信公众号、Google、网站制作、搜索引擎优化、微信小程序
声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联
- 创新互联电商外贸建站的优势！ 2015-04-20
- 外贸建站需要哪些东西 2021-11-15
- 外贸建站租用香港云服务器还是美国云服务器好？ 2022-10-02
- 外贸建站的推广方式有哪些 2016-04-18
- 外贸建站需要哪些东西？ 2014-07-23
- 成都外贸建站怎样才能有效果 2015-04-01
- 外贸建站中的哪些细节影响着网站流量？ 2015-06-11
- 外贸建站前必看的四大技巧及优化系统 2022-05-27
- 外贸建站seo推广除了内容，页面链接也很重要 2016-08-19
- 深圳网站建设之外贸建站原则 2015-10-26
- 外贸建站完成后如何继续完善 2021-08-25
- 外贸建站域名该怎么选？ 2015-06-08