Linked lists

1. Definition
2. Queue data structure
3. Stack data structure
4. Arrays vs linked lists

• A linked list is usually described as a node-based data structure.
• In this context, nodes can be described as containers for data.

// generic node interface, contains data as well as
// a pointer to the next node in the linked list
interface Node<T> {
    data:T
    next:Node<T> | null
}

// use the interface to define a node class used
// for a linked list containing strings
class StringNode implements Node<string> {
    data:string;
    next:Node<string> | null;
    // doubly linked list
    prev:Node<string> | null;
    // initialize node
    constructor(s:string, n:Node<string>, p:Node<string>) {
        this.data = s;
        this.next = n || null;
        this.prev = p || null;
    }
}

• The interface creates a singly-linked list because the nodes reference each other using forward pointers only.
• As opposed, the classe creates a doubly-linked list because the nodes reference each other using backward and forward pointers.
• Linked list data structure properties :
  • It supports a dynamic number of nodes (as opposed to the array) and thus supports node insertion and deletion.
  • Insertion / deletion has a complexity of O(1) because it requires updating a constant number of pointers and nodes :
    • The list maintains references to the first node (head) and the last node (tail) at all times.
    • As a result, insertion or deletion at the ends of a linked list have a complexity of O(1).
    • Insertion or deletion at any other position in a list will require an additional O(n) traversal operation.

Notes :

• Traversal operations prior to any insertion / deletion in a linked list is not recommended. Better alternatives exist ...
• Many other data structures are in fact 'constrained' versions of a linked list, which is what makes them fast.

• A queue is a FIFO data structure that is implemented using a singly-linked list.
• It supports insertion of the tail and deletion + value retrieval of the head.
• As a result, all operations on a queue have a complexity of O(1) because they do not require traversal.

• A stack is a LIFO data structure that is implemented using a singly-linked list.
• It supports insertion as well as deletion + value retrieval of the head.
• As a result, all operations on a stack have a complexity of O(1) because they do not require traversal.

Notes :

• Arrays are fit for quick search and update operations on a static set of elements.
• Linked lists are fit for quick insertions / retrievals on a dynamic set of elements.
• Linked lists can be optimized by creating and initial pool of nodes to pick from / discard to during insertion/deletion to save time on memory allocation.
• ArrayLists are fit for quick search and update operations on a dynamic set of elements, as well as stack-like insertion/removal.
• Use case for a queue : async requests queue (you don't want more than 5 networks call running at the same time on the frontend).
• Native Javascript Arrays are actually implemented using an arraylist.
• Native javascript arrays can be reset by setting their length to zero to gain performance.