NILinkedList Class Reference

Overview

A singly linked list implementation.

This data structure provides constant time insertion and deletion of objects in a collection.

A linked list is different from an NSMutableArray solely in the runtime of adding and removing objects. It is always possible to remove objects from both the beginning and end of a linked list in constant time, contrasted with an NSMutableArray where removing an object from the beginning of the list could result in O(N) linear time, where N is the number of objects in the collection when the action is performed. If an object's location is known, it is possible to get O(1) constant time removal with a linked list, where an NSMutableArray would get at best O(N) linear time.

This collection implements NSFastEnumeration which allows you to use foreach-style iteration on the linked list. If you would like more control over the iteration of the linked list you can use -[NILinkedList objectEnumerator]

When You Should Use a Linked List

Linked lists should be used when you need guaranteed constant-time performance characteristics for adding arbitrary objects to and removing arbitrary objects from a collection that also enforces consistent ordering.

Linked lists are used in NIMemoryCache to implement an efficient, least-recently used collection for in-memory caches. It is important that these caches use a collection with guaranteed constant-time properties because in-memory caches must operate as fast as possible in order to avoid locking up the UI. Specifically, in-memory caches could potentially have thousands of objects. Every time we access one of these objects we move its lru placement to the end of the lru list. If we were to use an NSArray for this data structure we could easily run into an O(N^2) exponential-time operation which is absolutely unacceptable.

Modifying a linked list

To add an object to a linked list, you may use addObject:.

[ll addObject:object];

To remove some arbitrary object in linear time (meaning we must perform a scan of the list), use removeObject:

[ll removeObject:object];

Note that using a linked list in this way is way is identical to using an NSMutableArray in performance time.

Accessing a Linked List

You can access the first and last objects with constant time by using firstObject and lastObject.

id firstObject = ll.firstObject;
id lastObject = ll.lastObject;

Traversing a Linked List

NILinkedList implements the NSFastEnumeration protocol, allowing you to use foreach-style iteration over the objects of a linked list. Note that you cannot modify a linked list during fast iteration and doing so will fire an assertion.

for (id object in ll) {
  // perform operations on the object
}

If you need to modify the linked list while traversing it, an acceptable algorithm is to successively remove either the head or tail object, depending on the order in which you wish to traverse the linked list.

Traversing Forward by Removing Objects from the List

while (nil != ll.firstObject) {
  id object = [ll firstObject];

  // Remove the head of the linked list in constant time.
  [ll removeFirstObject];
}

Traversing Backward by Removing Objects from the List

while (nil != ll.lastObject) {
  id object = [ll lastObject];

  // Remove the tail of the linked list in constant time.
  [ll removeLastObject];
}

Examples

Building a first-in-first-out list of operations

NILinkedList* ll = [NILinkedList linkedList];

// Add the operations to the linked list like you would an array.
[ll addObject:operation1];

// Each addObject call appends the object to the end of the linked list.
[ll addObject:operation2];

while (nil != ll.firstObject) {
  NSOperation* op1 = [ll firstObject];
  // Process the operation...

  // Remove the head of the linked list in constant time.
  [ll removeFirstObject];
}

Removing an item from the middle of the list

NILinkedList* ll = [NILinkedList linkedList];

[ll addObject:obj1];
[ll addObject:obj2];
[ll addObject:obj3];
[ll addObject:obj4];

// Find an object in the linked list in linear time.
NILinkedListLocation* location = [ll locationOfObject:obj3];

// Remove the object in constant time.
[ll removeObjectAtLocation:location];

// Location is no longer valid at this point.
location = nil;

// Remove an object in linear time. This is simply a more concise version of the above.
[ll removeObject:obj4];

// We would use the NILinkedListLocation to remove the object if we were storing the location
// in an external data structure and wanted constant time removal, for example. See
// NIMemoryCache for an example of this in action.

See Also

NIMemoryCache

Using the location object for constant time operations

NILinkedList* ll = [NILinkedList linkedList];

[ll addObject:obj1];
NILinkedListLocation* location = [ll addObject:obj2];
[ll addObject:obj3];
[ll addObject:obj4];

// Remove the second object in constant time.
[ll removeObjectAtLocation:location];

// Location is no longer valid at this point.
location = nil;

