淺談iOS 數(shù)據(jù)結(jié)構(gòu)之鏈表
更新時間：2017年09月07日 10:10:01 作者：hi_xgb
這篇文章主要介紹了淺談iOS 數(shù)據(jù)結(jié)構(gòu)之鏈表，本文詳細(xì)的介紹了單鏈表和雙鏈表，具有一定的參考價值，有興趣的可以了解一下
鏈表（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)細(xì)節(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
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本篇文章給大家講述了在APP第一次沒有審核通過后，重新提交的流程和注意的地方，學(xué)習(xí)一下吧。2017-12-12
這篇文章主要為大家詳細(xì)介紹了IOS圖層轉(zhuǎn)場動畫， CATransition類實現(xiàn)層的轉(zhuǎn)場動畫，能夠為層提供移出屏幕和移入屏幕的動畫效果，感興趣的小伙伴們可以參考一下2016-02-02
ios App加載本地HTML網(wǎng)頁,點(diǎn)擊網(wǎng)頁鏈接跳轉(zhuǎn)到app頁面的方法
下面小編就為大家分享一篇ios App加載本地HTML網(wǎng)頁,點(diǎn)擊網(wǎng)頁鏈接跳轉(zhuǎn)到app頁面的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-01-01
解析Objective-C?中?`+load`?方法的執(zhí)行順序
在?Objective-C?中,+load?方法是在類或分類被加載到內(nèi)存時調(diào)用的,它在程序啟動過程中非常早的階段執(zhí)行,用于在類或分類被加載時進(jìn)行一些初始化工作,這篇文章主要介紹了?Objective-C?中?`+load`?方法的執(zhí)行順序,需要的朋友可以參考下2024-07-07
百度地圖已經(jīng)開放了地圖API，大家可以很方便的調(diào)用地圖中的相應(yīng)數(shù)據(jù)，并完成各項個性化的展示，下面這篇文章主要給大家介紹了關(guān)于iOS如何實現(xiàn)百度地圖拖拽后更新位置以及反編碼的相關(guān)資料，需要的朋友可以參考借鑒，下面來一起看看吧。2017-12-12
IOS 基礎(chǔ)之設(shè)置 tableview 的分割線
這篇文章主要介紹了IOS 基礎(chǔ)之設(shè)置 tableview 的分割線的相關(guān)資料,需要的朋友可以參考下2017-03-03
這篇文章主要為大家介紹了iOS底層實例解析Swift閉包及OC閉包，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
iOS在頁面銷毀時如何優(yōu)雅的cancel網(wǎng)絡(luò)請求詳解
這篇文章主要給大家介紹了關(guān)于iOS在頁面銷毀時如何優(yōu)雅的cancel網(wǎng)絡(luò)請求的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-05-05
關(guān)于地理位置及定位系統(tǒng)，在iOS開發(fā)中也比較常見，接下來通過本文給大家介紹IOS入門筆記之地理位置定位系統(tǒng)，對ios地理位置定位系統(tǒng)感興趣的朋友一起學(xué)習(xí)吧2016-01-01
這篇文章主要介紹了談?wù)勚谱鱥OS Ad-Hoc測試應(yīng)用,AD-HOC測試是指隨機(jī)測試，這種測試的特點(diǎn)是無特定的測試用例，有興趣的可以了解一下。2016-12-12