您好,登錄后才能下訂單哦!
這篇文章主要介紹iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析,文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
鏈表(Linked List)是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的,表現(xiàn)形式如下圖所示:
單鏈表
雙鏈表
數(shù)組和鏈表區(qū)別:
數(shù)組:數(shù)組元素在內(nèi)存上連續(xù)存放,可以通過下標(biāo)查找元素;插入、刪除需要移動大量元素,比較適用于元素很少變化的情況
鏈表:鏈表中的元素在內(nèi)存中不是順序存儲的,查找慢,插入、刪除只需要對元素指針重新賦值,效率高
Objective-C 里沒有現(xiàn)成的鏈表結(jié)構(gòu),下面我實現(xiàn)了非線程安全的單鏈表和雙鏈表,以下都是具體的實現(xiàn)細節(jié),完整代碼可以在這兒下載
單鏈表
單鏈表提供了插入、刪除、查詢、反轉(zhuǎn)等操作,具體實現(xiàn)如下:
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
雙鏈表
雙鏈表提供了插入、刪除、查詢操作,具體實現(xiàn)如下:
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數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。