current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 13 down vote favorite
1

CKLinkedList is the implementation of a doubly linked list. I'd like to see comments on the memory management (I'm using ARC in the code below) and formatting + overall style.

CKList protocol file:

//
//  CKList.h
//  CollectionsKit
//
//  Created by Igor Rastvorov on 11/30/14.
//  Copyright (c) 2014 Igor Rastvorov. All rights reserved.
//

#import <Foundation/Foundation.h>
#import "CKCollection.h"
#import "CKQueue.h"

/**
 `CKList` is a formal protocol for all the adopters that represent a heterogenous list of objects.
 */
@protocol CKList <CKCollection, CKQueue>

@property(nonatomic, assign, readonly) NSUInteger size;

/// --------------------------------
/// @name Adding objects to the list
/// --------------------------------

/**
 Adds object to the head of the list.
 @param object An object to add to head.
 */
-(void) addObjectToHead:(id) object;

/// -----------------------------------
/// @name Getting objects from the list
/// -----------------------------------

/**
 Retrieves object at the tail of the list.
 @throws `NSRangeException` if the list is empty.
 */
-(id) objectAtTail;

/**
 Retrieves object at the specified position in the list.
 @param index Specifies the position to remove object from.
 @throws `NSRangeException` if the list is empty.
 */
-(id) objectAtIndex:(NSUInteger) index;

/// ------------------------------------
/// @name Removing objects from the list
/// ------------------------------------

/**
 Removes object from the head.

 @throws `NSRangeException` if the list is empty.
 */
-(void) removeObjectFromHead;

/**
 Removes object from the tail.

 @throws `NSRangeException` if the list is empty.
 */
-(void) removeObjectFromTail;

/**
 Removes object from the specified position in the list.

 @param index Specifies the position to remove object from.
 @throws `NSRangeException` if the list is empty.
 */
-(void) removeObjectAtIndex:(NSUInteger) index;

/**
 Constructs a new list within a range of the original list.

 @param range Range of objects within the original list. Objects within the specified range will be added to a sublist.
 */
-(id <CKList>) sublistWithRange:(NSRange) range;

/**
 Finds and returns an index of the first occurence of the specified object.

 @param object Object first occurence of which is to be found.
 */
-(NSUInteger) indexOfObject:(id) object;

/**
 Finds and returns an index of the last occurence of the specified object.

 @param object Object last occurence of which is to be found.
 */
-(NSUInteger) lastIndexOfObject:(id) object;

@end

CKLinkedList.h file:

//
//  CKLinkedList.h
//  CKLinkedList
//
//  Created by Igor Rastvorov on 11/27/14.
//  Copyright (c) 2014 Igor Rastvorov. All rights reserved.
//  ARC compatibe.

#import <Foundation/Foundation.h>
#include "CKList.h"

@class CKListNode;

/**
 Represents a linked list of objects.
 */
@interface CKLinkedList : NSObject <CKList> {
    CKListNode *_head;
    CKListNode *_tail;
}

@end

CKLinkedList.m file:

//
//  CKLinkedList.m
//  CKLinkedList
//
//  Created by Igor Rastvorov on 11/27/14.
//  Copyright (c) 2014 Igor Rastvorov. All rights reserved.

#import "CKLinkedList.h"

/**
 Represents a single node in a doubly linked list.
 */
@interface CKListNode : NSObject

@property(nonatomic, strong) CKListNode *next;
@property(nonatomic, strong) CKListNode *previous;
@property(nonatomic, strong) id data;

-(id) initWithData:(id) data;
-(BOOL) isEqual:(id)object;

@end

@implementation CKListNode

@synthesize next = _next;
@synthesize data = _data;

-(id) initWithData:(id)data {
    self = [super init];
    if (self) {
        [self setData:data];
    }

    return self;
}
-(BOOL) isEqual:(id)object {
    if (object != nil && [object isKindOfClass:[CKListNode class]]) {
        return [[self data] isEqual:[object data]];
    }

    return NO;
}
-(NSString *) description {
    return [[self data] description];
}

@end

@interface CKLinkedList ()

@property(nonatomic, readwrite) NSUInteger size;

-(CKListNode *) listNodeAtIndex:(NSUInteger) index;
-(void) removeNodeAtIndex:(NSUInteger) index;
@end

@implementation CKLinkedList

@synthesize size = _size;

#pragma mark - Initializing

-(instancetype) init {
    return [self initWithArray: nil];
}

-(id) initWithArray:(NSArray *)array {
    self = [super init];
    if (self) {
        if (array != nil) {
            for (id object in array) {
                [self addObjectToTail:object];
            }
        }
    }

    return self;
}

#pragma mark - Adding objects

-(void) addObjectToHead:(id)object {
    CKListNode *listNode = [[CKListNode alloc] initWithData:object];

    listNode.data = object;
    listNode.previous = nil;
    listNode.next = _head;
    _head.previous = listNode;

    _head = listNode;

    if ([self isEmpty]) {
        _tail = _head;
    }

    ++self.size;
}

