Data structures and algorithms

5 min readOct 10, 2023

(Part IV — Linked Lists(1))

In a previous article, we explored arrays and discussed their advantages and disadvantages. We delved into topics like insertion, searching, and deletion, particularly in the context of unordered and ordered arrays. Today, we’ll shift our focus to another concept: linked lists. We’ll uncover how linked lists can address certain challenges and discuss their benefits when implementing them in stacks and queues.

The article will be structured as follows:

A Different Kind of Structure?

Relationship Between LinkedList and Array
A Simple Linked List
Advantages
Disadvantages
Use Case: Implementing a To-Do List
Algorithms

Relationship Between LinkedList and Array

Let’s examine one of the major ways in which linked lists differ from arrays. In an array each item occupies a particular position. This position can be directly accessed using an index number. It’s like a row of houses: You can find a particular house using its address. In a list the only way to find a particular element is to follow along the chain of elements. It’s more like human relations. Maybe you ask Harry where Bob is. Harry doesn’t know, but he thinks Jane might know, so you go and ask Jane. Jane saw Bob leave the office with Sally, so you call Sally’s cell phone. She dropped Bob off at Peter’s office, so…but you get the idea. You can’t access a data item directly; you must use relationships between the items to locate it. You start with the first item, go to the second, then the third, until you find what you’re looking for.

A Simple Linked List

A Simple Linked List is a fundamental data structure used in computer science and programming for organizing and storing a collection of elements. It consists of a series of nodes, where each node contains two main components: data and a reference (or link) to the next node in the sequence. The last node typically has a reference to null, indicating the end of the list.

Advantages

Linked Lists offer several advantages. They can dynamically adjust their size during runtime, making them adaptable to changing element counts without the need for a fixed, pre-allocated size. Efficiency shines through operations involving insertions and deletions, especially at the list’s beginning or middle. These actions require minimal pointer updates, rendering them faster than equivalent array operations. Memory usage is efficient too, with Linked Lists allocating memory individually for each element, reducing wastage compared to fixed-size arrays. Unlike arrays, Linked Lists don’t suffer from wasted space when preallocated but not fully used. Their versatility extends to efficiently implementing other data structures like stacks and queues. Additionally, Linked Lists provide constant-time head operations, such as adding or removing the first element, which remain consistently efficient, irrespective of the list’s size.

Disadvantages

Linked Lists come with several disadvantages. Random access to elements using an index is notably slower, as reaching a specific element necessitates traversing the list from the beginning, resulting in linear time complexity (O(n)) for access operations. The use of additional memory for pointers/references alongside data can increase memory overhead, making Linked Lists less memory-efficient than arrays for large data storage. Managing pointers and references within Linked Lists can be more complex and prone to errors compared to working with arrays. Furthermore, due to their scattered memory locations, Linked Lists may not fully utilize CPU cache memory, potentially leading to slower performance in specific scenarios. Linked Lists are also unsuitable for certain algorithms and operations heavily reliant on random access or requiring contiguous memory. Additionally, traversing a Linked List can be slower than iterating through an array due to the added pointer-chasing overhead.

Use Case: Implementing a To-Do List

Imagine you’re building a to-do list application. Each item on the to-do list has a task description and a status (completed or not completed). A linked list can be a suitable data structure for managing this list of tasks.

Algorithms

Initialization:

Create an empty linked list. This involves creating a reference to the head (the first node), which is initially set to null.

Insertion at the Beginning :

To add a new node with data x at the beginning of the linked list:
Create a new node with data x.
Set the next pointer of the new node to point to the current head.
Update the head to point to the new node.

Insertion at the End :

To add a new node with data x at the end of the linked list:
Create a new node with data x.
Traverse the list to find the last node (the node with a next pointer equal to null).
Set the next pointer of the last node to point to the new node.

Insertion after a Given Node :

To insert a new node with data x after a specific node with data y:
Create a new node with data x.
Traverse the list to find the node with data y.
Set the next pointer of the new node to the node’s current next pointer.
Update the next pointer of the node with data y to point to the new node.

Deletion of a Node :

To delete a node with data x from the linked list:
Traverse the list to find the node with data x and keep track of the previous node.
Update the next pointer of the previous node to skip the node with data x.

Search :

To search for a node with data x:
Traverse the list, comparing the data of each node with x.
If a match is found, return the node; otherwise, return null.

In summary, Linked Lists excel in scenarios where dynamic size, efficient insertions/deletions, and constant-time head operations are essential. However, they may not be the best choice for situations requiring fast random access or minimal memory overhead.