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;

Definition at line 118 of file NIDataStructures.h.

Methods
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

- NILinkedList:

Returns the number of objects currently in the linked list.

Returns:

The number of objects currently in the linked list.

- (id) firstObject

Returns the first object in the linked list.

Returns:

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

Definition at line 295 of file NIDataStructures.m.

- (id) lastObject

Returns the last object in the linked list.

Returns:

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

Definition at line 301 of file NIDataStructures.m.

+ (NILinkedList *) linkedList

Returns a newly allocated and autoreleased linked list.

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

Definition at line 143 of file NIDataStructures.m.

+ (NILinkedList *) linkedListWithArray:

(NSArray *)

array

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

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

Definition at line 149 of file NIDataStructures.m.

- (id) initWithArray:

(NSArray *)

anArray

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

Parameters:

anArray

An array.

Returns:

A linked list initialized to contain the objects in anArray.

Definition at line 155 of file NIDataStructures.m.

- (NSArray *) allObjects

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

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.

Definition at line 312 of file NIDataStructures.m.

- (NSEnumerator *) objectEnumerator

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

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.

Definition at line 352 of file NIDataStructures.m.

- (BOOL) containsObject:

(id)

anObject

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

Run-time: O(count) linear

Returns:

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

Definition at line 326 of file NIDataStructures.m.

- (NSString *) description

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

Returns:

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

Definition at line 338 of file NIDataStructures.m.

- (NILinkedListLocation *) locationOfObject:

(id)

object

Searches for an object in the linked list.

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.

Definition at line 358 of file NIDataStructures.m.

- (id) objectAtLocation:

(NILinkedListLocation *)

location

Retrieves the object at a specific location.

Run-time: O(1) constant

Definition at line 346 of file NIDataStructures.m.

- (void) removeObjectAtLocation:

(NILinkedListLocation *)

location

Removes an object at a predetermined location.

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

Definition at line 371 of file NIDataStructures.m.

- (NILinkedListLocation *) addObject:

(id)

object

Appends an object to the linked list.

Run-time: O(1) constant

Returns:

A location within the linked list.

Definition at line 400 of file NIDataStructures.m.

- (void) addObjectsFromArray:

(NSArray *)

array

Appends an array of objects to the linked list.

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

Definition at line 432 of file NIDataStructures.m.

- (void) removeAllObjects

Removes all objects from the linked list.

Run-time: Theta(count) linear

Definition at line 445 of file NIDataStructures.m.

- (void) removeObject:

(id)

object

Removes an object from the linked list.

Run-time: O(count) linear

Definition at line 462 of file NIDataStructures.m.

- (void) removeFirstObject

Removes the first object from the linked list.

Run-time: O(1) constant

Definition at line 471 of file NIDataStructures.m.

- (void) removeLastObject

Removes the last object from the linked list.

Run-time: O(1) constant

Definition at line 477 of file NIDataStructures.m.