Tasks
Querying a Linked List
(NSUInteger)	- count
(id)	- firstObject
(id)	- lastObject
(NSArray *)	- allObjects
(NSEnumerator *)	- objectEnumerator
(BOOL)	- containsObject:
(NSString *)	- description
Creating a Linked List
(NILinkedList *)	+ linkedList
(NILinkedList *)	+ linkedListWithArray:
(id)	- initWithArray:
Constant-Time Access
(NILinkedListLocation *)	- locationOfObject:
(id)	- objectAtLocation:
(void)	- removeObjectAtLocation:
Adding Objects
(NILinkedListLocation *)	- addObject:
(void)	- addObjectsFromArray:
Removing Objects
(void)	- removeAllObjects
(void)	- removeObject:
(void)	- removeFirstObject
(void)	- removeLastObject

Method Documentation

count

Returns the number of objects currently in the linked list.

- (NSUInteger)count;

Discussion

Returns

The number of objects currently in the linked list.

firstObject

Returns the first object in the linked list.

- (id)firstObject;

Discussion

Returns

The first object in the linked list. If the linked list is empty, returns nil.

lastObject

Returns the last object in the linked list.

- (id)lastObject;

Discussion

Returns

The last object in the linked list. If the linked list is empty, returns nil.

linkedList

Returns a newly allocated and autoreleased linked list.

+ (NILinkedList*)linkedList;

Discussion

Identical to [[[NILinkedList alloc] init] autorelease];

linkedListWithArray:

Returns a newly allocated and autoreleased linked list filled with the objects from an array.

+ (NILinkedList*)linkedListWithArray:(NSArray *)array;

Discussion

Identical to [[[NILinkedList alloc] initWithArray:array] autorelease];

initWithArray:

Initializes a newly allocated linked list by placing in it the objects contained in a given array.

- (id)initWithArray:(NSArray *)anArray;

Discussion

Parameters

anArray

An array.

Returns

A linked list initialized to contain the objects in anArray.

allObjects

Returns an array containing the linked list's objects, or an empty array if the linked list has no objects.

- (NSArray*)allObjects;

Discussion

Returns

An array containing the linked list's objects, or an empty array if the linked list has no objects. The objects will be in the same order as the linked list.

objectEnumerator

Returns an enumerator object that lets you access each object in the linked list.

- (NSEnumerator*)objectEnumerator;

Discussion

Returns

An enumerator object that lets you access each object in the linked list, in order, from the first object to the last.

Attention

When you use this method you must not modify the linked list during enumeration.

containsObject:

Returns a Boolean value that indicates whether a given object is present in the linked list.

- (BOOL)containsObject:(id)anObject;

Discussion

Run-time: O(count) linear

Returns

YES if anObject is present in the linked list, otherwise NO.

description

Returns a string that represents the contents of the linked list, formatted as a property list.

- (NSString*)description;

Discussion

Returns

A string that represents the contents of the linked list, formatted as a property list.

locationOfObject:

Searches for an object in the linked list.

- (NILinkedListLocation*)locationOfObject:(id)object;

Discussion

The NILinkedListLocation object will remain valid as long as the object is still in the linked list. Once the object is removed from the linked list, however, the location object is released from memory and should no longer be used.

TODO (jverkoey July 1, 2011): Consider creating a wrapper object for the location so that we can deal with incorrect usage more safely.

Run-time: O(count) linear

Returns

A location within the linked list.

objectAtLocation:

Retrieves the object at a specific location.

- (id)objectAtLocation:(NILinkedListLocation *)location;

Discussion

Run-time: O(1) constant

removeObjectAtLocation:

Removes an object at a predetermined location.

- (void)removeObjectAtLocation:(NILinkedListLocation *)location;

Discussion

It is assumed that this location still exists in the linked list. If the object this location refers to has since been removed then this method will have undefined results.

This is provided as an optimization over the O(n) removal method but should be used with care.

 Run-time: O(1) constant

addObject:

Appends an object to the linked list.

- (NILinkedListLocation*)addObject:(id)object;

Discussion

Run-time: O(1) constant

Returns

A location within the linked list.

addObjectsFromArray:

Appends an array of objects to the linked list.

- (void)addObjectsFromArray:(NSArray *)array;

Discussion

Run-time: O(l) linear with the length of the given array

removeAllObjects

Removes all objects from the linked list.

- (void)removeAllObjects;

Discussion

Run-time: Theta(count) linear

removeObject:

Removes an object from the linked list.

- (void)removeObject:(id)object;

Discussion

Run-time: O(count) linear

removeFirstObject

Removes the first object from the linked list.

- (void)removeFirstObject;

Discussion

Run-time: O(1) constant

removeLastObject

Removes the last object from the linked list.

- (void)removeLastObject;

Discussion

Run-time: O(1) constant