Custom linked list class

Question

I put together a Custom Linked List class in hopes of using it for a Talent/Skill Tree for a game. It allows for inserting nodes with NSMutableDictionary for Skills and Requirements along with a nodeID and a Boolean to see if said node is activated or not.

I would like some feedback on this and any comments/ideas (all criticism welcome) so I can expand on the idea.

The class is located at Github

//
//  JBList.h
//
//
//  Created by Julius Btesh on 8/28/13.
//
//

#import <Foundation/Foundation.h>
#import "JBListNode.h"


@interface JBList : NSObject

@property (nonatomic) JBListNode *head; // This always points to the first position of the list
@property (nonatomic) JBListNode *tail; // Always points to the last position
@property (nonatomic) JBListNode *currTop;
@property (nonatomic) JBListNode *currBottom;
@property (nonatomic) int count;

- (void)pushFront:(NSMutableDictionary *)skills;
- (void)pushBack:(NSMutableDictionary *)skills;

- (void)pushFront:(NSMutableDictionary *)skills withRequirements:(NSMutableDictionary *)requirements;
- (void)pushBack:(NSMutableDictionary *)skills withRequirements:(NSMutableDictionary *)requirements;
- (NSMutableDictionary *)popFront;
- (NSMutableDictionary *)popBack;
- (NSMutableDictionary *)popNode:(NSInteger)node;

/* Will not work if you have multiple Skill Dictionaries with the same Keys + Values!!!!!
    Will find the FIRST nodeID with said Skill!!!!! 
*/
- (NSInteger)findNodeIDForSkills:(NSMutableDictionary *)skills;
/* Used for better search precision incase you have multiple Skill Dictionaries but different Requirement Dictionaries!!!
    But same as above, if there are multiple Skill AND Requirement Dictionaries with the same Keys + Values
    it will find the FIRST nodeID with said Skill AND Requirement!!! 
*/
- (NSInteger)findNodeIDForSkills:(NSMutableDictionary *)skills andRequirements:(NSMutableDictionary *)requirements;

- (void)activateNode:(NSInteger)node;
- (void)deactivateNode:(NSInteger)node;
- (BOOL)isActivated:(NSInteger)node;

- (void)setRequirements:(NSMutableDictionary *)requirements forNode:(NSInteger)node;
- (void)editRequirementsAtNode:(NSInteger)node setValue:(id)value forKey:(NSString *)key;
- (NSMutableDictionary *)findRequirements:(NSMutableDictionary *)requirements forNode:(NSInteger)node;

- (NSMutableDictionary *)findSkillsForNode:(NSInteger)node;
- (void)editSkillsAtNode:(NSInteger)node setValue:(id)value forKey:(NSString *)key;
- (void)allNodes;


@end



//
//  JBList.m
//
//
//  Created by Julius Btesh on 8/28/13.
//
//

#import "JBList.h"

@implementation JBList {
    JBListNode *_head;
    JBListNode *_tail;
    JBListNode *_currTop;
    JBListNode *_currBottom;
    int _count;
    int nodeID;
}

- (id)init {
    if (self = [super init]) {
        _head = nil;
        _tail = nil;
        _count = 0;
    }
    return self;
}

- (void)dealloc {
    int i = 0;
    JBListNode *tmp;
    while (i < _count){
        tmp = _head;
        _head = _head.next;
        tmp = nil;
    }
}

- (void)pushFront:(NSMutableDictionary *)skills {
    JBListNode *newElement = [[JBListNode alloc] init];
    newElement.skills = skills;
    if ( _count == 0 ){
        newElement.next = nil; //Set both the head and tail to NULL
        newElement.previous = nil;
        newElement.nodeID = 1;
        _count = 1;
        _head = newElement;
        _tail = newElement;
        _currTop = newElement;
        _currBottom = newElement;
        return; //Since there is only one element, quit
    }
    nodeID += 1;
    JBListNode *tmp = _head;
    newElement.next = tmp; //The new guys next is currently pointing to the bottom most element
    newElement.previous = tmp.previous; //Now, whatever the bottom was pointing to (the tail) the new node is pointing to.
    newElement.nodeID += 1;
    _currBottom = newElement; //The new node is now the bottom most element
    tmp.previous = newElement; //Now the former bottom is pointing to the new bottom
    _head = newElement; //The head is the bottom most element
    _count += 1;
}

- (void)pushBack:(NSMutableDictionary *)skills {
    JBListNode *newElement = [[JBListNode alloc] init];
    newElement.skills = skills;
    if ( _count == 0 ) {
        newElement.next = nil;
        newElement.previous = nil;
        newElement.nodeID = 1;
        nodeID = 1;
        _count = 1;
        _head = newElement;
        _tail = newElement;
        _currTop = newElement;
        _currBottom = newElement;
        return; //Since there is only one element, quit
    }
    nodeID += 1;
    JBListNode *tmp = _tail;
    newElement.previous = tmp; // The new node is pointing to the last element added
    newElement.next = tmp.next; // What ever the current top was pointing to, now the new node is pointing to it
    newElement.nodeID = nodeID;
    _currTop = newElement; // Top most element
    tmp.next = newElement; // Now the former top node is pointing to the new node
    _tail = newElement; // The tail is the top element
    _count += 1;
}

