Singly Linked Lists
Here is a short introduction for singly linked lists.
Table of Content:
• What is a singly linked list
• Memory via a singly linked list
• The Big O Notation of singly linked lists
What is a singly linked list?
A linked list is a data structure that is made up of nodes. Nodes have a value and a pointer. The pointer points to either another node or null. Linked lists have the following properties: head, tail and length. The head is the first node on the linked list, the tail is the last node and the length is the total number of nodes. Each node is connected in only one direction to the next node.
Nodes don’t have indexes. So if we were to access the node with the value of 3 in this linked list, we would have to start from the head and then ask for the next node until we have reached the node with the value of 3. Random access is harder with a linked list in comparison to an array.
Memory via a singly linked list
Similarly to arrays, a linked list is a way to store elements in memory. However unlike arrays, linked lists can be stored anywhere in memory. Since each node of a linked list points to the next node, it is easier to add an element to a linked list. With linked lists, the items never have to be moved around in memory.
The Big O Notation of singly linked lists
- Insertion: O(1)
- Removal: O(N)
- Searching: O(N)
- Access: O(N)
