No programming language discussion would be complete without examining
recursive data structures such as trees and linked lists.
The focus here is to implement basic linked list operations that have no
side-effect.
This is common behavior in functional languages such as Scheme, Lisp,
Haskell and ML.
The implementation uses deep copy rather than assignment
operations.
For example, for:
list = (1, 2, 3)
[list tail]
returns: (2,3)
with no side-effect: list = (1, 2, 3)
[list head]
returns: 1
with no side-effect: list = (1, 2, 3)
The linked list operations only return a copy, the receiver linked list
is not side-effected.
An example is a simple LinkedList implementation with
five external operations:
- +initWithObject: object is a class constructor,
returning a LinkedList object
initialized with one object entry.
- -dealloc the LinkedList.
- -head returns the object at the head of the LinkedList.
-
-tail returns a semi-deep copy of the tail of the
LinkedList.
-
-cons: object constructs a LinkedList with
object at the head.
The -dealloc operation obviously side-effect the
receiver by deallocating memory.
The final three create copies, with any appropriate
modifications applied to the copy.
For example:
-head returns a reference to a copy of the object
at the head of the list.
-tail returns a reference to a copy of the linked
list object following the head.
-cons: object returns a reference to a copy of
the receiver linked list object with a copy of the object at its head.
The key helper method, -copy, copies a linked list to a
new linked list by iterating through and copying the existing set of ListNode objects.
To create, newList, a copy of
linkedList:
newList = [ linkedList copy ];
- (LinkedList *) copy {
ListNode *n = self.first;
ListNode *l = [n copy];
LinkedList *t = [[LinkedList alloc] init];
t.first = l;
do {
n = n.next;
l.next = [n copy];
l = l.next;
} while( n != nil );
return t;
}
|
Note also that all linked lists created by -cons, -tail and +initWithObject:
are autoreleased on return, managing their own memory allocation and
eventually calling the -dealloc method. This follows the memory
management rule that whoever allocates the object must deallocate the
object.
-copy allocates memory and returns a reference without
autoreleasing, however this follows the memory manage rule that the
caller of a copy operation is responsible for releasing any memory.
#import <Foundation/Foundation.h>
@interface ListNode : NSObject {
id data;
ListNode *next;
}
@property (retain,nonatomic,readwrite) id data;
@property (retain,nonatomic,readwrite) ListNode* next;
- (ListNode *) initWithObject: (id) object;
- (ListNode *) copy;
@end
@implementation ListNode
@synthesize next, data;
- (ListNode *) initWithObject: (id)object {
self = [super init];
if(self != nil) {
self.data = object;
self.next = nil;
}
return self;
}
- (void)dealloc {
NSLog(@"ListNode dealloc %@", data);
[data release];
[next release];
[super dealloc];
}
-(ListNode *) copy {
ListNode *l = [[ListNode alloc]
initWithObject: [self.data copy]];
return l;
}
// copy caller must release |
@end |
@interface LinkedList : NSObject {
ListNode *first;
}
@property (retain, readwrite) ListNode* first;
+(LinkedList *) initWithObject: (id) object;
- (id) head;
- (LinkedList *) tail;
- (LinkedList *) cons: (id) object;
- (void) print;
-(LinkedList *) copy;
@end
@implementation LinkedList
@synthesize first;
+ (LinkedList *) initWithObject: (id) object {
LinkedList * l = [LinkedList alloc];
l.first = [[ListNode alloc] initWithObject:
[object copy]];
[l.first release];
return [l autorelease];
} |
- (void) print {
ListNode *node = first;
while( node != nil) {
NSLog(@"%@", node.data);
node = node.next;
}
}
- (id) head {
return [[first.data copy] autorelease];
}
- (LinkedList *) copy {
ListNode *n = self.first;
ListNode *l = [n copy];
LinkedList *t = [[LinkedList alloc]
init];
t.first = l;
do {
n = n.next;
l.next = [n
copy];
l = l.next;
} while( n != nil );
return t;
// copy caller must release
} |
- (LinkedList *) tail {
LinkedList *t = [self copy];
[t.first release];
t.first = t.first.next;
[t.first release];
return [t autorelease];
}
- (LinkedList *) cons: (id) object {
LinkedList *t;
t = [self copy];
ListNode *node = [[ListNode alloc] initWithObject: [object copy]];
node.next = t.first;
t.first = node; // setter has retain attribute
[node release];
return [t autorelease];
}
- (void)dealloc {
NSLog(@"LinkedList dealloc");
ListNode *node = self.first;
ListNode *next;
while(node != nil) {
next = node.next;
[node release];
node = next;
}
[super dealloc];
}
@end
|
int main (int argc, const char * argv[]) {
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
LinkedList * linkedList = [LinkedList initWithObject: @"3rd"];
linkedList = [linkedList cons: @"2nd"];
linkedList = [linkedList cons: @"1st"];
NSLog(@"____tail___");
[[linkedList tail] print];
NSLog(@"___head____");
NSLog(@"%@", [linkedList head]);
NSLog(@"___head(tail)____");
NSLog(@"%@", [[linkedList tail] head]);
NSLog(@"____full___");
[linkedList print];
[pool drain];
return 0;
}
|