Linked List in RAM and Its Performance

Last week, I discussed arrays and their basic operations. Now, let’s dive into Linked Lists and how they work.

What is a Linked List?

A Linked List consists of multiple Nodes, where each node contains two parts: a value (the data) and a pointer that references the next node or points to NULL (indicating the end of the list). After hearing this, you might wonder: How do we access a specific index? Unfortunately, unlike arrays, Linked Lists don’t allow direct indexing. To access a specific element, you have to traverse the list from the beginning, node by node, until you find the desired value. This gives Linked Lists a time complexity of O(n) for access and searching.

Linked List Operations: Insertion and Deletion

While accessing or searching takes O(n) time, insertion and deletion can be done in O(1) time in certain cases. How is this possible?

When inserting, all you need to do is adjust the pointer of the previous node to link it to the new node, and vice versa for deletion. If you're adding or removing an element at the beginning of the Linked List, the operation is constant time O(1). However, in the worst case—such as inserting or deleting at the end of the list—you'll need to traverse the list to find the last node, which takes O(n) time.

Linked List vs. Arrays in RAM

In my previous article on arrays, I explained that arrays store data in sequential order in RAM, whether they are dynamic or static. Even in dynamic arrays, the memory is allocated sequentially. But with Linked Lists, it’s different.

Linked Lists do not store nodes in consecutive memory locations. Each node is placed wherever there’s available memory in RAM, and the nodes are connected through pointers. This flexibility allows for efficient insertion and deletion operations, as Linked Lists don’t need to reallocate large blocks of memory, unlike dynamic arrays.

Singly vs. Doubly Linked Lists

When working with Linked Lists, there are two main types you’ll encounter: Singly Linked Lists and Doubly Linked Lists. Both types have different structures and use cases depending on how you need to traverse or manipulate the data.

1. Singly Linked List

In a Singly Linked List, each node contains two elements:

• A value (the data)

• A pointer to the next node in the list

This structure means you can only traverse the list in one direction—from the first node (head) to the last node (tail). If you need to go backward, you'd have to start over from the head and work your way forward again. Because of this, operations like insertion or deletion at the end of the list take O(n) time, as you have to traverse the entire list to find the last node.

Advantages:

• Requires less memory, as each node only stores one pointer (to the next node).

• Simpler to implement.

Disadvantages:

• You can only traverse in one direction.

• Deleting or inserting at the end or in the middle requires traversal, which can be less efficient.

2. Doubly Linked List

A Doubly Linked List, on the other hand, contains three elements in each node:

• A value (the data)

• A pointer to the next node

• A pointer to the previous node

With this structure, you can traverse the list in both directions—forward and backward—because each node points to both its successor and predecessor. This feature makes certain operations, like deletion, faster because you can access nodes in both directions without having to traverse from the beginning. For example, deleting the last node in a doubly linked list takes O(1) time, unlike in a singly linked list where it takes O(n).

Advantages:

• Allows traversal in both directions.

• Easier and faster to delete or insert nodes at the end or middle of the list.

Disadvantages:

• Requires more memory, as each node needs to store two pointers (to the next and previous nodes).

• More complex to implement.

When to Use Singly vs. Doubly Linked Lists?

• Singly Linked Lists are useful when you only need to traverse the list in one direction, and you want to save on memory.

• Doubly Linked Lists are better suited when you need quick access to both the previous and next nodes, such as in cases where you frequently need to traverse the list in reverse or delete nodes from the end.