The iOS framework that grows only as fast as its documentation
Data Structures


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


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]

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.