#pragma mark - CKQueue

-(void) addObjectToTail:(id)object {
    CKListNode *listNode = [[CKListNode alloc] initWithData:object];

    if ([self isEmpty]) {
        _head = listNode;
        _tail = _head;

        listNode.previous = nil;
    } else {
        listNode.previous = _tail;
    }

    listNode.next = nil;
    listNode.data = object;

    _tail.next = listNode;
    _tail = listNode;

    ++self.size;
}

#pragma mark - Retrieving objects

-(id) objectAtTail {
    return [_tail data];
}
-(id) objectAtIndex:(NSUInteger) index {
    return [[self listNodeAtIndex:index] data];
}

-(id <CKList>) sublistWithRange:(NSRange) range {
    id <CKList> sublist = [[CKLinkedList alloc] init];

    NSUInteger endIndex = range.location + range.length;
    for (NSUInteger startIndex = range.location; startIndex <= endIndex; ++startIndex) {
        CKListNode *currentNode = [self listNodeAtIndex:startIndex];
        [sublist addObjectToTail: currentNode];
    }

    return sublist;
}

-(NSUInteger) indexOfObject:(id) object {
    NSUInteger size = [self size];
    for (NSUInteger index = 0; index <= size; ++index) {
        if ([[self objectAtIndex:index] isEqual:object]) {
            return index;
        }
    }

    return NSNotFound;
}

-(NSUInteger) lastIndexOfObject:(id) object {
    for (NSUInteger index = [self size] - 1; index != 0; --index) {
        if ([[self objectAtIndex:index] isEqual:object]) {
            return index;
        }
    }

    return NSNotFound;
}

#pragma mark - CKQueue
-(id) objectAtHead {
    return [_head data];
}

#pragma mark - Removing objects

-(void) removeObjectFromTail {
    [self removeObjectAtIndex: [self size] - 1];
}
-(void) removeObjectAtIndex:(NSUInteger) index {
    [self removeNodeAtIndex:index];
    --self.size;
}

#pragma mark - CKQueue
-(void) removeObjectFromHead {
    [self removeObjectAtIndex:0];
}

#pragma mark - CKCollection

-(void) clear {
    for (NSUInteger listNodeIndex = 0; listNodeIndex < [self size]; ++listNodeIndex) {
        [self removeObjectFromHead];
    }
}

#pragma mark - List state

#pragma mark - CKCollection

-(BOOL) containsObject:(id) object {
    NSUInteger size = [self size];
    for (NSUInteger i = 0; i < size; ++i) {
        if ([[self objectAtIndex:i] isEqual:object]) {
            return YES;
        }
    }

    return NO;
}

-(NSString *) description {
    if ([self isEmpty]) {
        return @"(empty)";
    }

    NSString *contents = [NSMutableString stringWithString:@"(\n"];

    NSUInteger listNodeIndex;
    for (listNodeIndex = 0; listNodeIndex < [self size] - 1; ++listNodeIndex) {

        contents = [contents stringByAppendingString:[NSString stringWithFormat:@"\t%@,\n", [self listNodeAtIndex:listNodeIndex]]];
    }
    contents = [contents stringByAppendingString:[NSString stringWithFormat:@"\t%@\n)", [self listNodeAtIndex:listNodeIndex]]];

    return contents;
}

-(BOOL) isEmpty {
    return ([self size] == 0);
}

-(BOOL) isEqual:(id) object {
    if (object != nil && [object isKindOfClass:[CKLinkedList class]]) {
        if ([self size] != [object size]) {
            return NO;
        }

        CKListNode *listNode = nil;
        CKListNode *comparedListNode = nil;

        for (NSUInteger listNodeIndex = 0; listNodeIndex < [self size]; ++listNodeIndex) {
            listNode = [self listNodeAtIndex:listNodeIndex];
            comparedListNode = [object listNodeAtIndex:listNodeIndex];

            if (![listNode isEqual:comparedListNode]) {
                return NO;
            }
        }
    }

    return YES;
}

-(NSUInteger) hash {
    if ([self isEmpty]) {
        return [super hash];
    }

    NSUInteger hashCode = [[self objectAtIndex:0] hash];;
    for (NSUInteger i = 1; i < [self size]; ++i) {
        hashCode ^= [[self objectAtIndex:i] hash];
    }

    return hashCode;
}

-(NSArray *) toArray {
    NSMutableArray *array = [NSMutableArray arrayWithCapacity:[self size]];

    for (NSUInteger index = 0; index < [self size]; ++index) {
        [array addObject:[self objectAtIndex:index]];
    }

    return array;
}

// ---------------------------------
// Private interface
// ---------------------------------

-(CKListNode *) listNodeAtIndex:(NSUInteger) index {
    if (index >= [self size] ) {
        return nil;
    }

    CKListNode *listNode = _head;
    for (NSUInteger listNodeIndex = 0; listNodeIndex < index; ++listNodeIndex) {
        listNode = [listNode next];
    }

    return listNode;
}

