Data Structures

Classes
class	NILinkedList
	A singly linked list implementation. More...

Overview

For classic computer science data structures.

NILinkedList has been deprecated and will soon be removed altogether. Use NSMutableOrderedSet instead.

iOS provides most of the important data structures such as arrays, dictionaries, and sets. However, it is missing some lesser-used data structures such as linked lists. Nimbus makes use of the linked list data structure to provide an efficient, least-recently-used cache removal policy for its in-memory cache, NIMemoryCache.

Comparison of Data Structures

  Requirement           | NILinkedList | NSArray | NSSet | NSDictionary
  =====================================================================
  Instant arbitrary     |     YES      |   NO    |  YES  |     YES
  insertion/deletion    |     [1]      |         |       |
  ---------------------------------------------------------------------
  Consistent object     |     YES      |   YES   |  NO   |     NO
  ordering              |              |         |       |
  ---------------------------------------------------------------------
  Checking for object   |     NO       |   NO    |  YES  |     NO
  existence quickly     |              |         |       |
  ---------------------------------------------------------------------
  Instant object access |     YES      |   NO    |  YES  |     YES
                        |     [1]      |         |       |     [2]
  ---------------------------------------------------------------------

• [1] Note that being able to instantly remove and access objects in a NILinkedList requires additional overhead of maintaining NILinkedListLocation objects in your code. If this is your only requirement, then it's likely simpler to use an NSSet. A linked list is worth using if you also need consistent ordering, seeing as neither NSSet nor NSDictionary provide this.
• [2] This assumes you are accessing the object with its key.

Why NILinkedList was Built

NILinkedList was built to solve a specific need in Nimbus' in-memory caches of having a collection that guaranteed ordering, constant-time appending, and constant time removal of arbitrary objects. NSArray does not guarantee constant-time removal of objects, NSSet does not enforce ordering (though the new NSOrderedSet introduced in iOS 5 does), and NSDictionary also does not enforce ordering.