//
//  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"

@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

测试代码 :

- (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++;
	});
	
}


当链表添加元素个人超过800时候 发现打印链表时候数据有丢失 比如添加1...800  打印只有100...800 ,前边的0-99 数据不见了. 当添加超过800个元素时候 会出现内存释放问题 ,我的猜测时当没有强引用指向这个链表时候 ,同时对大量的对象 release 时候出错了.  

由于实在找不到原因,只能是猜测链表内部节点在释放内存时候出了问题. 于是我将链表内部的 Node 由对象改成 C 语言 结构体

typedef id AnyObject;

typedef struct node {
	__unsafe_unretained AnyObject data;
	struct node *next;
} Node; 

改进后的链表内存释放改为手动释放内存,没有发现节点数据丢失和内存释放的问题.
希望波波老师有时间把我上边 Objective-C 实现的链表代码 运行下, 可能 Java 是自动管理内存吧,在学习动态数组时候 没有见波波老师释放过内存,我自己写的动态数组 也是用的 C 语言数组,然后手动管理存入数组的对象内存引用计数.