Objective-C写的链表会出现坏内存访问
看了波波老师讲的链表,自己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++;
});
}
正在回答 回答被采纳积分+3
1回答
相似问题
登录后可查看更多问答，登录/注册
