Single Linked List

The Single Linked list is our first data structure in the data structures series. 
What is a Linked List?
A data structure that contains a head, tail and length property. Linked Lists consist of nodes, and each node has a value and a pointer to another node or null.
 

Comparisons With Arrays
Lists 

• Do not have indexes!
• Connected via nodes with a next pointer
• Random access is not allowed

Arrays

• Indexed in order!
• Insertion and deletion can be expensive
• Can quickly be accessed at a specific index

How a Singly Linked List Works
A singly linked list comprises a bunch of nodes, each node contains a piece of data and also points to the next node. Looking at the image above 4 is the first node in the list also called the head of the list. 4 points to the next node which is 6 which in turn points to the next 8 and so on.
Since each node points to the next node, when traversing a linked list we start from the head, before moving to the next node till we get to the tail. We cannot start from an index of a singly linked list like we do an array, because the singly linked list is not indexed we always have to start from the beginning to get to where we want to go in the list. 
BigO of Singly Linked Lists
Insertion –   O(1)
Removal –   It depends… O(1) or O(N)
Searching –   O(N)
Access –   O(N)
Key Points

• Singly Linked Lists are an excellent alternative to arrays when insertion and deletion at the beginning are frequently required.
• Arrays contain a built in index whereas Linked Lists do not.
• The idea of a list data structure that consists of nodes is the foundation for other data structures like Stacks and Queues

Written by Ebube Okocha