浅谈iOS 数据结构之链表

链表（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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。