Introduction to data structures: Linked Lists
Learn about the linked lists data structure in an intuitive way
The second data structure that most programmers are introduced to is
the linked list.
Linked lists are often juxtaposed with arrays.
Let's learn what linked lists are and how they compare to arrays.
What is a linked list?
The essence of the linked list data structure is contained in its
name. It's a group of elements that have links between them. These
links allow the elements to form a list.
In the simplest form of
a linked list, each element has a link to the next element. In a more
complex form, each element has a link to the previous and next element
(doubly linked list).
Linked lists also contain an additional link to the first element of
the list. This link is usually called "head" because it points to the
head (i.e. start) of the list. Linked lists can also contain an
additional link to the last element of the list. This link is usually
called "tail" because it points to the tail (i.e. end) of the list.
These links give the linked list certain "superpowers", but
everything comes with a price.
Before looking into the "superpowers" of the linked list data structure, it's important to note that the elements in a linked list are often called "nodes". A node is constructed of two parts:
- The first part contains the data.
- The second part contains the link(s) to other nodes.
As a comparison, the array data structure is not composed of nodes
since its elements only contain data, they don't have links to other
elements.
When talking about linked lists we will use the terms
"element(s)" and "node(s)" interchangeably.
What "superpowers" do linked lists have?
They are able to easily insert and remove elements.
To insert an element at the start of the list, we simply have to make
the new element point its link at the head of the list and make the
new element be the new head of the list.
To insert an element at the end of the list, we simply have to make
the last element in the list point its link to the new element. If the
list has a "tail" link we also need to make the new element be the new
tail of the list.
What do we need to do if we want to insert an element somewhere in the
middle of the list? As an exercise, try to figure out the steps.
To remove an element from the list, we simply have to make the
predecessor of the element we want to remove point its link to the
successor of the element we want to remove. In case we are removing
from the start of the list we need to update the "head" link. In case
we are removing from the end of the list and the list has a "tail"
link we need to update the "tail" link.
We don't have to create a new linked list, copy and shift elements
etc. as we have to do if we are using arrays.
What is the price that linked lists pay for their "superpowers"?
Linked lists consume more memory compared to arrays. In addition to
the data that each node stores, each node has to store a link to the
next node in the list (in case of doubly linked lists, each node has
to store two links).
Linked lists have to store the "head" link. An additional link has to
be stored if the linked list has a "tail" link.
Opposed to arrays, the elements of a linked list are not sequential in
the computer's memory. This means fewer opportunities for caching.
Linked lists do not offer access to their elements using idices as
arrays do.
When should linked lists be used?
- When the number of elements is not known upfront.
- When we need to insert/remove elements.
The linked list is a more dynamic data structure than the array.
To decide which one to use, ask yourself if the order of the elements
or their number is likely to change. If the answer is "yes", the
linked list data structure is a better choice.
If you enjoy my articles, please consider supporting me.