List

List

A List (or linked list) is a linear data structure formed by chaining Nodes together. Lists come in three varieties:

  • single: every node points to the next node
  • double: every node stores a reference to previous and next nodes
  • circular: the last node points to the first node

Instances of this class are doubly-linked lists.

Unlike arrays, Lists don't support random data access. When fetching data from a list, the cursor begins at head and sequentially visits each node. Thus, access data in a List is an O(n) operation.

Lists fare better than arrays in space complexity. Lists don't need to be contiguous. Furthermore, Nodes occupy exactly the memory they need so large chunks of memory need not be reserved beforehand. When an array fills up, the runtime creates a bigger array and copies all the items to the new array. This O(n) operation isn't relevant to Lists.

Adding or deleting at the beginning of a list takes O(1). Arrays take O(n).

Inserting or deleting at the end of a list takes O(n). Arrays take O(1). We keep reference to the last item in the List here to optimise performance and insert/delete at the end of list in O(1).

Guidance

Use an array when:

  • you want to access elements at random using an index, constant time O(1)
  • you need two-dimensional or multi-dimensional arrays

Use List when:

  • you want to access elements in a sequential manner only, like in stacks or queues
  • you would be inserting/deleting elements at the start and end of the list only. List takes constant time O(1), arrays O(n)
  • you have memory constraints. Array pre-allocate a large chunk of contiguous memory on initialisation. List are grow-as-you-go and don't need contiguous memory.

Constructor

new List()

Source:

Members

count

Returns the number of items in the list

Source:

Methods

add(data, atIndex) → {Node}

Add element at the given position in the list. If no index is specified, data is added to the end of the list.

Returns the newly created node.

Runtime:

  • O(1) for adding at start or end (default) of the list
  • O(n) otherwise
Parameters:
Name Type Description
data any
atIndex number

0 for adding at start of the list, or a positive integer to insert data in the middle.

Source:
Throws:

If index is negative or out of bounds

Type
OutOfBoundsError
Example
list.add(123)       // Adds '123' at the end of the list
 list.add(123, 0)    // Adds '123' at the beginning of the list
 list.add(123, 4)    // Adds '123' at index 4 or throws an error 

find(predicate) → (nullable) {any}

Search through the list for a node that matches the predicate.

Returns whatever the predicate returns. If predicate doesn't return a non-null value for any Node, returns null to indicate that the search failed.

Parameters:
Name Type Description
predicate List.FindPredicate
Source:

indexOf(value) → (nullable) {number}

Finds the first occurrence of value in the list.

Returns index of first occurrence or null. Runtime: O(n)

Parameters:
Name Type Description
value any
Source:
Example
// Given a list 1 → 2 → 3
 list.indexOf(2) // 1
 list.indexOf(5) // null

itemAtIndex(indexopt) → {any}

Get data stored at the given index. Runtime: O(n)

Parameters:
Name Type Attributes Default Description
index number <optional>
0
Source:
Throws:
Example
// Given a list 1 → 2 → 3
 list.itemAtIndex(2) // 3
 list.itemAtIndex(5) // null

remove(indexopt) → {any}

Removes list item at the given index and return the data held at the removed node. If no index is given, removes the last item.

Runtime:

  • O(1) when removing from start or end (default)
  • O(n) otherwise
Parameters:
Name Type Attributes Default Description
index number <optional>
last
Source:
Throws:
Example
list.remove(0)  // Removes first item
 list.remove(7)  // Removes 8th item or throws an out of bounds error
 list.remove()   // Removes last item

Type Definitions

FindPredicate(node, index) → (nullable) {any}

This closure is used to specify custom search predicate used by the find method. The function is passed a node and its index in the list on each iteration. Search continues until the closure returns a value other than null.

Parameters:
Name Type Description
node Node
index number
Source:
Example
// Returns the first node with even data, if none returns `null`
 const predicate = function(node, position) {
   if (node.data % 2 === 0) {
     return n
   }
   return null
 }