看了波波老师讲的链表,自己Objective-C写了一个 发现,最多只能存放800个元素,存放多了后很多节点丢失了,而且当 LinkedList 释放时候 ,内部的所有 Node 节点会出现崩溃 ,不知道是同时创建了大量的 autorelease 对象释放内存问题还是因为其他原因,当存放数据800以下时 链表在释放时候么有任何问题,不会存在节点丢失.

//

//  LinkedList.m

//  ArrayList

//

//  Created by dzb on 2018/8/3.

//  Copyright © 2018 大兵布莱恩特. All rights reserved.

//

#import "LinkedList.h"

@interface Node < ObjectType > : NSObject

///ObjectType

@property (nonatomic,strong) ObjectType object;

///next

@property (nonatomic,strong) Node <ObjectType > *next;

+ (instancetype) nodeWithObject:(ObjectType)object nextNode:(Node <ObjectType> *)next;

+ (instancetype) nodeWithObject:(ObjectType)object;

- (instancetype) initWithObject:(ObjectType)object nextNode:(Node <ObjectType> *)next;

@end

@implementation Node

+ (instancetype)nodeWithObject:(id)object {

return [Node nodeWithObject:object nextNode:nil];

}

+ (instancetype)nodeWithObject:(id)object nextNode:(Node *)next {

return [[Node alloc] initWithObject:object nextNode:next];

}

- (instancetype)initWithObject:(id)object nextNode:(Node *)next {

if (self = [super init]) {

self.object = object;

self.next = next;

}

return self;

}

- (NSString *)description {

return [NSString stringWithFormat:@"Node : %p , object : %@",self,self.object];

}

@end

@interface LinkedList ()

///head

@property (nonatomic,strong) Node *dummyHead;

///size

@property (nonatomic,assign) NSInteger size;

@end

@implementation LinkedList

- (instancetype)init

{

self = [super init];

if (self) {

self.dummyHead = [[Node alloc] init];

self.size = 0;

}

return self;

}

- (void)addObjectAtFirst:(id)object {

// Node *node = [Node nodeWithObject:object nextNode:self.head];

// self.head = node;

// self.size++;

[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;

}

prev.next = [Node nodeWithObject:object nextNode:prev.next];

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 cur.object;

}

- (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;

}

cur.object = object;

}

- (BOOL)containObject:(id)object {

Node *cur = self.dummyHead.next;

while (cur != NULL) {

if ([cur.object 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 *retNode = prev.next;

prev.next = retNode.next;

retNode.next = NULL;

return retNode.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];

cur = cur.next;

}

[string appendString:@"NULL\n"];

[string appendString:@"]\n"];

return string;

}

- (BOOL)isEmpty {

return self.count == 0;

}

- (void)dealloc

{

}

@end

当有强引用指向这个链表时候 这个链表不会被释放 ,一旦么有强引用指向这个链表,这个链表就会被立即释放,我猜测可能跟大量创建了对象 在 release 时候有关系. 

于是我用 C 语言结构体按照波波老师java 的代码 实现了链表 没有出现数据丢失 和 链表释放时候出现莫名其妙堆栈错误 还没有任何打印信息

typedef id AnyObject;

typedef struct node {

__unsafe_unretained AnyObject data;

struct node *next;

} Node;

希望波波老师能够把我上边的代码 运行下 查找下具体原因.

- (void) testArray {

NSTimer *timer = [NSTimer timerWithTimeInterval:3.0f target:self selector:@selector(test) userInfo:nil repeats:NO];

[[NSRunLoop currentRunLoop] addTimer:timer forMode:NSRunLoopCommonModes];

_timer = timer;

_timeArray = [NSMutableArray array];

}

- (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:@(i)];

}

NSLog(@"%@",linked);

CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);

CFTimeInterval duration = linkTime * 1000.0f;

NSLog(@"Linked in %f ms",duration);

// self->_linkedList = linked;

[self->_timeArray addObject:@(duration)];

count++;

});

}