LinkedList.m

@import Foundation;

NS_ASSUME_NONNULL_BEGIN

@interface Node <T>: NSObject
@property (nonatomic, strong, readonly) T value;
@property(nonatomic, strong, readonly) Node<T> *next;

- (instancetype)initWithValue:(T)value next:(nullable Node<T> *)next;

@end

@interface LinkedList <__covariant T>: NSObject

@property (nonatomic, readonly) NSInteger length;
@property (nonatomic, readonly) Node<T> *head;

- (instancetype)initWithValue:(T)value;
+ (instancetype)linkedListWithValue:(T)value;
- (instancetype)appendWithValue:(T)value;
- (instancetype)prependWithValue:(T)value;
- (NSInteger)length;
- (instancetype)sublistWithRange:(NSRange)range;
- (instancetype)removeFirstElement;
- (instancetype)removeLastElement;



@end

NS_ASSUME_NONNULL_END

@implementation Node

- (instancetype)initWithValue:(id)value next:(Node *)next {
    self = [super init];
    _value = value;
    _next = next;
    return self;
}

- (instancetype)appendWithValue:(id)value {
    if (!self.next) {
        Node *node = [[Node alloc] initWithValue:value next:nil];
        return [[Node alloc] initWithValue:_value next:node];
    }
    return [[Node alloc] initWithValue:_value
                                  next:[self.next appendWithValue:value]];
}

- (instancetype)prependWithValue:(id)value {
    if (!self.next) {
        return [[Node alloc]
            initWithValue:value
                     next:[[Node alloc] initWithValue:_value next:nil]];
    }
    return [[Node alloc] initWithValue:value
                                  next:[self.next prependWithValue:_value]];
}

- (instancetype)removeFirstElement {
    return [self.next copy];
}

- (instancetype)removeLastElement {
    if (!self.next) {
        return nil;
    } else if (!self.next.next) {
        return [[Node alloc] initWithValue:_value next:nil];
    }
    return
        [[Node alloc] initWithValue:_value next:[self.next removeLastElement]];
}

- (instancetype)copyNext:(NSInteger)remainingCount {
    if (remainingCount == 0) {
        return nil;
    }

    return [[Node alloc] initWithValue:_value
                                  next:[self.next copyNext:remainingCount - 1]];
}

- (instancetype)copyWithZone:(NSZone *)zone {
    if (!self.next) {
        return [[Node alloc] initWithValue:_value next:nil];
    }

    return
        [[Node alloc] initWithValue:_value next:[self.next copyWithZone:zone]];
}

- (instancetype)sublistWithRange:(NSRange)range {
    if (range.location == 0) {
        return [self copyNext:range.length];
    }
    return [self.next
        sublistWithRange:NSMakeRange(range.location - 1, range.length)];
}

- (NSString *)description {
    if (!self.next) {
        return [self.value description];
    }
    return [NSString
        stringWithFormat:@"%@ -> %@", self.value, [self.next description]];
}

@end

@implementation LinkedList

+ (instancetype)linkedListWithValue:(id)value {
    return [[self alloc] initWithValue:value];
}

- (instancetype)initWithValue:(id)value {
    self = [super init];
    _head = [[Node alloc] initWithValue:value next:nil];
    _length = 1;
    return self;
}

- (instancetype)initWithHead:(Node *)node length:(NSInteger)length {
    self = [super init];
    _head = node;
    _length = length;
    return self;
}

- (instancetype)appendWithValue:(id)value {
    return [[[self class] alloc] initWithHead:[self.head appendWithValue:value]
                                       length:_length + 1];
}

- (instancetype)prependWithValue:(id)value {
    return [[[self class] alloc] initWithHead:[self.head prependWithValue:value]
                                       length:_length + 1];
}

- (instancetype)sublistWithRange:(NSRange)range {

    NSInteger length = length - range.location;
    length = length > 0 ? length : 0;
    length = length > range.length ? range.length : length;

    return [[[self class] alloc] initWithHead:[self.head sublistWithRange:range]
                                       length:length];
}

- (instancetype)removeLastElement {
    NSInteger length = length == 0 ? 0 : length - 1;
    return [[[self class] alloc] initWithHead:[self.head removeFirstElement]
                                       length:length];
}

- (instancetype)removeFirstElement {
    NSInteger length = length == 0 ? 0 : length - 1;
    return [[[self class] alloc] initWithHead:[self.head removeLastElement]
                                       length:length];
}

@end