美文网首页暂时没看却需要看的iOS学习笔记数据结构和算法
iOS 数据结构之链表

iOS 数据结构之链表

作者: hi_xgb | 来源:发表于2017-09-03 21:59 被阅读1665次

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

    单链表
    双链表

    数组和链表区别：

    • 数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
    • 链表：链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高

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

    单链表

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

    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

    双链表

    双链表提供了插入、删除、查询操作，具体实现如下：

    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

    相关文章

      网友评论

      • Lilin_Coder:代码读了一下受益匪浅，但是 removeNode方法没想明白，其中的 if (node.next)这一段是什么作用呢？
        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;
        }
        InoruYang:移除的是中间段节点
      • foolishBoy:居然还用BB:stuck_out_tongue_closed_eyes:
        hi_xgb:@foolishBoy :smile::smile:
      • 大兵布莱恩特:是啊 楼主为什么不对c语言进行一次包装 去实现链表。当然也可以用现成的foundation一些东西去模拟链表 数组 字典的一些操作。不过讲数据结构只是一种思想用自己熟悉的语言去实现就行，没必要看别人用c++写的自己也用c++弄。
        hi_xgb:苹果已经为开发者考虑了很多，确实不用重新造轮子的，本文是为了熟悉一下相关的数据结构:smile:
      • Syik:希望作者能实测一下 链表跟mutableArray之间的性能差异, 若没有明显的性能差异, 在dictionary, array, set这些已经封装好的数据结构面前没有什么实用价值, 另外我之前测过各种排序算法, 实测也是远远不如系统的sort方法的..:flushed:
        YwWyW:同意，不然苹果为什么 不提供链表结构？

      本文标题：iOS 数据结构之链表

      本文链接：https://www.haomeiwen.com/subject/lhtsjxtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      暂时没看却需要看的

      iOS学习笔记

      数据结构和算法

      程序员

      iOS进阶指南

      将来跳槽用

      iOS开发

      算法

      关于我们|服务条款|联系我们|iOS 数据结构之链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！