中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析-創(chuàng)新互聯(lián)

這篇文章主要介紹iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

成都創(chuàng)新互聯(lián)公司是一家專注于網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站與策劃設(shè)計(jì),徐匯網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:徐匯等地區(qū)。徐匯做網(wǎng)站價(jià)格咨詢:18980820575

鏈表（Linked List）是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，表現(xiàn)形式如下圖所示：

單鏈表

iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析

雙鏈表

iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析

數(shù)組和鏈表區(qū)別：

  • 數(shù)組：數(shù)組元素在內(nèi)存上連續(xù)存放，可以通過下標(biāo)查找元素；插入、刪除需要移動(dòng)大量元素，比較適用于元素很少變化的情況

  • 鏈表：鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的，查找慢，插入、刪除只需要對(duì)元素指針重新賦值，效率高

Objective-C 里沒有現(xiàn)成的鏈表結(jié)構(gòu)，下面我實(shí)現(xiàn)了非線程安全的單鏈表和雙鏈表，以下都是具體的實(shí)現(xiàn)細(xì)節(jié)，完整代碼可以在這兒下載

單鏈表

單鏈表提供了插入、刪除、查詢、反轉(zhuǎn)等操作，具體實(shí)現(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

雙鏈表

雙鏈表提供了插入、刪除、查詢操作，具體實(shí)現(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)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.rwnh.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

本文標(biāo)題：iOS數(shù)據(jù)結(jié)構(gòu)之鏈表的示例分析-創(chuàng)新互聯(lián)
瀏覽地址：http://www.rwnh.cn/article42/dhphhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、微信公眾號(hào)、Google、網(wǎng)站制作、搜索引擎優(yōu)化、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

手機(jī)網(wǎng)站建設(shè)
峨眉山市| 织金县| 常德市| 河池市| 阿巴嘎旗| 沙田区| 乌什县| 建德市| 九龙城区| 增城市| 炎陵县| 南郑县| 威信县| 洪雅县| 织金县| 资中县| 星座| 丽水市| 苏尼特右旗| 聊城市| 荆州市| 高唐县| 宝坻区| 岱山县| 四川省| 巴楚县| 密云县| 利辛县| 廉江市| 山丹县| 沙雅县| 克什克腾旗| 天祝| 灵武市| 特克斯县| 姚安县| 伊宁县| 容城县| 类乌齐县| 铁岭县| 平邑县|