iOS 数据结构之链表

百家 作者:iOS开发 2017-10-09 11:30:00 阅读:221

点击上方“iOS开发”,选择“置顶公众号”

关键时刻,第一时间送达!


链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,表现形式如下图所示:


单链表



双链表



数组和链表区别:


  • 数组:数组元素在内存上连续存放,可以通过下标查找元素;插入、删除需要移动大量元素,比较适用于元素很少变化的情况

  • 链表:链表中的元素在内存中不是顺序存储的,查找慢,插入、删除只需要对元素指针重新赋值,效率高


Objective-C 里没有现成的链表结构,下面我实现了非线程安全的单链表和双链表,以下都是具体的实现细节,完整代码可以在这儿下载


单链表


单链表提供了插入、删除、查询、反转等操作,具体实现如下:


BBSingleLinkedList.h


#import

@interface BBSingleLinkedNode : NSObject

@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

@interface BBLinkedNode : NSObject

@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


  • 作者: hi_xgb

  • 链接:http://www.jianshu.com/p/12fe060811f2

  • 來源:简书

  • iOS开发整理发布,转载请联系作者授权

【点击成为安卓大神】

关注公众号:拾黑(shiheibook)了解更多

[广告]赞助链接:

四季很好,只要有你,文娱排行榜:http://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/

图库
关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接