-(void) removeNodeAtIndex:(NSUInteger) index {
    CKListNode *deallocationTarget = [self listNodeAtIndex:index];

    if (deallocationTarget == nil) {
        return;
    }

    if (deallocationTarget == _head) {
        _head = deallocationTarget.next;
    } else if (deallocationTarget == _tail) {
        _tail = deallocationTarget.previous;
    } else {
        deallocationTarget.previous.next = deallocationTarget.next;
        deallocationTarget.next.previous = deallocationTarget.previous;
    }

    deallocationTarget = nil;
}

@end

For reference, here is the code on GitHub.

share|improve this question

2 Answers 2

up vote 6 down vote

@bazola's answer hits on some points I would otherwise make, so be sure to stop by there.

Meanwhile, in this answer...

First of all, I don't particularly like objectAtTail or objectAtHead as method names. I think that as a general guideline, we can make our linked list work very similarly to NSArray. As for a start, we should replace objectAt... with firstObject and lastObject.

And more importantly, rather than throwing an exception, our method should just return nil when the list is empty. The documentation pointing out that an exception can be thrown is nice, but here I don't think throwing the exception is appropriate. And Apple wouldn't think so either, otherwise, they'd have firstObject and lastObject throw exceptions instead of returning nil.

Your size property is missing documentation. Is this the memory size the entire list takes up? Or is it the count of the objects in the list? If the latter, we should rename it to count, and the property shouldn't miss out on the detail documentation the rest of the class gets.

isEqual methods should basically always be optimized with the following:

-(BOOL) isEqual:(id)object {
    if (self == object) return true;
    // additional logic to determine if they are the same
}

What this does is starts with a check to see if self and object are pointers to the same object. If our pointers hold the same value, it's impossible for us to be unequal--we're the exact same objects.

-(NSString *) description {
    return [[self data] description];
}

This can lead to some really misleading debugging. We need to wrap our data's description in a string that indicates the object is in the list.

- (NSString *)description {
    return [NSString stringWithFormat:@"[<CKListNode:%p>: %@]", self, self.data];
}

Our toArray method is documented as returning an immutable array but actually returns a mutable array. Moreover, I think I'd like the method name better if it were arrayValue or arrayRepresentation.

But the return should look like this:

return [NSArray arrayWithArray:array];

Our clear method should be named more similarly to what we'd expect from other Objective-C collections. In this case, removeAllObjects.

You list several things as throwing exceptions, but I can't actually figure out where any exceptions are thrown.

It looks like eventually anything accessing an index calls back to this method:

 -(CKListNode *) listNodeAtIndex:(NSUInteger) index {
    if (index >= [self size] ) {
        return nil;
    }

    // stuff...
}

All you do is return nil;, which doesn't throw an exception. Instead of returning nil, here is one of the few places we actually ought to throw an Objective-C exception:

NSString *reason = [NSString stringWithFormat:@"Index: %i is outside the range (0,%i)", index, (self.size - 1)];

@throw([NSException exceptionWithName:@"NSRangeException"
                               reason:reason
                             userInfo:nil]);

Our CKListNode object shouldn't have a data property or an initWithData: method. Data means an NSData object or subclass. It is a representation of raw data... bytes. This isn't what our nodes carry around. They carry objects. So, we can use Objective-C terminology and initWithObject: as well as naming the property object, or we can use what I've seen in other linked lists and use payload as the property name an initWithPayload: as the method name. I think I prefer object between the two.

share|improve this answer
up vote 4 down vote

You use the appropriate terms for the head and tail of the linked list, and the implementation seems correct. I can't really comment on the specifics of the implementation but the header is easy to understand and it looks easy to use.

Your comments are good and explain the big picture stuff concisely. I think they help the overall understanding of the code, which is a very good thing.

I have some comments about some specific parts of the code.

@synthesize next = _next;
@synthesize data = _data;

For modern Objective-C, you don't have to actually synthesize the properties. This is handled automatically.

[self setData:data];

It is considered bad practice to access methods using self inside of the init method. The reason is that it is possible that self is not fully initialized. Sometimes it still feels necessary to do so, but I do not see any matching setData: method in the implementation. I would just access the value directly like this:

_data = data;

You have a similar thing going on here in another init method:

for (id object in array) {
    [self addObjectToTail:object];
}

This one is a bit more difficult to deal with, as addObjectToTail is something specialized that you need to work in a particular way. I would say that it is sometimes alright to access self in this way, but it is definitely not recommended. Sometimes as a workaround I will break things out to a C function that is called from the init method, but this approach has the possibility of making the code harder to read and understand.

-(id) objectAtTail {
    return [_tail data];
}

I am a bit confused why you don't do return _tail.data; since it is a property. If you are going to use properties, you may as well use the dot accessors for them. Otherwise you could make them private and provide the accessor methods manually.

Other than these minor points, everything looks good!

share|improve this answer
1  
Even if you made it private and manually implement the accessors, you could still call _tail.data. Ultimately, we prefer using _tail.data because the syntax is better. –  nhgrif Dec 22 '14 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.