链表
链表是一种常见的数据结构，链表中的数据是以节点表示的。每一个节点都有数据域(Data)和指针域(Next)，数据域用来存放数据，指针域指向下一个节点。
节点示意图.png
这样节点一个一个的连接起来就构成了简单的链表，
简单链表.png
链表可以分为单向链表，双向链表和循环链表。我们先来看一下单向链表。
单向链表
插入节点
插入节点.png
主要代码实现:
节点
@interface XSYSingleNode : NSObject<NSCopying,NSMutableCopying>
@property (nonatomic, strong) id key;
@property (nonatomic, strong) id value;
@property (nonatomic, strong) XSYSingleNode * next;
+ (instancetype)nodeWithKey:(id)key value:(id)value;
- (instancetype)initWithKey:(id)key value:(id)value;
@end
@implementation XSYSingleNode
- (instancetype)initWithKey:(id)key value:(id)value{
self.key = key;
self.value = value;
return [self init];
}
+ (instancetype)nodeWithKey:(id)key value:(id)value{
return [[self alloc] initWithKey:key value:value];
}
- (instancetype)init{
if (self = [super init]) {
}
return self;
}
- (id)copyWithZone:(NSZone *)zone{
XSYSingleNode * node = [[XSYSingleNode allocWithZone:zone] init];
node.key = self.key;
node.value = self.value;
node.next = self.next;
return node;
}
- (id)mutableCopyWithZone:(NSZone *)zone{
return [self copyWithZone:zone];
}
@end
- (void)insertNode:(XSYSingleNode *)node{
if (!node || !node.key || !node.value) {
return;
}
if (!_head) {
_head = node;
}
else{
XSYSingleNode * nod = _head;
while (nod.next) {
nod= nod.next;
}
nod.next = node;
}
_nodeDic[node.key] = node.value;
}
测试：
XSYSingleLinkedList * singleList = [XSYSingleLinkedList singleLinkedList];
XSYSingleNode * firNode = nil;
XSYSingleNode * delNode = nil;
for (int i = 1; i < 6; i ++) {
XSYSingleNode * node = [XSYSingleNode nodeWithKey:
[NSString stringWithFormat:@"%d",i] value:[NSString stringWithFormat:@"xsy_%02d",i]];
[singleList insertNode:node];
if (i == 1) {
firNode = node;
}
else if(i == 3){
delNode = node;
}
}
打印结果：
(
"xsy_01",
"xsy_02",
"xsy_03",
"xsy_04",
"xsy_05"
)
删除节点
删除节点.png
- (BOOL)removeNode:(XSYSingleNode *)node{
BOOL result = NO;
if ([[_nodeDic allKeys] containsObject:node.key]) {
result = YES;
if (node.next) {
node.key = node.next.key;
node.value = node.next.value;
node.next = node.next.next;
}
else{
// 删除头结点
_head = nil;
}
[_nodeDic removeObjectForKey:node];
}
return result;
}
测试：
BOOL result1 = [singleList removeNode:firNode];
NSLog(@"删除节点 --- %d",result1);
BOOL result2 = [singleList removeNode:delNode];
NSLog(@"删除节点 --- %d",result2);
NSLog(@"所有节点为 b--- %@",[singleList allNodes]);
打印结果:
删除节点 --- 1
删除节点 --- 1
所有节点为 b--- (
"xsy_02",
"xsy_04",
"xsy_05"
)
