//初始化时创建虚拟头结点
-(instancetype)init{
    self = [super init];
    if (self) {
        _first = [LCNode nodeWithElement:nil next:nil];
    }
    return self;
}


/// 获取index位置的node对象
/// @param index 索引
-(LCNode*)nodeForIndex:(int)index{
    [self rangeCheck:index];
    LCNode * node = _first.next;
    for (int i=0; i<index; i++) {
        node = node.next;
    }
    return node;
}

- (int)indexOf:(nonnull id)element {
    LCNode * node = _first.next;
    for (int i = 0; i<_size; i++) {
        if ([element isEqual:node.element]) {
            return i;
        }
        node = node.next;
    }
    return ELEMENT_NOT_FOUND;
}


- (void)add:(int)index element:(nonnull id)element {
    [self rangeCheckForAdd:index];
    
    //first -> headerNode -> node0 -> node1 -> node2

    //增加头结点之后，处理上更加统一，都可以拿到一个preNode
    //但额外增加了内存占用
    LCNode * preNode = index == 0?_first:[self nodeForIndex:index-1];
    preNode.next = [LCNode nodeWithElement:element next:preNode.next];
    
    _size++;
}


- (nonnull id)remove:(int)index {
   
    [self rangeCheck:index];
    
    //first -> headerNode -> node0 -> node1 -> node2
   
    LCNode * preNode = index == 0?_first:[self nodeForIndex:index-1];
    LCNode * node = preNode.next;
    preNode.next = node.next;
    
    _size--;
    
    return node.element;
}

-(NSString *)description{
    NSMutableString * des = [NSMutableString stringWithFormat:@"size=%d, [",_size];
    
    LCNode * node = _first.next;
    
    for (int i=0; i<_size; i++) {
        if (i!=0) {
            [des appendString:@", "];
        }
        
        [des appendFormat:@"%@",node];
                
        node = node.next;
    }
    [des appendString:@"]"];
    return des;
}

/// 删除index位置的元素
/// @param index 位置
-(nonnull id)remove:(int)index{
    
    [self rangeCheck:index];
    
    void* old = _elements[index];
    
    for (int i = index+1; i<_size; i++) {
        _elements[i-1] = _elements[i];
    }
        
    _elements[--_size] = NULL;
    
    [self trim];
    
    return (__bridge id)old;
}

-(void)trim{
    int oldCapacity = _capacity;
    int newCapacity = oldCapacity>>1;
    
    if (_size>newCapacity || oldCapacity<=DEFAULT_CAPACITY) {
        return;
    }
    
    int memorysize = newCapacity*sizeof(void*);
    void** newElements = malloc(memorysize);
    
     
     for (int i = 0; i < _size; i++) {
         newElements[i] = _elements[i];
     }
     
     if (_elements) {
          free(_elements);
         _elements = nil;
     }
    
     _elements = newElements;
     _capacity = newCapacity;

    NSLog(@"%d 缩容为 %d",oldCapacity,newCapacity);

}

/// 清除所有元素
-(void)clear{
    for (int i=0; i<_size; i++) {
        _elements[i] = nil;
    }
    _size = 0;
    
    if (_elements!=nil && _capacity >DEFAULT_CAPACITY) {
        int memorySize = DEFAULT_CAPACITY*sizeof(void*);
        _elements = (void**)malloc(memorySize);
    }
}