Linked Lists

What is a Linked List?

A Linked List is a type of linear data structure, where the elements are not stored at a contiguous location and are linked using pointers. Each element contains data and a reference to the next node. They do not have a reference to the previous node(singly linked list) unless it is a doubly linked list. This post will cover singly linked lists and their advantages/disadvantages over an array.

Traits of a Linked List

Each element, or node, is comprised of two items - the data and a reference to the next node, except for the last node which has a reference to null. The entry point into a linked list is called the head of the list. The head is not a separate node, but a reference to the first node. If the list is empty then the head is a null reference.

A linked list is flexible with the amount of elements it can contain. The amount of nodes in a list is not fixed and can grow or shrink on demand.

Advantages

Dynamic sizing

The size of arrays are fixed. This means we need to know the upper limit on the number of elements in advance. With a linked list, we don't have that limitation. Linked lists are favored when we are dealing with an unknown number of objects.

Insertion/Deletion

Insertion for arrays is expensive because the room has to be created for the new elements, which also means to create room existing elements have to be shifted. Insertion for linked lists takes constant time(O(1)) for beginning or end insertion as the only steps are to initialize a new node and then update the pointers. However, insertion to the middle of the linked list takes constant time since you need to iterate over n elements to get to the correct location before inserting the node. The same goes for deletion: beginning and end deletion takes constant time(O(1)) while deleting in the middle take linear time(O(n)).

Disadvantages

Random Access

Arrays support Random Access, which means elements can be accessed directly using their index in constant time(O(1)). For a linked list, the time complexity for accessing an element is linear(O(n)), as you do not have direct access to the individual elements like an array does.

Memory Cost

Linked lists require more memory per node as additional storage is required for pointers.