链表 ,数组 是我们经常碰到的线性数据结构, 是一种真正的动态数据结构 ,而数组是一段连续的内存空间,通过指针偏移去取数组里相邻的数据,而链表是将不同的内存空间,连在在一起,类似于我们生活中常见的火车车厢,每节车厢就可以看做是一个数据,只不过这个数据内部还有个指针指向它下一个节点的数据.
image.png
因此链表需要有个头节点 ,可以方便的进行查询 添加 移除等操作,小编通过学习链表这种数据结构的特点,用 Objective-C 语言实现了一个单向链表,即只有一个头节点 最后一个节点为 NULL.
//
// LinkedList.h
// ArrayList
//
// Created by dzb on 2018/8/3.
// Copyright © 2018 大兵布莱恩特. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface LinkedList <ObjectType> : NSObject
- (void) addObjectAtFirst:(ObjectType)object;
- (void) addObjectAtLast:(ObjectType)object;
- (void) addObject:(ObjectType)object atIndex:(NSInteger)index;
- (void) updateObject:(ObjectType)object atIndex:(NSInteger)index;
- (BOOL) containObject:(ObjectType)object;
- (ObjectType) objectAtIndex:(NSInteger)index;
- (ObjectType) removeObjectAtIndex:(NSInteger)index;
- (ObjectType) removeFirstObject;
- (ObjectType) removeLastObject;
///count
@property (nonatomic,assign) NSInteger count;
///empty
@property (nonatomic,assign,getter=isEmpty,readonly) BOOL empty;
///firstObject
@property (nonatomic,strong,readonly) ObjectType firstObject;
///lastObject
@property (nonatomic,strong,readonly) ObjectType lastObject;
@end
//
// LinkedList.m
// ArrayList
//
// Created by dzb on 2018/8/3.
// Copyright © 2018 大兵布莱恩特. All rights reserved.
//
#import "LinkedList.h"
typedef void* AnyObject;
typedef struct node {
AnyObject data;
struct node *next;
} Node;
@interface LinkedList ()
///head
@property (nonatomic,assign) Node *dummyHead;
///size
@property (nonatomic,assign) NSInteger size;
@end
@implementation LinkedList
- (instancetype)init
{
self = [super init];
if (self) {
Node * dummyHead = (Node*)malloc(sizeof(Node));
dummyHead->data = nil;
dummyHead->next = nil;
self.dummyHead = dummyHead;
self.size = 0;
}
return self;
}
- (void)addObjectAtFirst:(id)object {
[self addObject:object atIndex:0];
}
- (void)addObjectAtLast:(id)object {
[self addObject:object atIndex:self.size];
}
- (void)addObject:(id)object atIndex:(NSInteger)index {
if (index < 0 || index > self.count) {
@throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
return;
}
Node *prev = self.dummyHead;
for (int i = 0; i< index; i++) {
prev = prev->next;
}
Node *cur = (Node*)malloc(sizeof(Node));
cur->data = (__bridge_retained AnyObject)object;
cur->next = prev->next;
prev->next = cur;
self.size++;
}
- (id)objectAtIndex:(NSInteger)index {
if (index < 0 || index >= self.count) {
@throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
return nil;
}
Node *cur = self.dummyHead->next;
for (int i = 0; i<index; i++) {
cur = cur->next;
}
return (__bridge_transfer id)cur->data;
}
- (id)firstObject {
return [self objectAtIndex:0];
}
- (id)lastObject {
return [self objectAtIndex:self.count-1];
}
- (void)updateObject:(id)object atIndex:(NSInteger)index {
if (index < 0 || index >= self.count) {
@throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
return;
}
Node *cur = self.dummyHead->next;
for (int i = 0; i<index; i++) {
cur = cur->next;
}
CFRelease(cur->data);
cur->data = (__bridge_retained AnyObject)object;
}
- (BOOL)containObject:(id)object {
Node *cur = self.dummyHead->next;
while (cur != NULL) {
id data = (__bridge_transfer id)cur->data;
if ([data isEqual:object])
return YES;
cur = cur->next;
}
return NO;
}
- (id) removeObjectAtIndex:(NSInteger)index {
if (index < 0 || index >= self.count) {
@throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
return nil;
}
Node *prev = self.dummyHead;
for (int i = 0; i<index; i++) {
prev = prev->next;
}
Node *deleteNode = prev->next;
prev->next = deleteNode->next;
id object = (__bridge_transfer id)deleteNode->data;
free(deleteNode);
deleteNode = NULL;
self.size--;
return object;
}
- (id) removeFirstObject {
return [self removeObjectAtIndex:0];
}
- (id) removeLastObject {
return [self removeObjectAtIndex:self.count-1];
}
- (NSInteger)count {
return self.size;
}
- (NSString *)description {
NSMutableString *string = [NSMutableString stringWithFormat:@"\nLinkedList %p : [ \n" ,self];
Node *cur = self.dummyHead->next;
while (cur != nil) {
[string appendFormat:@"%@ -> \n",cur->data];
cur = cur->next;
}
[string appendString:@"NULL\n"];
[string appendString:@"]\n"];
return string;
}
- (BOOL)isEmpty {
return self.count == 0;
}
- (void)dealloc
{
while (self.count != 0) {
[self removeFirstObject];
}
}
@end
整个链表才有了头插法往链表里插入一个新的元素,即新来的元素插入到头节点位置, 当创建一个空链表时候 链表的头节点为一个空的 Node ,即 Node->data 和 Node->next 都为 NULL, 这样以后可要根据这个头节点往下查找每个节点的数据,进行增加 删除 修改 和查找的操作. 并管理了对象的引用计数 ,当链表销毁时会对内部的每一个节点进行释放内存的操作,并对节点内管理的对象引用计数进行-1操作,以保证存入链表的 OC 对象能够完美释放内存.
下边是测试用例
- (void) test {
static int count = 0;
if (count > 9) {
[_timer invalidate];
_timer = nil;
NSLog(@"time is %@",[_timeArray valueForKeyPath:@"@avg.self"]);
return;
}
dispatch_async(dispatch_get_global_queue(0, 0), ^{
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
int number = 100000;
Person *p = [Person new];
LinkedList <Person *> *linked = [[LinkedList alloc] init];
for (int i = 0; i<number; i++) {
[linked addObjectAtFirst:p];
}
CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
CFTimeInterval duration = linkTime * 1000.0f;
NSLog(@"Linked in %f ms",duration);
[self->_timeArray addObject:@(duration)];
count++;
});
}
image.png
往链表里添加10万个 同一个 person 对象 ,实质就是对 person 的引用计数+1 ,当链表销毁时候 再对同一个 person 对象执行 移除操作 ,使其引用计数为 0 ,Person 对象才会立马销毁
好了，我是大兵布莱恩特，欢迎加入博主技术交流群，iOS 开发交流群
QQ20180712-0.png
网友评论