- (void)pushFront:(NSMutableDictionary *)skills withRequirements:(NSMutableDictionary *)requirements {
    JBListNode *newElement = [[JBListNode alloc] init];
    newElement.skills = skills;
    newElement.requirements = requirements;
    if ( _count == 0 ){
        newElement.next = nil; //Set both the head and tail to NULL
        newElement.previous = nil;
        newElement.nodeID = 1;
        nodeID = 1;
        _count = 1;
        _head = newElement;
        _tail = newElement;
        _currTop = newElement;
        _currBottom = newElement;
        return; //Since there is only one element, quit
    }
    nodeID += 1;
    JBListNode *tmp = _head;
    newElement.next = tmp; //The new guys next is currently pointing to the bottom most element
    newElement.previous = tmp.previous; //Now, whatever the bottom was pointing to (the tail) the new node is pointing to.
    newElement.nodeID = nodeID;
    _currBottom = newElement; //The new node is now the bottom most element
    tmp.previous = newElement; //Now the former bottom is pointing to the new bottom
    _head = newElement; //The head is the bottom most element
    _count += 1;
}

- (void)pushBack:(NSMutableDictionary *)skills withRequirements:(NSMutableDictionary *)requirements {
    JBListNode *newElement = [[JBListNode alloc] init];
    newElement.skills = skills;
    newElement.requirements = requirements;
    if ( _count == 0 ) {
        newElement.next = nil;
        newElement.previous = nil;
        newElement.nodeID = 1;
        nodeID = 1;
        _count = 1;
        _head = newElement;
        _tail = newElement;
        _currTop = newElement;
        _currBottom = newElement;
        return; //Since there is only one element, quit
    }
    nodeID += 1;
    JBListNode *tmp = _tail;
    newElement.previous = tmp; // The new node is pointing to the last element added
    newElement.next = tmp.next; // What ever the current top was pointing to, now the new node is pointing to it
    newElement.nodeID = nodeID;
    _currTop = newElement; // Top most element
    tmp.next = newElement; // Now the former top node is pointing to the new node
    _tail = newElement; // The tail is the top element
    _count += 1;
}

- (NSMutableDictionary *)popFront {
    if (_count == 0){//Empty!
        NSLog(@"Empty!");
        return 0;
    }
    if (_count - 1 == 0) //If count will equal 0, there is 1 element in the list
    {
        NSMutableDictionary *value = _currBottom.skills; //hold the data, so i can delete the bottom
        _currBottom = nil; //delete the last element
        _count = 0;
        _head = nil; //head and tail are pointing to NULL
        _tail = nil;
        return value;
    }

    NSMutableDictionary *value = _currBottom.skills;
    JBListNode *tmp = _head;
    JBListNode *tmp2 = tmp.next;
    JBListNode *tmp3 = _tail;
    tmp2.previous = nil;
    tmp3.next = nil;
    _head = tmp2;
    _currBottom = tmp2;
    tmp = nil;
    _count -= 1;
    return value;
}

- (NSMutableDictionary *)popBack {
    if (_count == 0){//Empty!
        NSLog(@"Empty!");
        return 0;
    }
    if (_count - 1 == 0) //If count will equal 0, there is 1 element in the list
    {
        NSMutableDictionary *value = _currTop.skills; //hold the data, so i can delete the tmp
        _currTop = nil; //delete the last element
        _count = 0;
        _head = nil; //head and tail are pointing to NULL
        _tail = nil;
        return value;
    }

    NSMutableDictionary *value = _currTop.skills;
    JBListNode *tmp = _tail;
    JBListNode *tmp2 = tmp.previous;
    JBListNode *tmp3 = _head;
    tmp2.next = nil;
    tmp3.previous = nil;
    _tail = tmp2;
    _currTop = tmp2;
    tmp = nil;
    _count -= 1;
    return value;
}

- (NSMutableDictionary *)popNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    if (node == 1) //If count will equal 0, there is 1 element in the list
    {
        NSMutableDictionary *value = tmp.skills; //hold the data, so i can delete the tmp
        _head = tmp.next;
        _currBottom = tmp.next;
        _count -= 1;
        return value;
    }
    if (node == nodeID) {
        NSMutableDictionary *value = tmp.skills;
        JBListNode *tmp2 = tmp.previous;
        tmp2.next = nil;
        _tail = tmp2;
        _currTop = tmp2;
        tmp = nil;
        _count -= 1;
        return value;
    }

    NSMutableDictionary *value = tmp.skills;
    JBListNode *tmp2 = tmp.previous;
    JBListNode *tmp3 = tmp.next;
    tmp2.next = tmp3;
    tmp3.previous = tmp2;
    tmp = nil;
    _count -= 1;
    return value;

}

- (NSMutableDictionary *)findSkillsForNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    return tmp.skills;
}

