这篇文章主要介绍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
以上是“iOS数据结构之链表的示例分析”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。