Overview

Linked lists are linear data structures that store elements in nodes, which are not stored in consecutive memory locations, unlike arrays. Instead, each node contains its data and a reference (or link) to the next node in the sequence, allowing for dynamic memory allocation and flexibility in inserting or deleting nodes. This structure makes linked lists particularly suitable for applications where memory space is a premium and modifications to the data structure are frequent. However, unlike arrays, linked lists do not allow direct access to elements, which can lead to slower search times as it requires sequential traversal from the start of the list.

Visualization

There are a few kinds of linked lists (e.g. single-linked list, double linked list, circular linked list). However, single-linked lists seem to be the most prevalent in interviews, which is what we’ll focus on for now.

As you can see, a linked list is made up of nodes, which usually have 2 parameters: a value, and pointer to the next node in the sequence.

Linked Lists vs. Arrays

At first, linked lists and arrays may seem similar in terms of functionality, but there are some important differences between them, and such questions may be asked in technical interviews.

• Appending to the start of a linked list is O(1) time, but appending to the start of an array is O(N) time.
  • When we have a linked list, chances are that we have reference to the head node. To add an element to the head, all we need to do is create a new node, set the next node to be the current head, and set the head to be that newly created node.
  • On the other hand, when we want to append an element to the array, we must first create a new array and then manually add all elements from the old array to the new one, resulting in a time complexity of O(N).
• Retrieving the value at a position or index is O(1) time for arrays but O(N) time for linked lists.
  • Unlike arrays, we don’t assign the nodes to a particular position or index. Thus, to find the node at any position, we must iterate through the linked list and maintain a counter variable, resulting in a time complexity of O(N).

Now that we have a general idea on how linked lists work, let’s walk through some problems.

Example 1: Reverse Linked List

This is a classic linked list problem. You’re given a linked list, and you need to referse it, as shown in the example below.

Let’s start with brainstorming.

• Instead of jumping into reversing an entire list, let’s think about how we would reverse any pair of nodes. First and foremost, we need to have references to those 2 nodes, such as prev and curr. Moreover, we would set the next pointer of curr to be prev - curr.next = prev, and we would set the curr pointer to the prev pointer. Thus, we know that the our algorithm will involve the 2 lines below:

  curr.next = prev

  prev = curr

• Above, we reverse the linked list for a pair of nodes, but what about for an entire list? If we just focus on reversing a pair, how would we have access to the remaining nodes in the list?

  Assume we have the reference to 2 nodes: prev and curr. To avoid losing access to all other nodes, we could declare a tmp variable and set to the next node after curr - tmp = curr.next.

  As you can see above, we set prev to curr . To continue moving onto the next pair, we would then set curr to tmp - curr = tmp.