CocoaDev

Edit AllPages

The following is the actual Objective C class that implements a doubly-linked list (a variation of LinkedList). It can do the following:

*Addition of new elements to the front of the list *Forward traversal using internal iterator *Backward traversal *Removal of the item the iterator points at

Here’s the interface .h file:

// // LinkedList.h //

// Structure representing a // doubly-linked list node. typedef struct ListNode ListNode; struct ListNode { int value; ListNode *next; ListNode *prev; };

@interface LinkedList : NSObject { @private ListNode *head; ListNode *iterator; //bool reachedHead; //bool reachedTail; }

@end

Now for the implementation .m file:

// // LinkedList.m //

#import “LinkedList.h”

@implementation LinkedList

/* Instantiates new linked list with a

/* Adds a new element to the

/* Sets internal iterator to

/* Returns the value of the iterator node */

/* Iterates to the next node in order and

/* Iterates to the previous node in

/* Indicates that iterator

/* Indicates that iterator

/* Removes the iterator node from

@end

So, essentially this is it. I assume the basic knowledge of how linked list operates. You can just plug in this class and use it in your programs, although I think several things need to be added for comfortable operation, like element search e.t.c. You can test this class with a test sniplet like the following:

#import <Foundation/Foundation.h> #import “LinkedList.h”

int main (int argc, const char * argv[]) { NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

// insert code here...
LinkedList *test = [[LinkedList alloc] initWithHead: 0];

// testing addition
int i;
for (i = 1; i < 11; i++) {
	[test addToFront: i];
}
NSLog(@"-- Added 10 values");

// testing forward traversal
NSLog(@"-- Setting iterator to first node: %d", [test getFirst]);
NSLog(@"-- Going forward until we hit the last element...");
do {
	NSLog(@"---- Next element: %d", [test getNext]);
} while ([test atTail] == FALSE);
NSLog(@"-- We've hit the last element");

// testing back traversal
NSLog(@"-- Going back until we hit the first element...");
do {
	NSLog(@"---- Previous element: %d", [test getPrevious]);
} while ([test atHead] == FALSE);
NSLog(@"-- We've hit the first element");

// testing removal
NSLog(@"-- Going forward 5 times");
for (i = 0; i < 5; i++)
	NSLog(@"-- Next element: %d", [test getNext]);
NSLog(@"-- Current element with value %d", [test getCurrent]);
NSLog(@"-- Removing element with value %d", [test removeCurrent]);
NSLog(@"-- Continue forward traversal");
do {
	NSLog(@"---- Next element: %d", [test getNext]);
} while ([test atTail] == FALSE);
NSLog(@"-- We've hit the last element");

NSLog(@"-- Returning to front, going forward until we reach end");
NSLog(@"-- First element: %d", [test getFirst]);
do {
	NSLog(@"---- Next element: %d", [test getNext]);
} while ([test atTail] == FALSE);
NSLog(@"-- We've hit the last element");

[pool release];
return 0; }

One thing that still bugs me is that when you traverse back in this test program, the last traversal element gets printed twice, I guess because of the way my flag works.

–DimitriT


Wonderful object Dimitri. You’d actually be able to use it in Cocoa, which is good. A note about my comment earlier (I’m editing that part) it WILL work in C, but you’ll have to replace the cin and cout objects with printf() and gets()… I’d rather not mess with that though, because of buffer errors or whatever happens with those to…. Yeah, I started with C++… not a smart move V_V… Anyone have any ideas on how to implement multidimensional lists? Final note: Linked lists are GREAT for fetching command-line arguments. GREAT…. Then, you could implement an array of strings with a sizeof(whatever*argc) or something… But that wouldn’t be fun, object-oriented or cool. Or obfuscated.


Command line arguments? You are kidding… right? —- Although, If C++ is being used, I would just use the stl std::list and forego defining my own container. ;-)


Shh! They aren’t supposed to know about that!!!


This is cool. I’ve made some code edits that correct the issue of the last traveral element being accessed twice – fundamentally, the issue of course is that the boundary flag didn’t get updated until after the next iteration/check had already taken place. Initially I modified getPrevious and getNext to make sure to update the flags before returning, but then I realized maybe everythings just simpler if we do away with maintaining flags, and simply evaluate our boundaries in place? Makes the code simpler anyway. Thoughts? (I just commented out the parts I changed for now). Another question – is it better for getPrevious and getNext to keep returning the terminal value if the iterator is already at the boundary, or should it return NULL? –WardR


This is pretty cool, but if you change the way you detect the end/head to the way they do it on the STL library you could get a huge performance improvement when doing a lot of operations (i.e. particle systems). Instead of having the head and end pointing to nulls, create a NULL node and make it a circular list. That way you get rid of a lot of if statements.

darionco


I used this code for my game. (with changing int -> NSObject*, could contain all kind of classes) It worked well, until remove nodes. I found that after remove first node, ‘head’ is unavailable so next ‘getFirst’ call causes problem.

I added codes if(iterator == head) { head = iterator->next; } Now it works well! (spent 3 hours for this o_O)

minsumansu