Overview:

In our pursuit of becoming better programmers, we will next learn about data structures. In this article, let’s explore the most basic data structure: Linked List. Let’s learn what linked lists are, when and why they are useful and the different types of linked lists we can implement.

What are Linked Lists?

A linked list is a sequence of nodes, where each node stores some data and also keeps track of the next node in the list. Fundamentally, a linked list is a linear data structure.

What is a Linear Data Structure?

A data structure is said to be linear if its elements form a sequence. By definition, a sequence is an ordered set, which means that each node in the list is added and stored in order. Another example of a linear data structure besides Linked Lists would be Arrays.

What are nodes?

Each element in a linked list is called a node. For the most simple linked list, a node needs to store a value and also needs to keep track of the next node in the list. More specifically, the node can be written as an abstract data type, for example a Class, which has a private variable to store the data and another private pointer variable to store the address of the next node in the list.

Why use Linked Lists?

Linked lists are functionally similar to arrays. Both linked lists and arrays can be used to store a collection of data. As a matter of fact, retrieving elements in an array could be done in constant time, which is faster than the time it takes to find an element in a linked list. However, the property that makes linked lists more applicable compared to arrays is its ability to allocate memory dynamically.

When we declare an array, we need to also specify the maximum number of elements it will hold. This specification is necessary because arrays cannot allocate memory dynamically and thus needs to statically specify the number of memory blocks it needs from the memory space. Since arrays are linear data structures, they store elements in order of their insertion. However, arrays also require contiguous blocks of ordered physical memory spaces to store its values. Since the number of elements are unknown at the beginning, the memory allocation is almost always excessive. You can learn more about this here.

Compared to arrays, linked lists do not require contiguous blocks of physical memory. Each block can be scattered and exist in different memory spaces. Each block contains a pointer to the next block, which keeps the order of the list intact. Also, insertion or deletion of elements is more feasible because we do not need to keep track of how many elements we can fit in the list. The list grows with our data.

Limitations of using Linked Lists:

All linked list operations require a full list traversal. Operations could include, insertion, deletion or retrieving elements. This makes the runtime of each operation O(n) which is a disadvantage considering an arrays ability to retrieve and element in constant time. Linked lists are suitable when dynamic memory allocation is a priority over constant search time.

Types of Linked Lists:

There are three basic types of linked lists:

• Singly Linked List: Singly linked lists are the most common type of linked list. The singly linked list consists of a head node and each node contains a pointer to the next node in the list. Traversal is done starting at the head and going through each node. The last node in the list points to null.
• Doubly Linked List: Doubly linked lists are similar to singly linked lists except for the fact that each node is connected to the previous node in addition to the next node. This makes traversing the list possible from both direction, which is an improvement for the search runtime. Also, complete traversal is possible starting from any element in the list. The pointer pointing to the previous element in the head points to null and the pointer pointing to the next element in the last element points to null.
• Circular Linked List: Circular Linked lists have no ends. A circular linked list could be both singly or doubly linked. The list is circular because the last element points back to the first element. A thing to remember when implementing circular linked list is to keep track of the head element, or else the traversal could easily turn into an infinite loop.

In a nutshell:

Linked list is one of the most basic linear data structures. A linked list is a sequence of nodes which store some data and also store the address of the next node in the list. Compared to other linear data structures like the array, linked lists provide dynamic memory allocation capabilities which help us create lists that grow with our data. Most linked list operations require O(n) runtime and therefore should be used when dynamic memory allocation is a priority over faster runtime.