鏈表（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以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