- (void)editSkillsAtNode:(NSInteger)node setValue:(id)value forKey:(NSString *)key {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    [tmp.skills setValue:value forKey:key];
}

- (void)activateNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    tmp.activated = YES;
}

- (void)deactivateNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    tmp.activated = YES;
}

- (BOOL)isActivated:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    return tmp.activated;
}

- (void)setRequirements:(NSMutableDictionary *)requirements forNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    tmp.requirements = requirements;
}

- (void)editRequirementsAtNode:(NSInteger)node setValue:(id)value forKey:(NSString *)key {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    [tmp.requirements setValue:value forKey:key];
}

- (NSMutableDictionary *)findRequirements:(NSMutableDictionary *)requirements forNode:(NSInteger)node {
    JBListNode *tmp = _head;
    while (tmp.nodeID != node) {
        tmp = tmp.next;
    }
    return tmp.requirements;
}

- (NSInteger)findNodeIDForSkills:(NSMutableDictionary *)skills {
    JBListNode *tmp = _head;
    while (tmp.skills != skills) {
        tmp = tmp.next;
    }
    return tmp.nodeID;
}

- (NSInteger)findNodeIDForSkills:(NSMutableDictionary *)skills andRequirements:(NSMutableDictionary *)requirements {
    JBListNode *tmp = _head;
    while (tmp.skills != skills || tmp.requirements != requirements) {
        tmp = tmp.next;
    }
    return tmp.nodeID;
}

- (void)allNodes {
    JBListNode* tmp = _head;
    while (tmp != nil){
        NSLog(@"NodeID: %d", tmp.nodeID);
        NSLog(@"Skill: %@", tmp.skills);
        NSLog(@"Requirements: %@", tmp.requirements);
        NSLog(@"Activated: %d", tmp.activated);
        tmp = tmp.next;
    }
}

@end


//
//  JBListNode.h
//  
//
//  Created by Julius Btesh on 8/28/13.
//
//

#import <Foundation/Foundation.h>

@interface JBListNode : NSObject


@property (nonatomic) JBListNode *next;
@property (nonatomic) JBListNode *previous;

@property (nonatomic) NSInteger nodeID;
@property (nonatomic) NSMutableDictionary *skills;
@property (nonatomic) NSMutableDictionary *requirements;
@property (nonatomic) BOOL activated;



@end





//
//  JBListNode.m
//  
//
//  Created by Julius Btesh on 8/28/13.
//
//

#import "JBListNode.h"

@implementation JBListNode {
    JBListNode *_next;
    JBListNode *_previous;

    NSInteger _nodeID;
    NSMutableDictionary *_skills;
    NSMutableDictionary *_requirements;
    BOOL _activated;
}


- (id)init {
    if (self = [super init]) {
        _next = nil;
        _previous = nil;
        _activated = NO;
    }
    return self;
}

@end

Answer 1

First, it should be noted that an NSDictionary can use any object as it's key (as long as it conforms to NSCopying protocol), as such, your setValue:forKey: methods should probably be rewritten to take id as the key argument type, rather than NSString*.

---

Second, while the structure of your binary search tree is important for somethings, the structure is not important to some of your search methods. For example, in findNodeIDForSkills:andRequirements:, all that's important is that the skills and requirements match the arguments and we return the nodeID for the matching node (this can probably also be true for some of the other searches). As such, if we keep a private NSMutableArray that simply holds a reference to all of the nodes, we can use a forin loop to drastically increase the performance of the searches. Forin loops are quite fast.

---

Third, regardless of whether or not you implement my second suggestion, your searches still have a problem in the case that the arguments sent do not match any of the nodes.

In fact, if I'm correct, all of your searches will result in infinite loops if the search criteria cannot be met. They all have this pattern:

while (someCriteria) {
    tmp = tmp.next;
}

When you get to the end of the list, tmp.next will be nil. This assigns nil to tmp, and your criteria will still return true. Because tmp is nil, then tmp.next will still return nil, and at this point your criteria will always be true and the loop will never exit. You need to add something like this:

while (someCriteria) {
    tmp = tmp.next;
    if(!tmp) {
        return nil;
    }
}

Now we're returning some sort of value that indicates nothing was found and users of the class can check whether they got a good value returned or just nil, indicating their search turned up nothing.

---

Fourth, this one is just an Objective-C naming convention note.

and is typically reserved to describe an additional action taken place within the method. This isn't what is happening with your findNodeIDForSkills:andRequirements: method, and as such, the and should be taken out:

- (NSInteger)findNodeIDforSkills:(NSMutableDictionary *)skills 
                    requirements:(NSMutableDictionary *)requirements

An example where the and might be more appropriate would look something more like this:

- (NSInteger)findNodeIDforSkills:(NSMutableDictionary*)skills
             andEditRequirements:(id)value
                          forKey:(id)key

Where we're going to search through the nodes to find a matching skills dictionary, edit the requirements of the dictionary AND return the node ID for the dictionary we just found and edited. We are FINDING and EDITING. Whereas in your current use of the and, you're just finding by two criteria.