浅谈iOS 数据结构之链表

#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

#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

#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

#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