IDTMessaging Test

YDLinkedList.h

// 2. Implement a class for linked lists. At least implement methods for add and remove.

#import <Foundation/Foundation.h>

typedef struct YDLinkedListNode YDLinkedListNode;

// Helper method for handy list nodes creating
YDLinkedListNode * YDLinkedListNodeMake(id object, YDLinkedListNode *previousNode, YDLinkedListNode *nextNode);

struct YDLinkedListNode {
    __unsafe_unretained id object;
    YDLinkedListNode *previousNode;
    YDLinkedListNode *nextNode;
};

@interface YDLinkedList : NSObject

- (instancetype)init;
- (instancetype)initWithObject:(id)object;
+ (instancetype)listWithObject:(id)object;

- (id)objectAtIndex:(NSUInteger)index;
- (id)firstObject;
- (id)lastObject;

- (void)addObject:(id)object;

- (void)removeObject:(id)object;
- (void)removeAllObjects;

@end

YDLinkedList.m

#import "YDLinkedList.h"

@implementation YDLinkedList {
    NSUInteger size;
    YDLinkedListNode *firstNode;
    YDLinkedListNode *lastNode;
}

#pragma mark - Initialization

- (instancetype)init {
    if (self = [super init]) {
        size = 0;
        
        firstNode = nil;
        lastNode = nil;
    }
    return self;
}

- (instancetype)initWithObject:(id)object {
    if (self = [super init]) {
        YDLinkedListNode *node = YDLinkedListNodeMake(object, nil, nil);
        
        firstNode = node;
        lastNode = node;
        
        size = 1;
    }
    return self;
}

+ (instancetype)listWithObject:(id)object {
    return [[[self class] alloc] initWithObject:object];
}

#pragma mark - Accessor Methods

- (id)objectAtIndex:(NSUInteger)index {
    if (index > size - 1) {
        return nil;
    }
    
    YDLinkedListNode *node = nil;
    
    if (index > size / 2) {
        // we'll start looping from the end
        NSUInteger currentIndex = size - 1;
        for (node = lastNode; currentIndex > index; currentIndex--) {
            node = node->previousNode;
        }

    } else {
        // we'll start looping from the start
        NSUInteger currentIndex = 0;
        for (node = firstNode; currentIndex < index; currentIndex++) {
            node = node->nextNode;
        }
    }
    return node->object;
}

- (id)firstObject {
    if (size == 0) {
        return nil;
    }
    
    return firstNode->object;
}

- (id)lastObject {
    if (size == 0) {
        return nil;
    }
    
    return lastNode->object;
}

#pragma mark - Insertion Methods

- (void)addObject:(id)object {
    YDLinkedListNode *newNode = YDLinkedListNodeMake(object, nil, lastNode);
    if (size == 0) {
        firstNode = newNode;
        lastNode = newNode;
    } else {
        lastNode->nextNode = newNode;
        lastNode = newNode;
    }
    size++;
}

#pragma mark - Public Removal Methods

- (void)removeObject:(id)object {
    YDLinkedListNode *node;
    
    for (node = firstNode; node; node = node->nextNode) {
        if ([node->object isEqual:object]) {
            [self removeNode:node];
        }
    }
}

- (void)removeAllObjects {
    YDLinkedListNode *node;
    
    for (node = firstNode; node; node = node->nextNode) {
        [self removeNode:node];
    }
}

#pragma mark - Private Removal Methods

- (void)removeNode:(YDLinkedListNode *)node {
    if (size == 0) {
        return;
    } else if (size == 1) {
        firstNode = nil;
        lastNode = nil;
    } else if (node->nextNode == nil) {
        [self removeLastNode];
    } else if (node->previousNode == nil) {
        [self removeFirstNode];
    } else {
        YDLinkedListNode *tempNode = node->previousNode;
        tempNode->nextNode = node->nextNode;
        tempNode = node->nextNode;
        tempNode->previousNode = node->previousNode;
    }
    
    node->object = nil;
    free(node);
    size--;
}

- (void)removeLastNode {
    lastNode = lastNode->previousNode;
    lastNode->nextNode = nil;
}

- (void)removeFirstNode {
    firstNode = firstNode->nextNode;
    firstNode->previousNode = nil;
}

@end

#pragma mark - Helper Methods

YDLinkedListNode * YDLinkedListNodeMake(id object, YDLinkedListNode *previousNode, YDLinkedListNode *nextNode) {
    YDLinkedListNode *node = malloc(sizeof(YDLinkedListNode));
    node->nextNode = nextNode;
    node->previousNode = previousNode;
    node->object = object;
    return node;
};