Singly Linked List

- Unordered array has fast insertion and slow search and deletion; ordered array has fast search and slow insertion and deletion; arrays have constant size;

Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;

Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.

Unordered (unsorted) Singly Linked List

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the list
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the list
- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the list
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the list
- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of  singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Search for the item with specific value (key):

- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)

Ordered (sorted) Singly Linked List

Operations:

// TBD