Data Structures

---

Overview

For classic computer science data structures.

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.

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