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

歡迎大家關(guān)注我們團隊的公眾號羡铲，不定期分享各類技術(shù)干貨

image

最后編輯于：2018.06.13 21:58:04

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市儡毕，隨后出現(xiàn)的幾起案子也切，更是在濱河造成了極大的恐慌，老刑警劉巖腰湾，帶你破解...
沈念sama閱讀 207,248評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件雷恃，死亡現(xiàn)場離奇詭異，居然都是意外死亡费坊，警方通過查閱死者的電腦和手機倒槐，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,681評論 2贊 381
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來附井，“玉大人讨越，你說我怎么就攤上這事∠弁” “怎么了谎痢？”我有些...
開封第一講書人閱讀 153,443評論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵磕昼，是天一觀的道長卷雕。經(jīng)常有香客問我，道長票从，這世上最難降的妖魔是什么漫雕？我笑而不...
開封第一講書人閱讀 55,475評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮峰鄙，結(jié)果婚禮上浸间，老公的妹妹穿的比我還像新娘。我一直安慰自己吟榴，他們只是感情好魁蒜，可當(dāng)我...
茶點故事閱讀 64,458評論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著，像睡著了一般兜看。火紅的嫁衣襯著肌膚如雪锥咸。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,185評論 1贊 284
城市分裂傳說
那天细移，我揣著相機與錄音搏予，去河邊找鬼。笑死弧轧，一個胖子當(dāng)著我的面吹牛雪侥，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播精绎，決...
沈念sama閱讀 38,451評論 3贊 401
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼速缨，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了代乃？” 一聲冷哼從身側(cè)響起鸟廓，我...
開封第一講書人閱讀 37,112評論 0贊 261
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎襟己，沒想到半個月后引谜，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,609評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡擎浴，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,083評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年员咽，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片贮预。...
茶點故事閱讀 38,163評論 1贊 334
活死人
序言：一個原本活蹦亂跳的男人離奇死亡贝室，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出仿吞，到底是詐尸還是另有隱情滑频，我是刑警寧澤，帶...
沈念sama閱讀 33,803評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布唤冈，位于F島的核電站峡迷，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏你虹。R本人自食惡果不足惜绘搞，卻給世界環(huán)境...
茶點故事閱讀 39,357評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望傅物。院中可真熱鬧夯辖，春花似錦、人聲如沸董饰。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,357評論 0贊 19
一樁弒父案圆米，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至啄栓，卻和暖如春榨咐，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背谴供。一陣腳步聲響...
開封第一講書人閱讀 31,590評論 1贊 261
情欲美人皮
我被黑心中介騙來泰國打工块茁，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人桂肌。一個月前我還...
沈念sama閱讀 45,636評論 2贊 355
代替公主和親
正文我出身青樓数焊，卻偏偏與公主長得像，于是被迫代替她去往敵國和親崎场。傳聞我的和親對象是個殘疾皇子佩耳，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 42,925評論 2贊 344

iOS 數(shù)據(jù)結(jié)構(gòu)之鏈表

單鏈表

雙鏈表

單鏈表

BBSingleLinkedList.h

BBSingleLinkedList.m

雙鏈表

BBLinkedMap.h

BBLinkedMap.m

推薦閱讀更多精彩內(nèi)容